# For every $L_1$, $L_2$ regular, is $L=\{uv\ |\ u\ \text{is in}\ L_1, v\ \text{is in}\ L_2\ \text{and}\ |v| = 2|u|\}$ context free?

Is it true that for every 2 regular languages $$L_1$$, $$L_2$$ the language $$L=\{uv\ |\ u\ \text{is in}\ L_1, v\ \text{is in}\ L_2\ \text{and}\ |v| = 2|u|\}$$ is context free? I think that it isn't, because if $$L_1$$ & $$L_2$$ are regular then they are context-free and have grammars but I don't see construction that can limit the length of $$u$$ and $$v$$.

## 2 Answers

It is context-free, since we can build a (nondeterministic) PushDown Automaton for $$L$$ out of two NFA's for $$L_1$$ and $$L_2$$. Since PDA's have the same expressive power as context-free grammars, this means that $$L$$ is context-free.

The idea is that you add two (arbitrary) characters to the stack for every symbol in $$L_1$$ that you read, and then remove one character of the stack for every symbol in $$L_2$$ that you read. If at the end your stack is empty, you accept when you're in an accept state of $$L_2$$.

To be precise, you start with pushing a $$\#$$ into the stack, to mark the start. Then for the NFA for $$L_1$$, you convert every arrow with a character $$x$$ (that is not the empty character $$\varepsilon$$) between two states $$p$$ and $$q$$ as follows: $$\bigcirc_p\xrightarrow{x}\bigcirc_q\qquad\implies\qquad\bigcirc_p\xrightarrow{x,\ \/\varepsilon}\bigcirc_{pq}\xrightarrow{\varepsilon,\ \/\varepsilon}\bigcirc_q$$ Here the state $$pq$$ is new, and $$\$$ is any symbol (unequal to $$\#$$, of course). So we see each character $$x$$ that is being read will push two $$\$$ symbols into the stack.

Then between any accept state of the NFA for $$L_1$$, you draw an arrow $$\ \xrightarrow{\varepsilon,\ \varepsilon/\varepsilon}\$$ to the start state of the NFA for $$L_2$$.

The NFA for $$L_2$$ gets modified such that each arrow with a character $$x$$ (that is not the empty character) between two states $$p$$ and $$q$$ gets transformed to: $$\bigcirc_p\xrightarrow{x}\bigcirc_q\qquad\implies\qquad\bigcirc_p\xrightarrow{x,\ \varepsilon/\}\bigcirc_q$$ Hence this arrow will remove one $$\$$ from the stack with each character that is read.

(For both NFA's, any arrows with the empty character $$\varepsilon$$ will get transformed into an arrow $$\ \xrightarrow{\varepsilon,\ \varepsilon/\varepsilon}\$$, which of course still does nothing to the input or the stack.)

Finally put an arrow $$\ \xrightarrow{\varepsilon,\ \varepsilon/\#}\$$ from the accept states of the NFA for $$L_2$$ to a new state. This last state will be the (only) accept state of the PDA that you have built. The only way to reach it, is if there is a $$\#$$ in the stack after you have finished the whole string.

Yes!

Consider a left-regular grammar $$\mathscr G_1$$ for $$L_1 \setminus \{\epsilon\}$$ written without empty production rules. Such a grammar consists of production rules of forms $$\fbox{A \to x B}$$ and $$\fbox{A \to x}$$.

Similarly consider a right-regular grammar $$\mathscr G_2$$ for $$L_2 \setminus \{\epsilon\}$$, with rules of the forms $$\fbox{A \to B x}$$ and $$\fbox{A \to x}$$.

Let $$L'_2$$ be the language of all words in $$L_2 \setminus \{\epsilon\}$$ of even length.

We can write a grammar $$\mathscr G'_2$$ for $$L'_2$$ that introduces two terminals per rule:

• For all pairs of rules $$\fbox{A \to B x}$$ and $$\fbox{B \to C y}$$ in $$\mathscr G_2$$, write a new rule $$\fbox{A \to Cyx}$$.
• For all pairs of rules $$\fbox{A \to B x}$$ and $$\fbox{B \to y}$$ in $$\mathscr G_2$$, write a new rule $$\fbox{A \to yx}$$.

Now we can write a context-free grammar $$\mathscr G$$ for $$L$$:

• The nonterminals are $$\fbox{N_{AB}}$$, where $$A$$ is a nonterminal in $$\mathscr G_1$$ and $$B$$ is a nonterminal in $$\mathscr G'_2$$.
• The starting nonterminal is $$\fbox{N_{S_{L_1}S_{L_2}}}$$.

• For every pair of rules $$\fbox{A \to \color{red}xB} \in \mathscr G_1$$ and $$\fbox{C \to D\color{#0b0}y\color{#0b0}z} \in \mathscr G'_2$$, write a rule $$\fbox{N_{AC} \to \color{red}xN_{BD}\color{#0b0}y\color{#0b0}z}$$.

• For every pair of rules $$\fbox{A \to \color{red}x} \in \mathscr G_1$$ and $$\fbox{C \to \color{#0b0}y\color{#0b0}z} \in \mathscr G'_2$$, write a rule $$\fbox{N_{AC} \to \color{red}x\color{#0b0}y\color{#0b0}z}$$.
• If $$\epsilon \in L_1$$ and $$\epsilon \in L_2$$, write a rule $$\fbox{N_{S_{L_1}S_{L_2}} \to \epsilon}$$.

You can routinely verify this:

• If $$u \in L_1$$ and $$v \in L_2$$ and $$|v|=2|u|$$, then a chain of productions generating $$u$$ in $$\mathscr G_1$$ and a chain of productions generating $$v$$ in $$\mathscr G_2$$ are easily transformed into a chain of productions in $$\mathscr G$$ generating $$uv$$ in $$|u|$$ steps. (This proves $$L \subseteq \mathsf{Lang}(\mathscr G)$$.)

• Conversely, any chain of productions in $$\mathscr G$$ generating some string $$x$$ in $$L$$ can be “pulled apart” (by reading the nonterminal names) into chains of productions in $$\mathscr G_1$$ and $$\mathscr G_2$$ for the first third of $$x$$ and the last two-thirds of $$x$$, respectively. (This proves $$L \supseteq \mathsf{Lang}(\mathscr G)$$.)