The language generated by following grammar is: S → aSa | bSb | ε
The language generated by following grammar is:
S → aSa | bSb | εA. a<sup>n</sup> b<sup>m</sup> n ≥ 1, m ≥ 1
B. Odd length palindrome
C. a<sup>m</sup> b<sup>n</sup> n ≥ 0, m ≥ 0
D. Even length palindrome
Please scroll down to see the correct answer and solution guide.
Right Answer is: D
SOLUTION
Language generated by given grammar is
L = { ϵ, aa, aaaa, aaaaaa, …, bb, bbbb, bbbbbb,… abba, baab … }
Option 1: an bm n ≥ 1, m ≥ 1
Smallest string generated: ab (n = 1, m = 1 )
L does not contain string: ab. Therefore, option 1 is false
Option 2: Odd length palindrome
Odd length palindrome, String: a
L does not contain any odd length string. Therefore, option 2 is false
Option 3: am bn n ≥ 0, m ≥ 0
String generated: a (n = 1, m = 0)
L does not contain string: a. Therefore, option 3 is false
Option 4: Even length palindrome
Language L contains all even length palindrome. Therefore option 4 is correct