recategorized by
4,460 views
4 votes
4 votes

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 by

2 Answers

Best answer
4 votes
4 votes

Answer must be D

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

selected by
1 votes
1 votes

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.

Answer:

Related questions

1 votes
1 votes
0 answers
1
go_editor asked Jul 22, 2016
972 views
Non-deterministic pushdown automaton that accepts the language generated by the grammar: $S \rightarrow aSS \mid ab$ is$\delta (q_0, \lambda , z)= \{ (q_1, z) \}; \delta...
1 votes
1 votes
1 answer
3
go_editor asked Jul 22, 2016
2,730 views
The language $L=\{a^n b^n a^m b^m \mid n \geq 0, m \geq 0 \}$ isContext free but not linearContext free and linearNot context free and not linearNot context free but line...