Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Automata, language problem

  1. Oct 16, 2009 #1
    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!
  2. jcsd
  3. Oct 16, 2009 #2
    If I understand the notation correctly, you're looking for a regular expression capable of describing (for example):


    but NOT (for example):


    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.

  4. Oct 18, 2009 #3
    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.
    Last edited: Oct 18, 2009
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook