Pumping Lemma
Lemma: (Pumping Lemma)
If L is a regular language, then there exists a positive integer p (the pumping length) such that every string s ∈
L,|s | ≥p, can be partitioned into three pieces,s=xyz, such that the following conditions hold:
1.|y| > 0,
2.|xy| ≤p, and
Standard Example:
1.L={anbn | n=0}is not regular.
2.L={1n | n is a prime number}is not regular.
3.L={0i1j| i > j}is not regular.
If L is a regular language, then there exists a positive integer p (the pumping length) such that every string s ∈
L,|s | ≥p, can be partitioned into three pieces,s=xyz, such that the following conditions hold:
1.|y| > 0,
2.|xy| ≤p, and
3.for each i ≥0, xyiz
Standard Example:
1.L={anbn | n=0}is not regular.
2.L={1n | n is a prime number}is not regular.
3.L={0i1j| i > j}is not regular.
Comments
Post a Comment