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

ignougroup
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 nin 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 landexists j∈[1,n] i_j not= j }$ $L_b’ = {ab^{i_1}ab^{i_2}ldots ab^{i_n} mid i_j∈mathbb N landforall j∈[1,n] i_j = j }$ (complement?) $L_b” = {ac^{i_1}ac^{i_2}ldots ac^{i_n} mid i_j∈mathbb N landforall 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^3dots 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

Leave a Reply