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

The Gateway to Computer Science Excellence

+3 votes

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

- $S \rightarrow aSb \mid S_1; S_1 \rightarrow bS_1a \mid \lambda$
- $S \rightarrow aaS \mid S_1;S_1 \rightarrow bSb \mid \lambda$
- $S \rightarrow aSb \mid S_1;S_1 \rightarrow S_1ab \mid \lambda$
- $S \rightarrow aaS \mid S_1;S_1 \rightarrow bbS_1 \mid \lambda$

+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

+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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,321 answers

198,402 comments

105,158 users