# Decide if a formal language is a Context-free language

Let $L_1$ be a regular language.

Let $L_2$ be a Context-free language.

Let $L = \{w \in L_1 \mid w = \alpha_1\phi_1\alpha_2\phi_2\ldots\alpha_n\phi_n : \alpha_1\alpha_2\ldots\alpha_n\in L_2$ ; $\forall_i:\alpha_i,\phi_i\in\sum\}$

$\sum = \{a,b\}$

Is $L$ a Context-free language?

How do I prove it using closure properties only?

-
possible duplicate of Showing a language is context-free with closures –  user18119 Dec 30 '12 at 22:10
@QiL: This is not the same question. That one asked about the fair shuffle of a regular and a context-free language; this one asks about the subset of a regular language obtained by shuffling $\{a,b\}^*$ with a context-free language. –  Brian M. Scott Dec 30 '12 at 22:18
@BrianM.Scott: sorry I didn't look at (and didn't understand) the subtle differences. And I don't know how to cancel my vote :(. –  user18119 Dec 30 '12 at 22:23

As this is homework, I have been not too detailed. Nevertheless, the arguments are complete.

In fact the language is context-free. I do not understand your $\log$-example.

(added) $\newcommand{\u}[1]{\underline{#1}}$ By definition $L$ consists of those strings $w$ in $L_1$ such that the length of $w$ is even and when taking the odd letters from $w$ we obtain a string from $L_2$. A lovely nonstandard operation. So, if $w=\u aa\u ab\u bb\u bb\in L_1$ and $L_2=\{a^nb^n \mid n\ge 1\}$ then $w\in L$ as the odd letters spell out $aabb\in L_2$. Rather than deleting letters form words in $L_1$ we will add letters after every letter of a string in $L_2$ and check whether the result is from $L_1$. A morphism can delete letters, so an inverse morphism can insert those. We need however to ensure we only insert after every existing letter.

We start by defining an alternative alphabet next to $\Sigma=\{a,b\}$ to temporarily distinguish letters from $L_2$ and the inserted letters: $\Delta=\{c,d\}$.

For $u\in \{a,b,c,d\}^*$ we can check whether the $\Sigma$-part is in $L_2$ by applying the morphism $h$ that deletes $c$ and $d$ (and keeps $a$ and $b$). Thus the set of all strings in $L_2$ with $c$'s and $d$'s added at random positions is exactly the language $h^{-1}(L_2)$, obtained as an inverse morphism.

In the example we get, e.g., from $aabb$ both $\u ac\u ad\u bd\u bd$ (with insertions at proper positions) and $cc\u a\u ad\u bcd\u bd$ (insertions that are not to be kept).

We find strings that after inserting have letters in $\Sigma$ and $\Delta$ alternatingly (as desired) by intersecting with the simple regular language $R = (\Sigma\Delta)^*$.

We find all strings in $L_2$ with letters $a$ and $b$ inserted at even positions by then mapping $c$ and $d$ back to $a$ and $b$ using another morphism $g$.

We find $L$ by intersecting regular $L_1$ with the language we just have constructed from context-free $L_2$ using (inverse) morphisms and intersection with a regular language, to be precise $L = L_1 \cap g( h^{-1}(L_2) \cap R)$.

Note. If you know that context-free languages are in fact closed under finite state transductions (finite state automata with output) then the argumentation can be formulated in a more intuitive way. In fact closure under the three operations (inverse) morphisms and intersection with regular languages is equivalent with closure under finite state transductions.

(I also have flagged this question as duplicate ... but as Brian notes, I was wrong. Sorry moderator.)

-
Isn't it enough to show that $L=h^{-1}(L_2)$ ? So $L$ is closed under inverse homomorphism? Why is the second part needed? Please be a bit more specific I am having bad time over here :) –  Yoni Hassin Dec 31 '12 at 5:20
Well $L=L_1\cap h^{-1}(L_2)$ is close. However $h^{-1}$ inserts $c,d$ which are not part of $L_1$. –  Hendrik Jan Dec 31 '12 at 9:58
Nice argument. $~$ –  Brian M. Scott Dec 31 '12 at 15:26
@BrianM.Scott Thanks, I will consider this comment as another badge earned. In fact the construction is an ad-hoc implementation of [Nivat's Theorem] (en.wikipedia.org/wiki/…) for finite state transducers –  Hendrik Jan Dec 31 '12 at 17:11