Is it a right way to find the regular grammar by construct an DFA?

Question

This is my homework.

Exercise 3: Find a regular grammar for the language L = { | n + m is an odd number}. Show the way you obtain it.

The question ask to show the way I obtain the answer. So here is my explain.

We construct the DFA

From DFA, we got
S -> aA | bA
A -> aS | bS | null

Therefore, the regular grammar is
G = {V , T , S, P}
where
V = {S, A}
T = {a, b}
P = {S -> aA | bA, A -> aS | bS | null}

However, the next question is:

Construct a DFA that accepts the language generated by the grammar in Exercise 3. Simplify the constructed DFA if possible.

So I think that drawing the DFA is not the expected explaining for Exercise 3. Perhaps there is another ways to obtain the regular language without drawing DFA. Please let me know.

Thank you.

Your DFA matches all odd-length strings containing only a and b. But the language you are supposed to solve is odd-length strings consisting of a run of as followed by a run of bs. So your DFA matches aba and baa, but the only string with 2 as and a b in the language is aab — rici, Nov 04 '15 at 22:47

fjardon · Answer 1 · 2015-11-23T14:47:40.870

Usually deriving the DFA is harder than deriving the grammar. Another thing is that by first building the grammar, you can produce the minimal DFA matching this grammar. If you start by building a DFA, you will have to derive the corresponding grammar and then derive the minimal DFA from this grammar.

As an example of why deriving the DFA is harder: your DFA doesn't match the language a^n b^m, n+m odd. It matches all odd length strings, even those whith a and b mixed like: ababa.

I tried to produce the corresponding grammar:

  S  -> 'a' L2
     -> 'b' B2

  L1 -> 'a' L2
     -> 'b' B2

  L2 -> 'a' L1
     -> 'b' B1

  B1 -> 'b' B2

  B2 -> \empty
     -> 'b' B1

S is the start symbol.
L1 represents odd sequences of a then b.
L2 represents even sequences of a then b.
B1 represents odd sequences of b.
B2 represents even sequences of b.

This grammar is right regular and suitable for building the DFA.

score 0 · Answer 2 · answered Nov 23 '15 at 13:41

Constructing a (correct) DFA first is a perfectly fine way to get the regular grammar. The point is that it's easy to convert between regular grammars and DFAs since they are encoding literally almost exactly the same information.

As pointed out in the comment, your DFA isn't right. You should really have something like this:

state    s    state'
------   -    ------
even_a   a    odd_a
even_a   b    odd_b
odd_a    a    even_a
odd_a    b    even_b
even_b   a    dead
even_b   b    odd_b
odd_b    a    dead
odd_b    b    even_b
dead     a    dead
dead     b    dead

Going to a grammar from that using your method will give the right thing. Note that "odd_a" and "odd_b" are accepting states.

Is it a right way to find the regular grammar by construct an DFA?

2 Answers2