Session 11 and 12: �Pumping Lemma for Regular sets – Problems based on Pumping Lemma
By
Dr. Ashok Kumar
Amity School of Engineering & Technology
2
Question: How can we prove that a language
is not regular?
Prove that there is no DFA that accepts
Problem: this is not easy to prove
Solution: the Pumping Lemma !!!
Amity School of Engineering & Technology
The Pumping Lemma:
3
Amity School of Engineering & Technology
Applications ��of��the Pumping Lemma
Amity School of Engineering & Technology
5
Theorem:
The language
is not regular
Proof:
Use the Pumping Lemma
Amity School of Engineering & Technology
6
Assume for contradiction
that is a regular language
Since is infinite
we can apply the Pumping Lemma
Amity School of Engineering & Technology
Let be the integer in the Pumping Lemma
Pick a string such that:
length
We pick
Amity School of Engineering & Technology
it must be that length
From the Pumping Lemma
Write:
Thus:
Amity School of Engineering & Technology
From the Pumping Lemma:
Thus:
Amity School of Engineering & Technology
From the Pumping Lemma:
Thus:
Amity School of Engineering & Technology
BUT:
CONTRADICTION!!!
Amity School of Engineering & Technology
Our assumption that
is a regular language is not true
Conclusion:
is not a regular language
Therefore:
Amity School of Engineering & Technology
Application of Finite Automata
a. Recognizing patterns in text or other data: Finite automata can be used to search for and recognize specific patterns in text or other data. For example, a finite automaton can be used to recognize email addresses, URLs, or phone numbers in text.
b. Implementing regular expressions in programming languages: Regular expressions are a way to describe patterns in text using a set of rules. These rules can be translated into a finite automaton, which is used to match the pattern in the input text. Many programming languages, such as Perl, Python, and Java, use finite automata to implement regular expressions.
c. Validating input in form fields on websites: Finite automata can be used to validate user input in form fields on websites. For example, a finite automaton can be used to ensure that a user enters a valid email address or password.
Amity School of Engineering & Technology
d. Modeling digital circuits and switching systems: Finite automata can be used to model digital circuits and switching systems, such as those found in computers and other electronic devices.
e. Designing and analyzing computer algorithms and programs: Finite automata can be used to design and analyze computer algorithms and programs.
f. Building compilers and interpreters: Finite automata are used in the development of compilers and interpreters, which are programs that translate high-level programming languages into machine code that can be executed by a computer. Finite automata are used to recognize and process the syntax and semantics of the programming language.
Amity School of Engineering & Technology
g. Analyzing the behavior of software and hardware systems: Finite automata can be used to analyze the behavior of software and hardware systems, such as operating systems or network protocols.
h. Verifying the correctness of software and hardware systems: Finite automata can be used to verify the correctness of software and hardware systems by checking whether they satisfy certain requirements or specifications.
i. Developing language models and machine learning algorithms: Finite automata are used in the development of language models and machine learning algorithms, which are used in natural language processing and other applications. They can help identify patterns in data and make predictions based on those patterns.
Amity School of Engineering & Technology