[Solved]: Use closure properties to transform languages to $L := \{ a^nb^n : n\in \mathbb N \}$

Problem Detail: 

For the purpose of proving that they are not regular, what closure properties can I use to transform the languages

1. $L_a = \{ a^*cw \mid w \in \{a,b \}^* \land |w|_a = |w|_b \}$ and
2. $L_b = \{ab^{i_1}ab^{i_2}\ldots ab^{i_n} \mid i_j∈\mathbb N \land \exists j∈[1,n] \ i_j \not= j \}$

to $L := \{ a^nb^n \mid n\in \mathbb N \}$, respectively?

I tried:

1. $L_a = \{ a^*cw \mid w \in \{a,b \}^* \land |w|_a = |w|_b \}$

   $L_a' = \{ \{a,d\}^*cw \mid w \in \{a,b,d \}^* \land |w|_a + |w|_d = |w|_b \}$ (union?)

   $L_a'' = \{ d^*cw \mid w \in \{a,b \}^* \land |w|_a = |w|_b \}$ (concatenation?)

   $L_a''' = \{ w \mid w \in \{a,b \}^* \land |w|_a = |w|_b \}$ (homomorphism?)

2. $L_b = \{ab^{i_1}ab^{i_2}\ldots ab^{i_n} \mid i_j∈\mathbb N \land\exists j∈[1,n] \ i_j \not= j \}$

   $L_b' = \{ab^{i_1}ab^{i_2}\ldots ab^{i_n} \mid i_j∈\mathbb N \land\forall j∈[1,n] \ i_j = j \}$ (complement?)

   $L_b'' = \{ac^{i_1}ac^{i_2}\ldots ac^{i_n} \mid i_j∈\mathbb N \land\forall j∈[1,n] \ i_j = j \}$ (homomorphism?)

Asked By : corium

Answered By : Raphael

Regular languages are closed under intersection. This often allows to cut away all parts of a language that are not needed to show non-regularity. Complementation serves a similar purpose: if the original language is "complicated", the complement may be simpler so work with (in terms of other closure properties).

Hints:

For $L_a$, the part right of $c$ is sufficient; try to intersect with a regular expression that gets rid of the clutter. Note that the part right of $c$ is close to $L$. Maybe another regular expression can help?
For $L_b$, note that we get $n$ times $a$ and $b$ (in the last block), respectively, if we replace $\exists \dots i_j \neq j$ with $\forall \dots i_j=j$.

Complete solution for $L_a$:

Let $L_a' := L_a \cap \mathcal{L}(ca^*b^*) = \{ ca^nb^n \mid n \in \mathbb{N} \}$. Then, with homomorphism $\phi : \{a,b,c\} \to \{a,b\}^*$ defined by

$\qquad \displaystyle \phi(w) = \begin{cases} \varepsilon &, w = c \\ w &, \text{ else} \end{cases}$

we have $\phi(L_a') = L$.

Complete solution for $L_b$:

In order to get rid of the pesky $\exists$, we can complement. That introduces lots of words we do not want, i.e. such that don't have the $(ab^*)^*$ structure, so we can intersect with exactly that regular expression to get structure back:

$\qquad \displaystyle L_b' := \overline{L_b} \cap \mathcal{L}((ab^*)^*) = \{ abab^2ab^3\dots ab^n \mid n \in \mathbb{N} \}$.

Note that words in $L_b'$ contain exactly $n$ times the symbol $a$; if we can get rid of all blocks of $b$ but the last, we have $L$. This is possible by (nondeterministic) finite state transduction which $\mathsf{REG}$ is closed under. The transducer removes all $b$ until it decides on an $a$ that is was the last one. After that it emits the input and accepts if no further $a$ is encountered.

Note that if we reverse $L_b'$, we can cut away the excess $b$ with a deterministic transducer and reverse again to obtain $L$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1949

 Ask a Question

 Download Related Notes/Documents