Question 7886 – Theory-of-Computation
April 20, 2024
Question 7918 – Theory-of-Computation
April 20, 2024
Question 7886 – Theory-of-Computation
April 20, 2024
Question 7918 – Theory-of-Computation
April 20, 2024

GATE 2017 [Set-1]

Question 10
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?
A
{(ab)n (cb)n│n ≥ 1}
B
{(ab)n cb(m1 ) cb(m2 )…cb(mn )│n,m1,m2,…,mn ≥ 1}
C
{(ab)n (cbm)n│m,n ≥ 1}
D
{(ab)n (cbn)m│m,n ≥ 1}
Question 10 Explanation: 
T→ bT | b, this production will generate any number of b’s > 1
S→ abScT | abcT, this production will generate equal number of “ab” and “c” and for every “abc” any number of b’s ( > 1) after “abc”.
For Ex:

Hence the language generated by the grammar is
L = {(ab)n cb(m1 ) cb(m2 )…cb(mn )│n,m1,m2,…,mn ≥ 1}
Correct Answer: B
Question 10 Explanation: 
T→ bT | b, this production will generate any number of b’s > 1
S→ abScT | abcT, this production will generate equal number of “ab” and “c” and for every “abc” any number of b’s ( > 1) after “abc”.
For Ex:

Hence the language generated by the grammar is
L = {(ab)n cb(m1 ) cb(m2 )…cb(mn )│n,m1,m2,…,mn ≥ 1}
0 0 votes
Article Rating
Subscribe
Notify of
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x