You marked answer C. Which is Quite close to D, Difference is Just that number of $a's$ could also be $0$.

The Gateway to Computer Science Excellence

+1 vote

Identify the language generated by the following grammar:

$S->AB$

$A->aAb|\epsilon$

$B->bB|b$

(A)$\{a^m b^n|n≥m, m>0\}$

(B)$\{a^m b^n|n≥m, m≥0\}$

(C)$\{a^m b^n|n>m, m>0\}$

(D)$\{a^m b^n|n>m, m≥0\}$

I select option C but it is wrong, correct answer is option D.

I could not understand Gradup answer explanation.Please help me to rectify my fault.

$S->AB$

$A->aAb|\epsilon$

$B->bB|b$

(A)$\{a^m b^n|n≥m, m>0\}$

(B)$\{a^m b^n|n≥m, m≥0\}$

(C)$\{a^m b^n|n>m, m>0\}$

(D)$\{a^m b^n|n>m, m≥0\}$

I select option C but it is wrong, correct answer is option D.

I could not understand Gradup answer explanation.Please help me to rectify my fault.

+2 votes

Best answer

Language Generated by Variable $A$ is $\left \{ a^mb^m | m\geq 0 \right \}$

Language generated by Variable $B$ is $\left \{ b^k | k> 0 \right \}$

So, Language generated by Variable $S$ will be Concatenation of above languages. Hence, $\left \{ a^mb^mb^k|m\geq 0,k> 0 \right \}$ Which can also be written as $\left \{ a^mb^n|m\geq 0,n>m \right \}$

Language generated by Variable $B$ is $\left \{ b^k | k> 0 \right \}$

So, Language generated by Variable $S$ will be Concatenation of above languages. Hence, $\left \{ a^mb^mb^k|m\geq 0,k> 0 \right \}$ Which can also be written as $\left \{ a^mb^n|m\geq 0,n>m \right \}$

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

50,650 questions

56,242 answers

194,289 comments

95,941 users