Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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. –  Micah Sep 29 '12 at 4:58
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. –  MJD Sep 29 '12 at 5:40
    
@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. –  Arthur Fischer Sep 29 '12 at 7:38
    
@Arthur Yes, saying "...it never has to count higher than 2" is crucial, which is why I said that. –  MJD Sep 29 '12 at 12:51
add comment

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer
add comment

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*}$$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.