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?

  • 1
    $L$ is in fact regular; it's probably easier to see this by finding a finite-state machine that accepts $L$ than a regular expression.2012-09-29
  • 1
    It's regular because the FSM can count the number of `foobar` that it sees, and it never has to count higher than 2 to know the answer.2012-09-29
  • 0
    @MJD: Saying a "FSM can count the number of `foobar` that it sees" might be a bit misleading to the question at hand. Perhaps it is better to say that similar to some (caricatures of) primitive tribes, DFAs can count the number of occurrences of `foobar` as 0, 1, 2, 3, $\ldots$ , $n-1$, many.2012-09-29
  • 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*}$$