Gate2006-33

Question

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

Answer 1

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.