language generated by G'={bcb,bbcb,bcbb,bbcbb,bcbbbb,bbbbbbb

language generated by G'={bcb,bbcb,bcbb,bbcbb,bcbbbb,bbbbbbbcb...} then why it is not regular? According to techtud test series answer is option a

6Comments
Vikash @vikasch
22 Dec 2014 06:18 pm

i know i also have many doubts regard techtud TOC test but these guys doing there best definitely they will improve it and make it much better . you do your best..... 

shelly jain @shellygangwal
22 Dec 2014 06:40 pm

definitely these guys doing their best but i just want to make sure what is the correct answer
 

Vikash @vikasch
22 Dec 2014 06:59 pm

first of all leave this question because it based on CSL or CSG which is not our course .

Arjun Suresh @arjunsuresh1987
23 Dec 2014 09:16 am

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. 

Saurav Das @sauravdas
24 Dec 2014 03:24 pm

What about the production Ab-->a ? Is this not CSG?

Vikash @vikasch
24 Dec 2014 03:47 pm

of course its CSG because it not following the condition of CFG that "alpha<=beta" 

Pages