1
$\begingroup$

CFL is not closed under intersection. That means, if we have L1,L2 of CFL then

L1 intersection L2 is not a CFL

And we know, all Regular languages are CFL. Then how it is true that intersection of Regular language (R1) (which is again a CFL) and a CFL(CL1) is a CFL?

R1 intersection CL1 should not be CFL right? becase R1 is again a CFL.

enter image description here

$\endgroup$
  • $\begingroup$ CFL is not closed under intersections means intersecting two CFL languages does not have to be in CFL but it still can be (for example the intersection of a CFL language with it self) $\endgroup$ – narek Bojikian Jan 28 at 11:38
  • $\begingroup$ To understand this, I need to draw a product automata for a DFA and PDA? Can you please give some example? $\endgroup$ – Sivaranjani Duraisamy Jan 28 at 11:56
2
$\begingroup$

Every CFL language can be describes as a PDA. Every regular language can be described as a DFA.

The orthogonal product of a DFA and PDA can be defined as follows:

The new states of the automaton are all $(q_{PDA}, q_{DFA})$. That start state is $(s_{PDA}, s_{DFA})$ and the final states are all $(f_{PDA}, f_{DFA})$ where $f_{PDA}\in F_{PDA}$ and $f_{DFA} \in F_{DFA}$.

Given the transition of the PDA defined as $\delta_{PDA}(q_{PDA}, stack_{PDA}, a) = (q'_{PDA}, stack'_{PDA})$ and transition function of the DFA $\delta_{DFA}(q_{DFA})$

The transition function $\delta(q, a)$ for the new Automaton is where the transition function of the PDA is defined defined as $\delta((q_{PDA}, q_{DFA}), stack_{PDA}, a) = ((q'_{PDA}, \delta_{DFA}(q_{DFA})), stack'_{PDA})$

(in laymans terms, split out the states simulate the DFA and PDA independently and only accept the language when both are in a final state)

There is only 1 stack in this automaton. Thus it is a valid PDA. Therefor the language described by the intersection of a CFL and a regular language is a CFL.

The reason this does not hold for the intersection of 2 CFLs is because you need a second stack for second PDA.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I still could not understand how to construct a product automata for FA and PDA. Can you please give me a example with a diagram. Examples can be RL - c and CFL - a^nb^n. So, Σ* ∩ a^nb^n = a^nb^n - is a CFL. I have done the individual automatas and attached with the question. Please help me how to combine and proove that the final one is a CFL $\endgroup$ – Sivaranjani Duraisamy Jan 30 at 6:00
0
$\begingroup$

The sticking point is in the first statement:

CFL is not closed under intersection. That means, if we have L1,L2 of CFL then

L1 intersection L2 is not a CFL

This is not what non-closure means. What it actually means is that the intersection of two languages from a given set may not be in the given set, so in this case "CFL is not closed under intersection" means that given two context free languages, their intersection might not be a context free language.

For many context free languages however,their intersection is context free.

As you note, and as Ratchet Freak proves, the intersection of a context free language and regular language is context free.

We can make more complicated examples though:

Let $L_{1} = \{0^{n}1^{n}\#0^{m}1^{k} \mid n,m,k \in \mathbb{N}\}$ and $L_{2} = \{0^{n}1^{m}\#0^{k}1^{k} \mid n,m,k \in \mathbb{N}\}$, then $L_{1} \cap L_{2} = \{0^{n}1^{n}\#0^{m}1^{m}\}$, which is still context free, and both $L_{1}$ and $L_{2}$ are non-regular, so there's no extra restriction leading to the intersection being context free.

| cite | improve this answer | |
$\endgroup$

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.