Identify the language generated by the following grammar , ISRO 2017 S -> AB A…
2017
Identify the language generated by the following grammar , ISRO 2017
S -> AB
A -> aAb|ϵ
B -> bB| b - A.
{ambn | n>=m, m>0}
- B.
{ambn | n>=m, m>=0}
- C.
{ambn | n>m, m>0}
- D.
{ambn | n>m, m>=0}
Attempted by 41 students.
Show answer & explanation
Correct answer: D
Step 1: Analyze Non-terminal A. The production A -> aAb | ε generates strings with equal numbers of 'a's and 'b's (e.g., ab, aabb). Thus, A generates { a^n b^n | n >= 0 }.
Step 2: Analyze Non-terminal B. The production B -> bB | b generates one or more 'b's (e.g., b, bb). Thus, B generates { b^k | k >= 1 }.
Step 3: Analyze Start Symbol S. The production S -> AB concatenates the strings from A and B. Resulting form is a^n b^n b^k = a^n b^{n+k}.
Step 4: Determine Language. Let m = n (count of 'a's) and p = n+k (count of 'b's). Since k >= 1, the count of 'b's is strictly greater than 'a's. The language is { a^m b^n | n > m, m >= 0 }.