2

Let $\mathcal L$ be a language. Denote by $\mathcal L_{\text{even}}$ the language consisting of all words in $\mathcal L$ whose length is even.

Prove that if $\mathcal L$ is context-free over the alphabet $\{0,1\}$ then $\mathcal L_{\text{even}}$ is also context-free.

Here is my idea:

All the words that belong to $\mathcal L_{\text{even}}$ are joined from words in $\mathcal L$, e.g. given the word $\color{green}{011}\in \mathcal L$ and the word $\color{blue}{10100}\in \mathcal L$, we can join them: $\color{green}{011}\color{blue}{10100}\in \mathcal L_{\text{even}}$.

I think that since the context-free languages are closed under junction, it follows that $\mathcal L_{\text{even}}$ is context-free, and that's it.

But it looks too simple so I'm suspicious.

Yuval Filmus
  • 57,157
  • how do you define your language ? once your proved that a context-free language can always be defined by a push-down automata, it is easy to add at its end a (finite state) automata checking if the word has an even length, but I'm not sure that converting a grammar for $L$ to a grammar for $L_{even}$ would be so easy – reuns Jan 23 '16 at 21:09
  • in fact, I'm thinking that converting a grammar for $L$ to a grammar for $L_{even}$ wouldn't be so difficult, just replace any non terminal $A$ by $A_{even},A_{odd}$ and for example the rule $A \to B x C A$ will be replaced by $A_{even} \to B_{even} x C_{even} A_{odd} | A_{even} \to B_{odd} x C_{even} A_{even} | \ldots$ – reuns Jan 23 '16 at 21:19

2 Answers2

2

You are misinterpreting the definition of $\mathcal{L}_\mathrm{even}$: it consists of those words in $\mathcal{L}$ which have even length. For example, if $\mathcal{L} = \{ a^n b^n, a^n b^{n+1} : n \geq 0 \}$ then $\mathcal{L}_\mathrm{even} = \{ a^n b^n : n \geq 0 \}$.

For the proof, use the fact that the context-free languages are closed under intersection with regular languages.

Yuval Filmus
  • 57,157
  • and how would you prove that ? with PDA ? – reuns Jan 23 '16 at 21:11
  • @user1952009 This is a standard fact. One possible proof is through PDAs. Check your textbook. – Yuval Filmus Jan 23 '16 at 21:13
  • @NehoraiRaphael $\mathcal{L}_\mathrm{odd}$ is not necessarily regular, indeed it is not regular in my example. – Yuval Filmus Jan 23 '16 at 21:13
  • @NehoraiRaphael Yes, $\mathcal{L}_\mathrm{odd} = {a^nb^{n+1} : n \geq 0}$ is not regular. – Yuval Filmus Jan 23 '16 at 21:16
  • @NehoraiRaphael No, it doesn't. Now spend a few hours on it before writing back. (No need to write back if all is understood!) – Yuval Filmus Jan 23 '16 at 21:19
  • @Yuval Filmus : do you think the algorithm I use above to generate a grammar for $L_{even}$ would work for the intersection with any regular language ? – reuns Jan 23 '16 at 21:23
  • @NehoraiRaphael No, it's not. It's actually the prototypical non-regular language. – Yuval Filmus Jan 23 '16 at 21:23
  • @user1952009 There's only one way to know. Come up with the construction and prove that it works. Or check the literature for proofs that take this route. – Yuval Filmus Jan 23 '16 at 21:24
  • @YuvalFilmus I don't want to bother you but what about this expression $\big((0+1)(0+1)\big)^*$? –  Jan 23 '16 at 21:26
  • @NehoraiRaphael Well, it doesn't work. I can explain exactly why, but I believe you can work it out yourself. I strongly suggest you spend a few hours reflecting on this matter on your own. – Yuval Filmus Jan 23 '16 at 21:27
  • @NehoraiRaphael Your expression does define the set of even-length strings, which is however different (in general) from $\mathcal{L}_\mathrm{even}$, which is the set of even-length strings in $\mathcal{L}$. – Yuval Filmus Jan 23 '16 at 21:28
  • I can prove "with the hands" that there is a simple algorithm to generate the grammar for $L \cap R$ working with any regular language $R$ : regular language means finite state automata, i.e. the current state can be described by a integer $ < N$ where $N$ is the number of state of the automata, thus replacing in the grammar for $L$ any non terminal $A$ by $A_1,\ldots,A_N$ and adapting the rules accordingly will yield a grammar for $L \cap R$. – reuns Jan 23 '16 at 21:31
0

After using @YuvalFilmus's hint

Let's denote $\mathcal L'$ to be the language of all the even words above the alphabe $\{0,1\}$.

$\mathcal L'$ is regular because we can write a regular expression for it: $\big((0+1)(0+1)\big)^*$, we can see that $\mathcal L_{\text{even}}=\mathcal L \cap \mathcal L'$ since the context-free languages are closed under intersection with regular languages so $\mathcal L_{\text{even}}$ is context free $\square$