# Unambiguous CFG that generates regular language according to Pumping Lemma?

Specifically, the pumping lemma says that for any regular language L there exists a constant p such that any word w in L with length at least p can be split into three substrings, w = xyz, where the middle portion y must not be empty, such that the words xz, xyz, xyyz, xyyyz, … constructed by repeating y an arbitrary number of times (including zero times) are still in L.

Now what's the unambigious CFG that produces this (recognizes strings of the form $xy^kz$)?

if $x=z=a$ and $y=b$, then

$X \rightarrow aX | Xa | bX | Xb | a | b$

is ambiguous.

• Please make sure you know what you want to ask before posting. Wasting people's time by changing your question in fundamental ways is not nice. – Raphael Dec 29 '15 at 14:36
• The Pumping lemma does not claim the existence of such a grammar. But since these words are all in the language L (that is the claim), just use any grammar for L. It remains to see why there are always unambiguous grammars for regular languages, but that's not too hard. – Raphael Dec 29 '15 at 14:39

## 1 Answer

For your first question, do check out the pumping lemma for regular languages. It is quite different from what you state.

For the second one, it is the set of strings of $a$ with exactly one $b$. Use:

\begin{align} S &\rightarrow a S \mid b A \mid b \\ A &\rightarrow a A \mid a \end{align}

Clearly non-ambiguous. Even a regular grammar.

• Is my sentence about the pumping lemma really incorrect? – mavavilj Dec 29 '15 at 13:32
• @mavavilj, yes. – vonbrand Dec 29 '15 at 13:34
• Then what does: "Specifically, the pumping lemma says that for any regular language L there exists a constant p such that any word w in L with length at least p can be split into three substrings, w = xyz, where the middle portion y must not be empty, such that the words xz, xyz, xyyz, xyyyz, … constructed by repeating y an arbitrary number of times (including zero times) are still in L." mean? – mavavilj Dec 29 '15 at 13:34
• @mavavilj, you see the statemement is significantly longer, with a lot of qualifications. – vonbrand Dec 29 '15 at 13:35
• @mavavilj, sorry I won't run around chasing your ever changing question. – vonbrand Dec 29 '15 at 13:59