Pumping lemma used to show that language is not regular.
What is pumping?
for regular expression
r = (a u b) (abb)* (bba u bbb), the string w= babbbbb pumps because we may decompose w into three sub strings.
w= b. abb. bbb
such that b(abb)i bbb is represented by r, for every i>= 0.
in this DFA.,
the string aaabab= aa. aba.b pumps because of the cycle that the aba follows.
Suppose L is a regular Language., the there exists an integer k such that for all strings z belongs to L. , satisfying |z|>=k., we can write z= uvw where
|v| >= 1
|uv| <=k
u vi w belongs to L, for all i>=0.
No comments:
Post a Comment