The Gateway to Computer Science Excellence
+3 votes
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$
in Theory of Computation by Veteran (105k points)
recategorized by | 867 views

2 Answers

+3 votes
Best answer

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

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
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,385 answers
198,558 comments
105,381 users