Theory

1.Regular Language

A language is regular if it can be expressed in terms of regular expression

They are languages that can be recognized by finite automata

Regular expressions can be thought of as the algebraic description of a regular language .

Regular languages have closure properties, meaning that various operations on regular languages (such as union, concatenation, and Kleene star) result in another regular language.

Pumping Lemma

Pumping: The word pumping refers to generating many input strings by pushing a symbol in an input string repeatedly.

Lemma: The word Lemma refers to the intermediate theorem in a proof.

There are two Pumping Lemmas, that are defined for

Regular Languages

Context-Free Languages

Pumping Lemma For Regular Languages

Theorem:

If A is a Regular Language, then A has a Pumping Length ‘P’ such that any string ‘S’ where |S ≥ P may be divided into three parts S = xyz such that the following conditions must be true:

1.) xyⁱz ∈ A for every i ≥ 0

2.) |y| > 0

3.) |xy| ≤ P

Pumping Lemma is used as proof of the irregularity of a language. It means, that if a language is regular, it always satisfies the pumping lemma. If at least one string is made from pumping, not in language A, then A is not regular.

Steps to apply pumping lemma

Step 1: Assume that Language A is Regular.

Step 2: It has to have a Pumping Length (say P).

Step 3: All strings longer than P can be pumped |S| ≥ P.

Step 4: Now, find a string ‘S’ in A such that |S| ≥ P.

Step 5: Divide S into x y z strings.

Step 6: Show that xyⁱz ∉ A for some i.

Step 7: Then consider how S can be divided into x y z.

Step 8: Show that none of the above strings satisfies all three pumping conditions simultaneously.

Step 9: S cannot be pumped == CONTRADICTION.

Detailed description of the steps mentioned above:

1. Assume the language L is regular: This is the starting point for the proof

2. Identify the pumping length (p): The pumping lemma guarantees the existence of a pumping length p for any regular language. This p applies to all strings in the language with a length greater than or equal to p (L ≥ p).

3. Choose a string S ∈ L and |S| ≥ p: Select a string S from the language L that has a length greater than or equal to the pumping length (p).

4.Divide S into three substrings: Divide the chosen string S into three substrings as follows:

x: A prefix of S (can be empty). y: The substring to be "pumped" (must have at least one symbol). z: The suffix of S after y (can be empty). Therefore, the string S can be represented as S=xyz.

5.Apply pumping for different values of i: The lemma states that we can "pump" the substring y by inserting copies of it i times

6.Analyze the resulting strings: The key step is to analyze the resulting strings (xz, s, and x(yⁱ)z) and show that at least one of them does not belong to the language L. This contradicts the initial assumption that L is regular.