1
$\begingroup$

$L=a^*b^*c^* \setminus \{a^n b^n c^n \mid n \geq 0\}$ can be proved as context-free by partitioning it as $L = \{a^nb^mc^* \mid n \neq m\} \cup \{a^*b^nc^m \mid n \neq m\}$ and further dividing each $\neq$ into smaller and larger. You will have four sets. You can give CFG's for each. Then since CFGs are closed under union, you have your proof.

Now how can I go around proving that $L$ is not regular? If you prove that the each of these four sets are not regular, you still can not prove that the union is not regular, can you?

$\endgroup$
3
$\begingroup$

Lets assume towards contradiction that L is regular. Then, by closure properties, we have $\bar L$ is regular, and thus also $\bar L \bigcap (a^*b^*c^*)$ is regular. But calculating it, we find out $\bar L \bigcap (a^*b^*c^*)=\{a^nb^nc^n\}$ is not regular.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Suppose that $L$ is regular. Take the complement of $L$ and intersect it with $a^*b^*c^*$. You are left with $M = \{a^n b^n c^n \mid n \ge 0\}$. Due to the closure properties of regular languages, $M$ is also regular.

Let $n_0$ be the pumping length of $M$. By the pumping lemma there is some $x \in \{1, \dots, n_0\}$ such that all words $a^{(n_0-x)+ix} b^{n_0} c^{n_0}$ for $i \ge 0$ belong to $M$.

Pick $i=0$ to obtain $a^{n_0 - x} b^{n_0} c^{n_0} \in M$, a contradiction.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Suppose that $L$ is regular, and let $p$ be the pumping lemma constant. Let $w = a^p b^{p+p!} c^{p+p!} \in L$. By the pumping lemma, we can write $w = xyz$ so that $|xy| \leq p$, $y \neq \epsilon$, and $xy^iz \in L$ for all $i \geq 0$. Since $|xy| \leq p$, the subword $y$ is composed entirely of $a$'s, say $y = a^t$, where $t \neq 0$. Then $xy^{1+n!/t}z = a^{p+p!} b^{p+p!} c^{p+p!} \notin L$, contradicting the pumping lemma.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ While proving irregularity, finding just one $w$ that can not be pumped is enough, right? E.g. we can write some other $w$ using the $p$, like $w=a^{p+1}b^pc^p$ that can be pumped, but that does not change the fact $L$ is irregular. $\endgroup$ – Zargo May 31 at 8:56
  • $\begingroup$ The pumping lemma states that if $L$ is regular then there exists $p$ such that for each word $w \in L$ of length at least $p$ there exists a decomposition $w = xyz$ satisfying certain conditions. If for each $p$ you find a word $w \in L$ of length at least $p$ which cannot be decomposed in a way that specifies all the conditions, then you show that the conclusions of the pumping lemma do not hold. Therefore the premise of the lemma must fail, that is, $L$ cannot be regular. $\endgroup$ – Yuval Filmus May 31 at 10:06

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.