How to prove that this language is not regular?

858 Views Asked by At

$$L = \{ab^nc^n, n \geq 0\} \ \cup \ \{a^kw, k \neq 1, w = (b+c)^*\}$$

How can I prove that this language is not regular? I tried using the pumping lemma, but it doesn't seems to work. Is there another way to prove this?

My idea is to perform an operation on $L$ and another language which will result in a language that we know it's not regular and since the operation is closed on regular languages, we can prove $L$ is not regular. Any idea what operation I can use?

2

There are 2 best solutions below

5
On

First, try to get an idea what makes this language not regular. It's given as the union of two languages. If both of those are regular, we would have a regular language, so if $L$ is not regular, at least one of these two languages is not regular. Let \begin{align*} M &= \{ a b^n c^n : n \geq 0 \} \\ N &= \{ a^k w : k \neq 1, w \in (a+b)^* \} \end{align*}

Any regular language is accepted by a deterministic finite automaton (DFA). It is easy to write down a DFA to accept $N$. From the start state, input of $a$ leads to a state with only one subsequent transition, to an accepting state that consumes as many $a$s as continue to be input, then on a $b$ transitions to a third state. Alternatively, from the start state, input of $b$ leads to the third state. The third state is accepting and transitions to itself on any input of $a$ or $b$. (If your DFA formalism requires explicit transitions to non-accepting states, it should be clear that only the "one $a$ in, second $a$ out" state has a non-accepting input.) So $N$ is a regular language.

So $M$ must not be regular. In fact, it is not. There is no way a regular expression or a DFA can memorize the (potentially arbitrarily large) number, $n$, of $b$s to then ensure there follow $n$ $c$s.

One could also organize $L$ (into a disjoint union) by the number of leading $a$s: $$ L = (b+c)^* | a b^n c^n | a^2(b+c)^* $$ which helps us realize there is no way $N$ can fill in $M$ enough to make their union regular. The straightforward (non-minimal) DFA for the language presented this way starts with a Start-$a$-$a$ chain to pick which of the three alternatives could apply to a given input. It is evident tha the first and third alternatives are given by regular expressions, so the difficulties must be in the second alternative.

0
On

Hint. Take the intersection of $L$ with $ab^*c^*$.