Question

3. Consider the following “theorem". If L is a regular language then

∀ words w ∈ L where |w| > 1
∃ an expression w = xyz where

(a) ∀i≥0.xyiz∈L

(b) |y| ≥ 1
Explain whether this is a (true) theorem or not

( the question want us to explain why this theorem does not work alone)

Answer 1

The theorem does not works because it does assumes anything about the size of L. if L is finite ,this 'theorem' would not work.

This might look like pumping lemma for regular languages but it is not since the requirement for pumping lemma to work is that L is an infinite Language(otherwise its regular trivially) so that we always find a state in FSA for L, which we visit again and again.

A counterexample for this theorem would be L={a}, the only choice of y is 'a', but y²=aa does not belong to L