1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ This would be more appropriate at the Computer Science SE; see this question for reference. $\endgroup$ – DylanSp Mar 14 '16 at 16:16
  • 6
    $\begingroup$ @DylanSp: No, it would not; it’s a mathematical question, it’s perfectly fine here, and in fact we frequently answer questions of this type. $\endgroup$ – Brian M. Scott Mar 14 '16 at 16:18
  • $\begingroup$ The language is not regular, so you can use the pumping lemma for regular languages to prove it. It is context-free however, so you can't really apply the pumping lemma for context-free languages (you usually use pumping lemmas to disprove regularity, context-freeness etc.). I can post a proper answer explaining things more in-depth, unless someone else does it before me… $\endgroup$ – A.Sh Mar 14 '16 at 16:18
  • 1
    $\begingroup$ If you look in the right-hand sidebar, in the “Related” section, you will see a long list of links to other questions where people have asked how to prove that various languages are not regular using the pumping lemma. Perhaps some of those would be helpful. $\endgroup$ – MJD Mar 14 '16 at 16:24
  • 3
    $\begingroup$ Wikipedia is probably a better place than YouTube to look for references. $\endgroup$ – J.-E. Pin Mar 14 '16 at 16:45
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

It's shorter to use the Myhill-Nerode theorem:

For $i\ne j$, the strings $ba^ib$ and $ba^jb$ are distinguishable because $ba^ibc^i$ is in the language but $ba^jbc^i$ is not.

Because $\{ba^nb\mid n\in \mathbb N\}$ are infinitely many pairwise distinguishable prefixes, the language is not regular.

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