I came across problem asking whether given statement is true and false. The statement given was as follows:

Every Type-2 grammar can generate regular language.

I felt that Type-2 grammar means, its context free grammar and is generated by PDA. PDA is more powerful than FA which generate regular languages. Hence any Type-2 grammar should be able to generate regular language. But the answer given was FALSE saying that there are Type-2 grammars which generate "pure CFL" (non regular languages).

So I was guessing whats going on here. I have following doubts:

  1. Is the question asking whether all CFLs are also regular? (which is not the case and thats why the given answer states "pure CFL")?

  2. Is the question asking whether every CFG generate "all" regular languages? (which is obviously senseless and hence is FALSE?)

  3. Is the answer FALSE because deterministic context free automata accepting on empty stack cannot even accept regular languages?


The question is poorly worded. Here is what they probably meant to ask:

Is the language generated by a context-free grammar always regular?

Clearly, the answer is negative.

However, this is just a guess, since the question isn't really clear. I suspect ignoring questions which are not clearly stated. If you encounter such a question in an exam, ask the setter to rephrase the question using proper English.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.