867 views

A regular grammar for the language $L= \{a^nb^m \mid \text{ n is even and m is even } \}$ is given by

1. $S \rightarrow aSb \mid S_1; S_1 \rightarrow bS_1a \mid \lambda$
2. $S \rightarrow aaS \mid S_1;S_1 \rightarrow bSb \mid \lambda$
3. $S \rightarrow aSb \mid S_1;S_1 \rightarrow S_1ab \mid \lambda$
4. $S \rightarrow aaS \mid S_1;S_1 \rightarrow bbS_1 \mid \lambda$

recategorized | 867 views

We can easily solve this by elimination through examples approach

A) S  - -> aSb - -> aS1b --> ab      //n=m=1 not even ; Not the answer

B) S --> aaS --> aaS1 --> aabSb-->aabaaSb -->aabaab // not in a n b m format ; Not the answer

C) S  - -> aSb - -> aS1b --> ab      //n=m=1 not even ; Not the answer

D) always make strings in a n b m format ; such that n and m are even //hence the answer

by Boss (33k points)
selected by
0
This method doesn't work for many cases as I am getting even length string in B and C as well.

Is it like that I need to find at least one case where this string produces odd length?
+1 vote

Given Language    L = { a^n b^m } where n is even and m is even

In simple words we can consider this Language as even no of a's followed by even no of b's .If we write down the Language then it would be something like this....

L = {∈ , aa , bb , aaaa , bbbb ........}

Option 1 Grammar can't give us "aa" as a substring so it is not the correct option.

Option 3 Grammar can't give us "bb" as a substring so it is not the correct option.

It seems like option 2 can give us even no of a's followed by even no of b's but it is not true because initially we can get even no of a's then off-course we can even get even no of b's but there is a small problem in it that is the production "S1 --->bSb " due to this production we can get even no of a's in middle of b's and it should not be happened. So it is not the correct option.

Option 4 can give us exactly what we want out of given Grammar and 'll satisfy the Given Languge.

by Boss (45.4k points)
0
Good and much-needed explanation.

Thanks