Pumping Lemma - unregular expression

108 Views Asked by At

How do prove that this expression is unregular, I know firstly you have to try prove that it is regular and work from there. I also know that $w=xuz$ and the three rules are needed

Let $M$ be the language over the alphabet $\{a, b, c\}$ given by $M = \{a^ib^jc^k \mid i, j, k ≥ 0, j = i + k\}$.

1

There are 1 best solutions below

0
On BEST ANSWER

Hint:

Suppose $M$ is regular. Then by the Pumping Lemma, there is some $p$ so that all words of length at least $p$ can be decomposed as $xyz$ in such a way that $xy^nz\in M$ for all $n$.

Consider the word $ab^pc^{p-1}\in M$, and say that its Pumping Lemma decomposition is $xyz$. What are $x$, $y$, and $z$?

Prove that if $xy^nz\in M$ for all $n\in\mathbb{N}$, then necessarily a few properties must hold:

  1. $x$ must contain $a$ and cannot contain any $c$
  2. $z$ must contain all $p-1$ copies of $c$

This necessarily means that we have $x=ab^{m_x}$, $y=b^{m_y}$, and $z=b^{m_z}c^{p-1}$ for some $m_x,m_y,m_z\geq 0$ such that $m_x+m_y+m_z=p$ and $m_y\geq 1$. But then $$ xy^nz=ab^{m_x+nm_y+m_z}c^{p-1}=ab^{p+(n-1)m_y}c^{p-1}. $$ But, this word clearly cannot be in $M$, as $p+(n-1)m_y>1+(p-1)$ for all $n\geq 2$.