Automata, language problem

vectorcube

Let L be the language with alphabet {0, 1}.

L:={ w in {0, 1}* | number of 0 divisible by 5, number of 1 divisible by 3}


Find a deterministic finite automata & regular expression that express L.

Sorry, but this is sort of a problem that i got stuck in a book. Help me, please!

davee123

If I understand the notation correctly, you're looking for a regular expression capable of describing (for example):

00000111111
10010101011
0010010100000
1000000000011

but NOT (for example):

100101010110
100110101011
001001010000
100000000001

I can't think of a way to do this without making some sort of state machine, since you have to have some degree of memory in order to ensure that what you place going *forward* is in synch with what you've already placed into a given string. Hence, doesn't it by definition defy the possibility of having a regular expression?

I could see if you wanted something wherein you could not intersperse 1's and 0's in increments other than those divisible by 3 and 5 respectively. That you could do with a regular expression just fine. But interspersing them, I dunno-- my gut instinct says you can't do that with a regular expression.

DaveE

signerror

davee123 - Actually, a DFA exists. You only need a constant amount of memory, not an unbounded stack as with pushdown automata for general context-free grammars.

vectorcube: Are you familiar with the result that finite automata and regular expressions are equivalent? There is a very simple DFA (deterministic finite automaton) which accepts your language: it has 15 states, indexed by pairs (i,j) for 0<i<5 and and 0<j<3, where i and j respectively "count" the number of 0's, 1's seen so far (modulo 5 and modulo 3). That is, there are transitions from (i,j) -> (i+1 mod 5, j) on "0", and (i,j) -> (i, j+1 mod 3) on "1". The start and accept state is (0,0). Do you see how this counts digits?

Your regular expression will certainly be rather large (if you do want an explicit expression, which you probably don't). There are systematic ways to convert from DFAs to regular expressions (and vice versa); there should be a constructive proof in your book. E.g. in the 1st ed. of Hopcroft & Ullman it is theorem 2.4. So this is one way to get the regular expression; perhaps there is a simpler way.

Hope this is helpful.