1
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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