pumping lemma for very simple regular expression

Question

Pumping lemma definition (from wiki)

Let L be a regular language. Then there exists an integer p ≥ 1 depending only on L such that every string w in L of length at least p (p is called the "pumping length"[4]) can be written as w = xyz (i.e., w can be divided into three substrings), satisfying the following conditions:

|y| ≥ 1; |xy| ≤ p for all i ≥ 0, xyiz ∈ L

Suppose I want to test regular expression 011 Since it is regular expressionm, there is string w for at least length p that satisfy w=xyz

The number of this automata is 3, p should be >= 3 But only string that accept this automata is 011 So I pick 011 as w I can break up 3 part 011 = xyz but how can I break? I cannot satisfy |y| ≥ 1; |xy| ≤ p for all i ≥ 0, xyiz ∈ L

Since it is only accept 011 How can I pump? Where am I wrong

Pumping Lemma is for Regular Languages not expressions. What is the language in this question ? — sinanspd
@sinanspd: Every regular expression (in the CS sense) defines a unique regular language. In this case L = { "011" }. — ruakh
@ruakh yeah I thought the language would be broader since pumping a language of a single expression is relatively easier — sinanspd

ruakh ruakh · Accepted Answer · 2015-04-17T01:13:24

Let p be 4. Then there are no strings w in L of length at least p, so any statement of the form "Every string w in L of length at least p […]" will be vacuously true. So the pumping lemma is satisfied.

pumping lemma for very simple regular expression

2 Answers