FOR FREE CONTENT

Pumping Lemma Theorem for Regular Langauge:

Let L be an infinite regular, then there exists some positive  integer n (No. of state in minimal DFA)

Such that,

Any ω ∊ L with |w| ≥ n can be decomposed as (Where ω and L represent string and language correspondingly).

ω = xyz with conditions (1) | xy | ≤ n and  (2) | y | ≥ 1 (pumping).

Such that,

So, one language violet above pumping lemma theorem then it is not regular.

Example:

The number of states of given Finite Automata n = 3 so, | ω | ≥  n it satisfies the first condition. 

Now, | xy | = 2 so, | xy | ≤ n satisfy it. 

Whereas | y | ≥ 1 or y > 0 it means y should be pumping loop for ω = xyyz it also possible and we can take as, 

Let’s take another example:

Now, what strings belong to this language? 

In that case:

Then we can say the language xy*z, not violet pumping lemma.