# How to create all even length words from a given CNF grammar

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?

• – D.W.
May 31, 2022 at 2:05

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.

• Thanks! So how can I formally define L(G5) with {V5, Σ5, R5, S5} using {V1, Σ1, R1, S1}?
– Eran
May 31, 2022 at 21:10
• 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$. Jun 1, 2022 at 15:20
• Can you please write down the full new formal grammar? I have tried to do it but i got stuck
– Eran
Jun 11, 2022 at 11:27
• 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$. Jun 11, 2022 at 12:34
• how can I define the new axiom?
– Eran
Jun 11, 2022 at 15:02