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\}$.

  • $\begingroup$ What you provide is called a "language", not an "expression". Also "unregular" is a very uncommon term; usually one says "not regular" or "non-regular". $\endgroup$ – Peter Leupold Jan 24 at 12:15


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


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.