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?)

  • $\begingroup$ What do you want to transform them into? $\endgroup$ – jmad May 20 '12 at 14:33
  • 2
    $\begingroup$ Please take a little effort to formulate your question more clearly. $\endgroup$ – Dave Clarke May 20 '12 at 14:39
  • $\begingroup$ I edited so that it easier to read. But I still don't get it. Do you want to prove they are not regular by saying they can be reduced to $L$ which is not? $\endgroup$ – jmad May 20 '12 at 15:10
  • $\begingroup$ This looks like you are dumping your work on us without more effort than copying some assignment. Please give us some more. $\endgroup$ – Raphael May 20 '12 at 15:10
  • 3
    $\begingroup$ Try to be more formal; when you write "union" write the languages which are joined, when you write "homomorphism" define the homomorphism etc. $\endgroup$ – sdcvvc May 20 '12 at 16:49

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


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


Hint: for $L_a$ you can use stability with intersection from $L_a'''$.

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

    $L_a \cup d^* = L_a'$

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

    $L_a' \cap a^*cw = L_a''$

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

    homomorphism $ h(d) = \epsilon, h(c) = \epsilon, h(a) = a, h(b) = b $

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

    $L_a''' = L := \{ a^nb^n \mid n\in \mathbb N \}$ is the same but other syntax?

  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 \}$

    $\overline L_b = L_b'$ so follows $\forall j∈[1,n] \ i_j = 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?)

    homomorphism $ h(b) = c, h(a) = a $ i say b is know my new c - is my idea of thislanguage correct? - $ab abb abbb ... ab^n$ ? O.o

    $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 \}$

    $L_b'' \cap a^*b^*$ and than homorphism $h(a) = a, h(b)=b, h(c) = \epsilon \\\ $ first we have $a \epsilon ^{i_1}a \epsilon ^{i_2}\ldots a \epsilon ^{i_n}$ and than $a^*b^*$. Can anyone give me a hint for the transformation to $a^nb^n$?

  • 1
    $\begingroup$ let us continue this discussion in chat $\endgroup$ – Raphael May 23 '12 at 20:42
  • $\begingroup$ Note that $L_b'$ is not the complement of $L_b$! For instance, $b \notin L_b$ but $b \notin L_b'$, either. $\endgroup$ – Raphael May 24 '12 at 21:51

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.