## Automata, language problem

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!
 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
 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+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.