[Solved]: Proving that CFLs are closed under even-ness using grammars

Problem Detail: 

This is a question from a 2007 exam paper for a course I'm studying, question 2 on page 2.

Theorem: Let $L$ be a context-free language. Let $L_{even}$ be the subset of $L$ consisting of all the strings in $L$ that have even length. Then $L_{even}$ is context-free.

The question is to prove this theorem using two of three different methods: using grammars, PDAs, or a theorem about language intersections.

I can very easily find a proof using PDAs (maintain your current odd/even status using the stack), and intersections (intersect with $\Sigma^*_{even}$, which is regular) - but I can't think of how to do it using properties of grammars. I suspect either Chomsky or Greibach Normal Forms comes in handy here but I'm not sure how.

Asked By : ajd

Answered By : Hendrik Jan

The proof using grammars basically mimics the proof using automata. It is not very complicated, using a trick with derivation trees that have a computation of the finite state automaton on the leaves of the derivation tree, which is (bottom up) taken to the root.

Start with a grammar $G$ in Chomsky normal form. The grammar for the intersection (of a CFL $L(G)$ and a regular language $L({\cal A})$) has nonterminals $A_{pq}$ where $A$ is a nonterminal of $G$ and $p,q$ are states of $\cal A$. It means the set of all strings derived from $A$ in $G$ while having a path from $p$ to $q$ in $\cal A$.

Then the productions are

• $S\to S_{if}$ where $S$ is the axiom in $G$ and $i$ and $f$ are initial and final states in $\cal A$.

• $A_{pq} \to B_{pr}C_{rq}$ if $A\to BC$ in $G$, and $p,q,r$ states in $\cal A$

• $A_{pq} \to a$ if $A\to a$ in $G$ and transition $(p,a,q)$ for $\cal A$.

(added) That is the general construction for the intersection of context-free and regular languages. In your specific example the regular restriction is on the length of the strings. Now we need only two copies $A_e, A_o$ of each nonterminal $A$, denoting the parity of the length of the strings generated.

• axiom $S_e$
• $A_e \to B_eC_e \mid B_oC_o$, $A_o \to B_eC_o \mid B_oC_e$, for $A \to BC$ in $G$
• $A_o\to a$ for $A\to a$ in $G$.

That qualifies as a "push-down free" proof? Definitely no knowledge about the PDA-CFG equivalence is used.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12554

3.2K people like this

 Download Related Notes/Documents