1
$\begingroup$

I have the language

$ A_{1} \triangleq\left\{a w c^{l} d^{m}\mid l \in \mathbb{N} \wedge m \in \mathbb{N}^{+} \wedge w \in\{a, b\}^{*} \wedge |\left.w\right|_{a}=l+m\right\} \operatorname{with} \Sigma \triangleq\{a, b, c, d\} $

and I have no idea which word I should use to prevent a case distinction.

My first idea was to set $l = 0$ and $w=b^n$ so I would have the word $p=aa^nd^n$. The problem with that is, I have no idea how to proof this because this single "a" makes me crazy. Do you could help me?

$\endgroup$
  • $\begingroup$ Can you reveal how that single "a" makes you crazy in the question? $\endgroup$ – Apass.Jack Feb 21 at 23:14
  • $\begingroup$ @Apass.Jack Because i do not know how to work with this. With my idea i have ${a}^{n+1}$ so i can not pump. pls can you tell me how i could find a word? $\endgroup$ – Marie.L Feb 22 at 4:26
  • $\begingroup$ Do you want to prove it is not regular? to use a word that cannot be pumped? Then $aa^nd^n$ is such a word, assuming $n$ is a pumping length. (What do you mean by "prevent a case distinction"?) $\endgroup$ – Apass.Jack Feb 22 at 4:51
  • $\begingroup$ Yes I want to prove it is not regular. "What do you mean by "prevent a case distinction"?" If you have a language like this here $ A \triangleq\left\{(a b)^{n} c^{n} | n \in \mathbb{N}\right\} $. And you use the word $ w=(a b)^{n+1} c^{n+1} $ than you have to make a case distinction, because you can decompose the word into several species. For example be xyz a decomposition,then we have: 1: $ x=(a b)^{i}, y=(a b)^{j} $ and $ z=(a b)^{n+1-i-j} c^{n+1} $ 2: $ x=(a b)^{i}, y=(a b)^{j} a $ and $ z=b(a b)^{n-i-j} c^{n+1} $ 3: ... 4: ... And you have to prove the PL for every case. $\endgroup$ – Marie.L Feb 23 at 9:38
  • $\begingroup$ @Apass.Jack Do you unterstand what I mean? $\endgroup$ – Marie.L Feb 23 at 15:20
1
$\begingroup$

If we want to use the usual pumping lemma for regular languages as introduced in most textbooks to prove a given language is not regular, the way to avoid or reduce case distinction in showing a word cannot be pumped is to

  • select that word so that its front part is in a very restricted form and at least at long as the pumping length.
  • combine all cases into very few or only one case conceptually.

Let me take the language in the question as an example.

To show $A_{1} \triangleq\left\{a w c^{l} d^{m}\mid l \in \mathbb{N} \wedge m \in \mathbb{N}^{+} \wedge w \in\{a, b\}^{*} \wedge |\left.w\right|_{a}=l+m\right\}$ is not regular, let us suppose our adversary Adriana claims $A$ is regular with pumping length $p$. In order to beat Adriana, we select word $w=aa^pd^p\in A_1$. Adriana claims that $w=xyz$ for some $x,y,z$ such that $|xy|\le p$, $|y|\ge1$ and for all $n\ge0$, $xy^nz\in A$.

It looks like we have to make a case distinction, because Adriana could decompose the word in many ways. For example, Adriana could have any one of the following decompositions.

  1. $ x=\epsilon, y=a^{j}$ and $ z=a^{p+1-j} d^{p}.$
  2. $ x=a, y=a^{j}$ and $ z=d^{p-j} d^{p}.$
  3. $x=aa^i, y=a^{j}$ and $ z=d^{p-i-j} d^{p}.$
  4. $\cdots$.

We have to prove Adriana is wrong in every possible case. There is no way around that, as Adrianna is free to choose any one of them.

However, a little dose of abstraction and intelligence will enable us to treat all cases simultaneously.

Since $|xy|\le p$ and all $p$ letters at the front of $w$ are $a$'s, $y$ must contain $a$ only. Suppose $y=a^i$ for some $i>0$. Then $xz=xy^0z$ contains less number of $a$'s than $w$ but the same number of $c$ and $d$ as $w$. That means $xz\not=A_1$. We beat Adriana as if she has only one case.

Hopefully this strategy answers your question. Indeed, it should be applicable to almost all similar problems in the course of your study where you want to prove a language is not regular.


Here are a few exercises about the languages you have encountered.

Exercise 1. Prove the language $C \triangleq\left\{a^{m} b^{n} c d^{n} d^{m} \mid n, m \in \mathbb{N} \wedge m \leq 3\right\}$ is not regular "without case distinction".

Exercise 2. Prove the language $B \triangleq\left\{w \in \Sigma^{*} \mid |\left.w\right|_{b} \neq|w|_{c} \right\}$ is not regular "without case distinction".

Exercise 3. Prove the language $A \triangleq\left\{(a b)^{n} c^{n} | n \in \mathbb{N}\right\}$ is not regular using two combined cases.

$\endgroup$

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.