[Solved]: How do you describe a language that is generated by Context Free Grammer

Problem Detail: 

I am familiar with describing Regular Expressions but when it comes to describing CFG I get confused. Do you describe it in words like you would regular expressions or do you do something like this ?

this is the CFG I am trying to describe

S -> SS  S -> XXX  X -> aX| Xa| b 

I was thinking something like this

S-> SS   ->XXXS   ->aXXXs   ->abXXS   ->abXXS   ->abXAXS   ->abbaXS   ->abbabS   ->abbabS   ->abbabXXX   ->abbabbXX   ->abbabbbX   ->abbabbbb   ->abbabbbb 

Asked By : Dana

Answered By : Yuval Filmus

Hint: How many $b$s are there in each word generated by this grammar?

Guidance: What is the language generated by $X$? What is the language generated by $XXX$? What is the language generated by $S$?

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/23565

3.2K people like this

 Download Related Notes/Documents