0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Hint: disjoint unions. $\endgroup$ Nov 5 '17 at 16:21
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$ Nov 5 '17 at 16:38
  • $\begingroup$ @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. $\endgroup$ Nov 5 '17 at 17:11
  • $\begingroup$ 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 = $... $\endgroup$ Nov 5 '17 at 17:36
  • $\begingroup$ @FabioSomenzi : D'oh! Good catch! Mentally shifted the symbols by one. $\endgroup$ Nov 5 '17 at 17:54
  • $\begingroup$ The operation does exist, it is the intersection. And your answer is by far too complicated. $\endgroup$
    – J.-E. Pin
    Nov 5 '17 at 23:48

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.