Infinite Automata | Pumping Lemma | Toc
#InfiniteAutomata
#PumpingLemma
#TheoryOfAutomata
#TOC
Hello everyone welcome to learning Portal if you have any query related to our lectures then feel free and comment us we will reply you as soon as possible.
Pumping Lemma version II
Statement
Let L be an infinite language accepted by a finite automaton with N states, then for all words w in L that have
langth more than N, there are strings x,y and z (y being non-null string) and length(x) + length(y) ≤ N s.t.
w = xyz and all strings of the form xynz are in L for n = 1,2,3, …
Proof
The lemma can be proved, considering the following examples
Example
Consider the language PALINDROME which is obviously infinite language. It has already been shown that the
PALINDROME satisfies pumping lemma version I (previous version). To check whether the new version of
pumping lemma still holds in case of the PALINDROME, let the PALINDROME be a regular language and be
accepted by an FA of 78 states. Consider the word w = a85ba85.
Decompose w as xyz, where x,y and z are all strings belonging to ∑* while y is non-null string, s.t.
length(x) + length(y) ≤ 78, which shows that the substring xy is consisting of a’s and xyyz will become
a
more than 85
ba85 which is not in PALINDROME. Hence pumping lemma version II is not satisfied for the
language PALINDROME. Thus pumping lemma version II can’t be satisfied by any non regular language.
Following is another example in this regard