Search code examples
context-free-grammarregular-languageautomata

if L = P ∩ Q where P is Context Free Language(CFL) and Q is Regular then L is in?


The intersection of a context free language P with a regular language Q, is said to be always context free,but I still don't get why it is context free but not regular.

The language generated by such an intersection has strings that are accepted both by a PDA and a DFA .Since all regular language are context free and it is accepted by a DFA, shouldn't it be a regular language?


Solution

  • The set of all strings from an alphabet is a regular language, and its intetsection with any other language L from that alphabet is precisely L.

    Or in other words, it is not just which strings are accepted. Also relevant is which strings are not accepted.