Proving that CFLs are closed under even-ness using grammars

Question

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.

Answer 1

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.

Answer 2

Actually you can shoot all three qestions with a single stone.

Since you can easily define a regular language $Even=\Sigma^{2n}$ for all even strings :

1. you prove the result by applying closure of CF languages under intersection with regular sets.

2. You use the standard construction of such an intersection based on CF grammar to get the grammar version of the proof.

3. You use the standard construction of such an intersection based on PDAs to get the PDA version of the proof.

You have to know at least one of the two constructions, since it is usually how the closure under regular set intersection is proved.

The purpose of the question is to check that you know the theorem, and at least one way to prove it.