326 views

1 Answer

Best answer
4 votes
4 votes

Lets see the strings generated by G and G'.

For G,
S -> bAcAb -> bcAb ->bcb

S -> bbSbb -> bbAcAbb -> bbcbb

S -> bbSbb -> bbAcAbb -> bbcAb -> bbcb

So, G is generating all strings where number of b's to the left of 'c' in the input string is greater than or equal to the number of b's to the right. So, L(G) is context-free but not regular.

For G' we have an extra production bA -> A which can condense any number of b's. So, G' will generate all strings over b and c containing at least one b before and after a c. This language is hence regular. 

So, (B) is correct. 

 

selected by

Related questions

2 votes
2 votes
1 answer
1
h4kr asked Dec 4, 2022
577 views
I don’t get the explanation, How do you categorize grammer on the basis of production?
0 votes
0 votes
0 answers
2
goluabhinan asked Sep 16, 2018
204 views
What is the difference between phase structured grammar and phrase structured grammar?
0 votes
0 votes
0 answers
4