Regular expressions, regular grammars and the pumping lemma notes — Unit 2

A DFA is a machine representation of a language. A Regular Expression (RE) is a purely algebraic, declarative representation of that exact same language. It provides a simple string formula to generate all valid strings in the language.

REs are extensively used in modern software engineering (grep, text editors, input validation), though software regex engines add non-theoretical features.

⇒1.1 The Base Cases

Let $\Sigma$ be a given alphabet.

• $\emptyset$ (Empty Set) is a regular expression representing the language containing no strings.
• $\epsilon$ (Epsilon) is a regular expression representing the language containing only the empty string $\{\epsilon\}$.
• For any symbol $a \in \Sigma$, the symbol '$a$' is a regular expression representing the language $\{a\}$.

If $R_1$ and $R_2$ are valid regular expressions, we can combine them using exactly three mathematical operators.

⇒2.1 Union ( $+$ or $|$ )

Represents a logical OR.
The expression $R_1 + R_2$ denotes the language $L(R_1) \cup L(R_2)$.
Example: $0 + 1$ denotes the language containing exactly two strings: $\{0, 1\}$. The string can be a 0 OR a 1.

⇒2.2 Concatenation ( $\cdot$ )

Represents logical sequence. The dot is often omitted.
The expression $R_1 \cdot R_2$ or simply $R_1R_2$ means a string from $R_1$ followed immediately by a string from $R_2$.
Example: $(0+1)0$ denotes $\{00, 10\}$. Any bit, followed by a zero.

⇒2.3 Kleene Star ( $^*$ )

Represents repetition (zero or more times).
The expression $R^*$ denotes the concatenation of $R$ with itself any number of times (including zero).
Example: $0^*$ denotes $\{\epsilon, 0, 00, 000, ...\}$.

Operator Precedence: Star ($^*$) is highest, followed by Concatenation ($\cdot$), followed by Union ($+$). Use parentheses to override.

Translating English rules into algebraic Regular Expressions takes practice. Let $\Sigma = \{a, b\}$.

⇒3.1 Common Examples

• All strings: $(a+b)^*$ (This is the universal set $\Sigma^*$).
• All strings ending in 'abb': $(a+b)^*abb$. (Any random garbage at the start, but absolutely must finish with abb).
• All strings starting with 'a' and ending with 'b': $a(a+b)^*b$.
• All strings containing the substring 'bab': $(a+b)^*bab(a+b)^*$.
• All strings of exactly length 3: $(a+b)(a+b)(a+b)$.
• All strings containing exactly one 'a': $b^*ab^*$. (Zero or more b's, exactly one a, followed by zero or more b's).
• All strings of even length: $((a+b)(a+b))^*$.

Stephen Kleene proved a monumental theorem linking algebra to machines:

Theorem: A language is regular if and only if it is accepted by a finite automaton.
This means RE $\equiv$ NFA $\equiv$ DFA. Any expression can be turned into a machine, and any machine can be reduced to an algebraic expression.

