1
$\begingroup$

I want to prove that $\{A^iB^jC^k \mid i=j \text{ or } j=k\}$ is a not a regular language using the pumping lemma.

I've found that the only way to obtain a contradiction is when $x \in A^*$, $y \in B^*$, $z \in C^*$, as $y$ is unable to be pumped up and still fit in the language. However if I have any combination of $y \in B^*C^*$ or $y \in A^*B^*$ and either $x$ or $z$ is empty, it appears as if $y$ can be pumped and thus this would be a regular language. The only way I can think that this would violate the rules of pumping lemma is if $|xy| ≤ P$. Assuming that $P$ is $2$ (which may be completely wrong), then the above still wouldn't violate the pumping lemma and thus this would be a regular language, right?

$\endgroup$
  • $\begingroup$ I cannot make heads or tails of your question. $\endgroup$ – Yuval Filmus Feb 7 at 3:56
1
$\begingroup$

Let's start with stating the pumping lemma, in its contrapositive form:

Suppose that $L$ is a language such that for all $p>0$, the following holds. There exists a word $w \in L$ of length at least $p$ such that for every decomposition $w=xyz$ in which $|xy| \leq p$ and $y \neq \epsilon$, there exists $t \geq 0$ such that $xy^tz \notin L$. Then $L$ is not regular.

Now let us prove that your language is not regular. Given $p > 0$, let $w = a^pb^p \in L$, which certainly has length at least $p$. Given a decomposition $w = xyz$ with $|xy| \leq p$ and $y \neq \epsilon$, we see that $y = a^i$ for some $i \neq 0$. Therefore $xy^0z = a^{p-i}b^p \notin L$. Hence the pumping lemma applies, and shows that $L$ is not regular.

| cite | improve this answer | |
$\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.