2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Perhaps there isn't any easy way using grammars? $\endgroup$ – Yuval Filmus Jun 9 '13 at 5:16
  • $\begingroup$ Well, it seems to be harder than the other two ways - but one can infer from its presence on the exam that it can be done, and that it can be done by a reasonably good undergraduate. $\endgroup$ – ajd Jun 9 '13 at 6:40
  • $\begingroup$ As the answers below show, this is in fact not the case. You can mimic your other answers in the grammar world using the known equivalence between grammars and PDAs, but you're not really thinking in terms of grammars but in terms of PDAs. $\endgroup$ – Yuval Filmus Jun 9 '13 at 15:48
  • $\begingroup$ @YuvalFilmus My answer below seems to confirm what you say, but in fact I do not agree. The CF grammar is a recursive process generating a string. The "added" regular part tries to find in parallel a path for the FSA. It does so recursively, "top-down" like a CFG behaves. The PDA proof also adds the FSA states, but the simulation is left to right, like the PDA behaves. So, although adding FSA states is similar, the constructions are straightforward for each of the two concepts, not a detour via the other formalism. $\endgroup$ – Hendrik Jan Jun 9 '13 at 20:26
  • 1
    $\begingroup$ You use the stack? How does that work; the original PDA might already use the stack! Usually, you will do finite counting in the states. $\endgroup$ – Raphael Jun 10 '13 at 10:35
2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\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.