⇒4.1 Converting RE to $\epsilon$-NFA (Thompson's Construction)

We can mechanically build an NFA from a Regular Expression by building tiny primitive machines and linking them with $\epsilon$-transitions.

• For $a+b$ (Union): Create a new start state. Branch it with two $\epsilon$-arrows: one to the start state of machine $a$, one to the start of machine $b$. Connect their final states via $\epsilon$-arrows to a single new final state.
• For $ab$ (Concatenation): Delete the final state of machine $a$. Merge it directly with the start state of machine $b$.
• For $a^*$ (Star): Create a new start state and new final state. Draw an $\epsilon$-arrow from start to final (allowing zero repetitions). Draw an $\epsilon$-arrow from the old final state looping backward to the old start state (allowing multiple repetitions).

How do we go the other way? How do we take a complex web of DFA states and crush it down into a single algebraic Regular Expression? We use Arden's Theorem.

⇒5.1 The Mathematical Rule

Let $P$ and $Q$ be two regular expressions. If $P$ does NOT contain the empty string $\epsilon$, then the algebraic equation:

$R = Q + RP$

has a unique, guaranteed solution:

$R = QP^*$

*(Intuition: The equation means R can be Q, or it can be R followed by P. Recursively expanding it: R = Q + (Q+RP)P = Q + QP + RPP = ... = $QP^*$)*.

To convert a DFA to an RE, we write a system of algebraic equations for every state in the machine.

⇒6.1 The State Equation Method

• 1. Create a variable for each state ($q_0, q_1, q_2$).
• 2. Write an equation for each state detailing the incoming arrows.
  Example: If $q_1$ has an arrow from $q_0$ reading 'a', and a loop on itself reading 'b', the equation is: $q_1 = q_0a + q_1b$.
• 3. Crucial Rule: If the state is the START state, you must mathematically add $+ \epsilon$ to its equation.
• 4. Use basic algebra substitution and Arden's Theorem to systematically eliminate variables, starting from the final states.
• 5. The final Regular Expression is simply the sum of the equations of the Final States.

If $q_2$ is the only final state, and you algebraically solve the system to find $q_2 = a(a+b)^*$, then that is your final Regular Expression.

We have machines (DFA) and algebra (RE). We now introduce linguistics (Grammars). A Grammar provides a set of production rules to generate strings.

⇒7.1 Formal 4-Tuple Definition

A grammar $G = (V, T, P, S)$

• $V$ (Variables / Non-terminals): Abstract symbols representing sets of strings. Usually uppercase letters (A, B, S).
• $T$ (Terminals): The actual alphabet symbols of the language. Usually lowercase letters (a, b, 0, 1).
• $P$ (Production Rules): Mapping rules defining how variables can be replaced by terminals and other variables. (e.g., $A \rightarrow aB$).
• $S$ (Start Symbol): The specific variable where all generation begins. $S \in V$.

A Grammar is only considered "Regular" if its production rules follow incredibly strict formatting limits.

⇒8.1 Right Linear Grammar

Every production rule must be in the form:
$A \rightarrow aB$ (A terminal followed by AT MOST one variable)
or
$A \rightarrow a$ (Just a terminal)
or
$A \rightarrow \epsilon$

The single non-terminal must always be on the absolute RIGHT side.

⇒8.2 Left Linear Grammar

Every production rule must be in the form:
$A \rightarrow Ba$ (The variable is on the LEFT)
or $A \rightarrow a$.

Important: You cannot mix Right Linear and Left Linear rules in the same grammar. If you do, it becomes a Context-Free Grammar, which is mathematically more powerful and cannot be represented by a DFA.

DFAs are incredible for simple pattern matching, but they have a fatal, insurmountable flaw: They cannot count.

⇒9.1 The Memory Problem

Consider the language $L = \{a^n b^n \mid n \ge 0\}$.
This is the language of perfectly balanced strings: $\epsilon, ab, aabb, aaabbb$.

To build a DFA for this, the machine must read all the 'a's, remember exactly how many it saw, and then verify it sees the exact same number of 'b's.
If $n=5$, it needs 5 states to count the 'a's. If $n=1000$, it needs 1000 states.
Since $n$ can go to infinity, the machine would require an infinite number of states. But the 'F' in DFA stands for FINITE Automata.

Therefore, it is mathematically impossible to build a DFA for $a^n b^n$. This language is Not Regular.

How do we definitively prove to a mathematician that a language is NOT regular? We use the Pumping Lemma, a proof by contradiction.

⇒10.1 The Theorem Statement

If $L$ is a regular language, then there exists some constant integer $p$ (the pumping length, representing the number of states in the DFA), such that ANY string $w$ in the language where $|w| \ge p$, can be mathematically split into three distinct pieces: $w = xyz$, satisfying three strict conditions:

• 1. $|y| > 0$: The middle piece $y$ cannot be empty. It must contain at least one symbol. (This represents a loop in the DFA).
• 2. $|xy| \le p$: The first two pieces combined must be shorter than or equal to the pumping length. (The loop must occur within the first $p$ states).
• 3. For all $i \ge 0, xy^iz \in L$: You can duplicate (pump) the middle piece $y$ zero times, twice, or ten billion times, and the resulting Frankenstein string MUST still magically belong to the language $L$.

We use the lemma as an adversarial game. We assume the language IS regular, let the lemma make its claims, and then we strategically break Condition 3 to force a contradiction.

⇒11.1 Prove $L = \{a^n b^n\}$ is not regular.

• Step 1: Assume $L$ is regular. Therefore, there exists a pumping length $p$.
• Step 2: I must choose a specific string from $L$ that is longer than $p$. Let $w = a^p b^p$. (This string has $p$ 'a's followed by $p$ 'b's).
• Step 3: The lemma states $w$ can be split into $xyz$.
  Condition 2 says $|xy| \le p$. Since the first $p$ characters of our string are exclusively 'a's, this mathematically forces $x$ and $y$ to be composed entirely and exclusively of 'a's. There are no 'b's in $y$.
• Step 4: Let's pump $y$ (duplicate it). We check $xy^2z$.
  Because $y$ consists only of 'a's (by Step 3), and $y$ is not empty (Condition 1), duplicating $y$ adds more 'a's to the string. However, it adds absolutely zero 'b's.
• Step 5: The new pumped string has more 'a's than 'b's. Therefore, it is no longer of the form $a^n b^n$. It is mathematically impossible for $xy^2z$ to be in $L$.

Conclusion: Condition 3 is broken. Our initial assumption must be false. The language is NOT regular.

A set is "closed" under an operation if applying that operation to elements of the set produces a result that is still inside the set.

Regular Languages are incredibly robust. They are closed under almost everything.

⇒12.1 The Major Closure Properties

If $L_1$ and $L_2$ are regular languages, then the following are mathematically guaranteed to ALSO be regular languages (meaning a DFA can be built for them):

• Union: $L_1 \cup L_2$. (Proven by Thompson's construction).
• Concatenation: $L_1 \cdot L_2$.
• Kleene Star: $L_1^*$.
• Intersection: $L_1 \cap L_2$. (Proven by building a DFA that simulates both machines simultaneously using the Cartesian Product of states).
• Complement: $\Sigma^* - L_1$. (Proven by simply taking the DFA for $L_1$ and flipping all Final states to Non-Final, and all Non-Final states to Final).
• Difference: $L_1 - L_2$. (Because $L_1 - L_2 = L_1 \cap \overline{L_2}$, and it is closed under intersection and complement).
• Reversal: $L_1^R$. (Reverse all strings. Proven by reversing the arrows on the DFA).

Advanced operations under which Regular Languages remain closed.

⇒13.1 Homomorphism

A homomorphism is a substitution function. It replaces every single symbol in the alphabet with a specific string of symbols.

Example: Let $h(0) = a$ and $h(1) = bb$.
If $w = 010$, then $h(w) = abba$.
If $L$ is a regular language, then the new language $h(L)$ (created by applying the substitution to every string in L) is guaranteed to still be a regular language.

⇒13.2 Inverse Homomorphism

The reverse process. It asks: "What original strings, when subjected to the substitution $h$, would result in strings that belong to language $L$?"

Regular Languages are mathematically closed under inverse homomorphism.

Unit 2 requires you to fluidly translate between the algebraic RE world and the machine DFA world, and provides the mathematical weapons to prove limits.

⇒14.1 University Exam Checklist

• Write a Regular Expression for complex English specifications (e.g., "strings of 0s and 1s containing at least three 1s").
• State Kleene's Theorem.
• Use Thompson's Construction algorithm to systematically draw an $\epsilon$-NFA for a complex Regular Expression like $(a+b)^*abb$.
• State Arden's Theorem ($R = Q + RP$).
• Given a DFA transition diagram, write the system of state equations and use Arden's Theorem to solve for the final Regular Expression.
• Define a Regular Grammar (Right Linear and Left Linear) and explain why mixing the rules is illegal.
• Convert a DFA directly into a Right Linear Grammar.
• State the Pumping Lemma for Regular Languages, detailing all three conditions of $w=xyz$.
• Use the Pumping Lemma to mathematically prove that $L = \{0^n 1^n\}$, $L = \{ww^R\}$ (palindromes), and $L = \{a^p \mid p \text{ is prime}\}$ are NOT regular languages.
• List five operations under which Regular Languages are closed. Briefly explain the proof for Complement and Intersection.