given CFG G1 = {V1, Σ1, R1, S1} in its CNF form,

I have to define a new G5 grammar that constructs L(G5) using {V1, Σ1, R1, S1}:

while L(G5) = { x ∈ L(G1) | |x| is even }

i . e .

L(G5) composed of all even length words in L(G1)

How can I do it?


1 Answer 1


This is a specific application of the fact that context-free languages are closed under under intersection with a regular languages. The usual proof is to use the fact that we can find a pushdown automaton and a finite state automaton, and then for the intersection simulate the pair in parallel. This is called the product construction.

Here there is a simple solution directly on the context-free grammar. For each nonterminal $A$ introduce two copies $A_e$ and $A_o$ that together derive the same set of strings, but separated into even length and odd length respectively. The productions must be annotated with odd and even accordingly.

  • $\begingroup$ Thanks! So how can I formally define L(G5) with {V5, Σ5, R5, S5} using {V1, Σ1, R1, S1}? $\endgroup$
    – Eran
    May 31, 2022 at 21:10
  • $\begingroup$ The new set of nonterminals is of the form $\{ X_e, X_o \mid X\in V\}$. The productions have to be changed from $A\to BC$ into $A_x\to B_yC_z$ for a sensible choice of $x,y,z$. $\endgroup$ Jun 1, 2022 at 15:20
  • $\begingroup$ Can you please write down the full new formal grammar? I have tried to do it but i got stuck $\endgroup$
    – Eran
    Jun 11, 2022 at 11:27
  • $\begingroup$ Change $A\to a$ into $A_o\to a$. Change $A\to BC$ into $A_e\to B_eC_e$ and $A_e\to B_oC_o$ and similar for $A_o$. New axiom $S_e$. $\endgroup$ Jun 11, 2022 at 12:34
  • $\begingroup$ how can I define the new axiom? $\endgroup$
    – Eran
    Jun 11, 2022 at 15:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.