-
Consider the following context-free grammar over the alphabet ∑ = {a, b, c} with S as the start symbol:
S → abScT | abcT
T → bT | b
Which one of the following represents the language generated by the above grammar?
-
- {(ab)n (cb)n] n ≥ 1}
- {(ab)n ... cbm1 cbm2 .......cbmn | n, m1, m2..., mn ≥ 1}
- {(ab)n (cbm)n | m , n ≥ 1}
- {(ab)n (cbn)m | m , n ≥ 1}
- {(ab)n (cb)n] n ≥ 1}
Correct Option: C
The given context free Grammar
∑ = {a , b , c} with S as the start symbol.
S → abScT/ abcT
T → bT/ b
The minimum length string generated by the grammar is 1.
Consider first case ( S → abcT ) then ( S → abcb ) .
Hence all the variable s are greater than 1.
Consider second case
S → abScT
→ ababScTcT
→ ababScTcTcT .............................. ..............................
→ (ab)n (CT)n
Here T can generate any number of b's string with single b, so (T = bm)
Hence, the language is
L = [ (ab)n ( cbm )n | m , n ≥ 1 ]
Hence option (c) is correct.
