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?

Question

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

Answer 1

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.

Answer 2

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