Register

Gate2006-33

674 views
4 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

1 Answer

0 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.
Voting & Accepting an answer helps improve the community
← Previous · CFG: Removal of Unit...Next → · Register spilling
← Previous in category · CFG: Removal of Unit...Next in category → · Regular Grammar
Position:
Show:

Related questions

2 2 votes
0 0 answers
1.7k
1.7k views
sid1221 asked Aug 29, 2017
1,677 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}= cos...
0 0 votes
0 0 answers
1.1k
1.1k views
gabbar asked Oct 7, 2016
1,096 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 n...
0 0 votes
0 0 answers
555
555 views
Registered user 11 asked Jan 14, 2016
555 views
gate2006