Register

Gate2006-33

504 views
4 votes
4 votes
In general we say that every regular language is CFL.

It is given regular union DCFL is context free. For eg if we take kleene closure as regular then union will be regular. If kleene closure is regular how can we say it is CFL?  Kleene closure can generate a^n b^nc^n but it is not CFL
User Avatar

1 Answer

0 votes
0 votes
Friend, you are looking confuse.

a^n b^n c^n are different from kleene closure. a^n b^n c^n is not context free because in CNF there is only stack data structure is used to compare the alphabet of string if required. Language is CNF only if there is  two or less than alphabet need to compare. Here there are three alphabet whose number are need to compare in string. That is not possible through single stack.

If any thing feel wrong plz comment.
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

2 votes
2 votes
0 answers
1
sid1221 asked Aug 29, 2017
1,149 views
ME , GATE2006
Assuming $i=\sqrt{-1}$ and t is real number , $\int_{0}^{\Pi /3} e^{it}dt$ given ans is $\sqrt{3}/2 + i/2 , and i am getting \sqrt{3}/2-i/2$ i solved first put $e^{it}= cost +isint$ then and integrate , but in solution they first integrate $e^{it}$ then put the value of it ... but ans different ... why is this happening .. am i missing something ??
Assuming $i=\sqrt{-1}$ and t is real number , $\int_{0}^{\Pi /3} e^{it}dt$given ans is $\sqrt{3}/2 + i/2 , and i am getting \sqrt{3}/2-i/2$i solved first put $e^{it}= cos...
User Avatar
0 votes
0 votes
0 answers
2
gabbar asked Oct 7, 2016
830 views
gate2006..topic digital logic
consider numbers represented in 4bit graycode. let h3h2h1h0 be the graycode representation of a number n and let g3g2g1g0 be the graycode of (n+1)modulo16) value of the number?
consider numbers represented in 4bit graycode. let h3h2h1h0 be the graycode representation of a number n and let g3g2g1g0 be the graycode of (n+1)modulo16) value of the n...
User Avatar
0 votes
0 votes
0 answers
3
Registered user 11 asked Jan 14, 2016
312 views
gate2006
User Avatar
Link Copied!