2
$\begingroup$

Is the language $L = \{\omega : \omega\text{ contains exactly one 'foobar'}\}$ regular? I have a hunch that it is non-regular because a regular expression representing the language must remember that is has encountered the substring 'foobar.'

However, I can't seem to use the pumping lemma to prove that it is indeed not regular. Say $s \in L$ and $s$ is of the form

[substring not containing 'foobar']foobar[substring not containing 'foobar']. 

Then, $L$ is pumpable because $s = xyz \in L$ for $|s| > p$, where $y$ can be a substring within either section labeled [substring not containing 'foobar']. If we repeat $y$ $j$ times, $xy^jz$ will still be in $L$.

However, again, $L$ doesn't seem regular to me... why is my pumping lemma proof erring?

  • 0
    @Arthur Yes, saying "...it never has to count higher than 2" is crucial, which is why I said that.2012-09-29

2 Answers 2

3

Hint: It is regular. So one cannot expect the Pumping Lemma to yield anything.

3

Just for fun, here’s a regular grammar that generates the language in question. The $S$ and $A_k$ productions generate the first part of the string, the $B$ productions generate the foobar, and the $R$ and $C_k$ productions generate the last part of the string.

Let $\bar f$ represent any terminal character other than $f$, $\bar o$ any terminal character other than $o$, and so on, and let $x$ represent any terminal character.

$\begin{align*} &S\to fA_1\mid \bar fS\mid fB_2\mid B_1\\ &A_1\to oA_2\mid\bar oS\\ &A_2\to oA_3\mid\bar oS\\ &A_3\to bA_4\mid\bar bS\\ &A_4\to aA_5\mid\bar aS\\ &A_5\to\bar rS\\ &B_1\to fB_2\\ &B_2\to oB_3\\ &B_3\to oB_4\\ &B_4\to bB_5\\ &B_5\to aB_6\\ &B_6\to rR\mid r\\ &R\to fC_1\mid\bar fR\mid x\\ &C_1\to oC_2\mid\bar oR\mid x\\ &C_2\to oC_3\mid\bar oR\mid x\\ &C_3\to bC_4\mid\bar bR\mid x\\ &C_4\to aC_5\mid\bar aR\mid x\\ &C_5\to \bar rR\mid\bar r \end{align*}$