# How to prove that this language is not regular?

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

• Hint: disjoint unions. Nov 5 '17 at 16:21

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

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.

• I may be missing something, but you seem to postulate the non-regularity of $L$, which is what you need to prove. The non-regularity of $M$ is obvious. Nov 5 '17 at 16:38
• @FabioSomenzi : From the OP: "How can I prove that this language is not regular?" So I do not postulate this. Further, the objection you raise is the specific reason the final paragraph, splitting $L$ into disjoint languages, is present. Nov 5 '17 at 17:11
• I see that, but that paragraph is not quite a proof. Note that you inadvertently changed the language ($a+b$ instead of $b+c$) and in so doing made the problem way more difficult than it is. If $A \cap B = \emptyset$, then $(A \cup B) \setminus B =$... Nov 5 '17 at 17:36
• @FabioSomenzi : D'oh! Good catch! Mentally shifted the symbols by one. Nov 5 '17 at 17:54
• The operation does exist, it is the intersection. And your answer is by far too complicated. Nov 5 '17 at 23:48