Formal Languages – Using Pumping Lemma to Prove Non-Regular Language

Question

I'm currently stuck on a problem were I'm asked to look at a language and prove whether or not it is a regular language or something else such as context-free.

I've been given the example:

$$\{ba^n bc^n \mid n ≥ 1\}$$

From this, I can see that it is in face not a regular language due to the multiple repetition of segments but I need to use a proof to actually prove.

I'm under the impression I need to use the pumping lemma to solve but unfortunately after searching on Youtube for help i'm still finding it hard to grasp.

I would appreciate if someone could talk me through step by step on how to use pumping lemma to show that this is a context free language (if it is).

Thanks in advance

Answer 1

I’ll walk you through the argument.

Suppose that $L=\{ba^nbc^n:n\ge 1\}$ is regular. Then the pumping lemma for regular languages says that it has a pumping length $p$ such that if $w$ is any word of $L$ whose length is at least $p$ (i.e., such that $|w|\ge p$), then $w$ can be decomposed as $w=xyz$ in such a way that $|xy|\le p$, $|y|\ge 1$, and $xy^kz\in L$ for every $k\ge 0$. In order to use the pumping lemma to show that $L$ is not in fact regular, we must find a word $w$ for which this yields some contradiction. Finding such a $w$ is largely a matter of practice and experience with similar problems.

Here we can take $w=ba^pbc^p$. No matter how we split this as $w=xyz$, if $|xy|\le p$, then the $xy$ part is some initial segment of the first $p$ letters of $w$, i.e., of $ba^{p-1}$. There are now two possibilities that have to be distinguished.

• If $|x|\ge 1$, then the initial $b$ of $w$ is part of $x$, and $y=a^r$ for some $r$ such that $1\le r\le p-1$.

If this is the case, then $x=ba^s$ for some $s\ge 0$ such that $r+s\le p-1$, and $z=a^{p-r-s}bc^p$; why? Then for any $k\ge 0$ we have

$$xy^kz=ba^sa^{kr}a^{p-r-s}c^p=ba^{p-r+(k-1)r}bc^p\;.$$

You can easily check that this is in $L$ if and only if $k=1$. If $k=0$, the block of $a$s is shorter than the block of $c$s, and if $k>1$, the block of $a$s is longer than the block of $c$s; in both cases the word is not in $L$.

• If $x$ is empty, then $y=ba^r$ for some $r\le p-1$.

In this case $z=a^{p-r}bc^p$, and

$$xy^2z=y^2z=ba^rba^pbc^p\;,$$

which is plainly not in $L$. This is sufficient, but we can go further and note that in fact $xy^kz\in L$ if and only if $k=1$, so that we just have the original $w$: $xy^kz$ has $k+1$ $b$s, while every member of $L$ has exactly two $b$s.