Diving Deep into Regular Languages - Automata, Expressions, and Grammars

Hello again, explorers of computation! In our previous journey, we introduced the fundamental concepts of regular languages. Today, we're diving even deeper, adding more detail and formal structure to our understanding. We'll reinforce the connections between machines, expressions, and grammars that define this foundational class of languages. Get ready for a more thorough look!

1. The Groundwork Revisited: More Detailed Basic Concepts

Let's solidify our understanding of the core building blocks.

Alphabets, Strings, and Languages

• Alphabet (Σ): A finite, non-empty set of symbols. Examples: $\Sigma = \{a, b\}$, $\Sigma = \{0, 1, \dots, 9\}$.
• String: A finite sequence of symbols from Σ. The empty string, denoted by λ, is the string with zero symbols. $|\lambda| = 0$.
• String Operations:
  • Concatenation: If $w = a_1a_2\dots a_n$ and $v = b_1b_2\dots b_m$, their concatenation $wv$ is $a_1a_2\dots a_n b_1b_2\dots b_m$. Concatenation with the empty string leaves a string unchanged: $\lambda w = w \lambda = w$.
  • Length: $|w|$ denotes the number of symbols in $w$. It follows that $|uv| = |u| + |v|$.
  • Reversal: $w^R$ is the string written in reverse order. If $w=a_1\dots a_n$, then $w^R = a_n \dots a_1$. We have $(uv)^R = v^R u^R$ and $(w^R)^R = w$.
  • Powers: $w^n$ is $w$ concatenated with itself $n$ times. $w^0 = \lambda$.
  • Substring: Any string of consecutive symbols within $w$.
  • Prefix/Suffix: If $w = vu$, then $v$ is a prefix and $u$ is a suffix of $w$. λ is a prefix and suffix of every string.
• Set of Strings:
  • Σ*: The set of all possible finite strings over Σ, including λ. This set is always infinite if Σ is non-empty.
  • Σ+: The set Σ* excluding λ. Σ+ = Σ* - {λ}.
• Language (L): Defined formally as any subset of Σ*.
  • Sentence: A string $w$ is a sentence of language $L$ if $w \in L$.
  • Finite Language: A language with a finite number of sentences.
  • Infinite Language: A language with an infinite number of sentences (most interesting languages are infinite). Example: $L = \{a^n b^n : n \ge 0\} = \{\lambda, ab, aabb, aaabbb, \dots\}$.

Language Operations

Since languages are sets, standard set operations apply:

• Union ($L_1 \cup L_2$)
• Intersection ($L_1 \cap L_2$)
• Difference ($L_1 - L_2$)
• Complement ($\overline{L} = \Sigma^* - L$, relative to the alphabet Σ)

We also define operations specific to languages:

• Reverse: $L^R = \{w^R : w \in L\}$.
• Concatenation: $L_1 L_2 = \{uv : u \in L_1, v \in L_2\}$.
• Powers: $L^n = L$ concatenated with itself $n$ times. $L^0 = \{\lambda\}$, $L^1 = L$.
• Kleene Star (Star Closure): $L^* = L^0 \cup L^1 \cup L^2 \cup \dots = \bigcup_{i=0}^{\infty} L^i$.
• Positive Closure: $L^+ = L^1 \cup L^2 \cup \dots = \bigcup_{i=1}^{\infty} L^i$. Note that $L^* = L^+ \cup \{\lambda\}$.

Grammars

Grammars provide a finite way to describe potentially infinite languages. A grammar $G = (V, T, S, P)$ consists of:

• $V$: Finite set of variables (non-terminals, often uppercase letters).
• $T$: Finite set of terminal symbols (the alphabet Σ, often lowercase letters or digits). $V \cap T = \emptyset$.
• $S$: The start variable ($S \in V$), representing the top-level concept (like 'sentence').
• $P$: Finite set of productions (rewrite rules).

Productions specify how strings can be transformed. For now, we consider general productions $x \rightarrow y$, where $x \in (V \cup T)^+$ (at least one symbol, including at least one variable) and $y \in (V \cup T)^*$.

• Derivation Step: If $w = uxv$, and $x \rightarrow y$ is a production in $P$, we say $w$ derives $z = uyv$, written $w \Rightarrow z$.
• Derivation: A sequence of derivation steps: $w_1 \Rightarrow w_2 \Rightarrow \dots \Rightarrow w_n$. We write $w_1 \Rightarrow^* w_n$ to indicate $w_n$ can be derived from $w_1$ in zero or more steps.
• Sentential Form: Any string (containing variables and/or terminals) derivable from the start symbol $S$.
• Language Generated ($L(G)$): The set of all strings consisting only of terminals that can be derived from $S$. $L(G) = \{w \in T^* : S \Rightarrow^* w\}$.

Example: Grammar $G = (\{S\}, \{a, b\}, S, \{S \rightarrow aSb, S \rightarrow \lambda\})$ generates $L(G) = \{a^n b^n : n \ge 0\}$. Derivation of $aabb$: $S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aabb$. The strings $S, aSb, aaSbb$ are sentential forms.

Automata

An automaton is an abstract computational model. Key components:

• Input: A string read sequentially.
• Control Unit: Has a finite set of internal states, including an initial state.
• Storage: Temporary memory (its nature distinguishes automata types).
• Transitions: Moves between states based on current state, input symbol, and storage contents.
• Output: Can be a simple accept/reject (accepter) or a generated string (transducer).

Automata operate in discrete time steps. A configuration describes the state, remaining input, and storage content. A move is a transition between configurations.

2. Finite Automata (FA): Computation with Bounded Memory

Finite Automata have a control unit but no temporary storage beyond their current state. They recognize the family of regular languages.

Deterministic Finite Accepters (DFA)

A DFA makes precisely one move for each input symbol.

Formal Definition: A DFA is a 5-tuple $M = (Q, \Sigma, \delta, q_0, F)$:

• $Q$: Finite set of states.
• $\Sigma$: Finite input alphabet.
• $\delta: Q \times \Sigma \rightarrow Q$: The transition function. Given state $q \in Q$ and input $a \in \Sigma$, $\delta(q, a)$ is the unique next state. $\delta$ is a total function, defined for all pairs $(q, a)$.
• $q_0 \in Q$: The initial state.
• $F \subseteq Q$: The set of final (accepting) states.

Operation:

1. Starts in state $q_0$.
2. Reads the input string $w = a_1a_2\dots a_n$ from left to right.
3. After reading $a_i$, if in state $q$, transitions to state $\delta(q, a_i)$.
4. After reading $a_n$, if the current state is in $F$, the string $w$ is accepted. Otherwise, it's rejected.

Extended Transition Function ($\delta^*$): To describe the state after processing a string $w$, we define $\delta^*: Q \times \Sigma^* \rightarrow Q$ recursively:

1. $\delta^*(q, \lambda) = q$ (Base case: empty string doesn't change state).
2. $\delta^*(q, wa) = \delta(\delta^*(q, w), a)$ (Recursive step: state after reading $wa$ is found by applying $\delta$ to the state after reading $w$ and the final symbol $a$).

Theorem: $\delta^*(q_i, w) = q_j$ if and only if there is a walk labeled $w$ from state $q_i$ to state $q_j$ in the DFA's transition graph.

Language Accepted ($L(M)$): $L(M) = \{w \in \Sigma^* : \delta^*(q_0, w) \in F\}$.

Regular Language: A language $L$ is regular if there exists a DFA $M$ such that $L = L(M)$.

Example DFA Construction:

• To accept strings starting with "ab": Need states to track "start", "seen a", "seen ab" (final trap), and "error" (non-final trap).
• To accept strings not containing "001": Need states to remember relevant suffixes seen so far (λ, 0, 00). If "001" is formed, go to a non-final trap state. All other reachable states are final.

Nondeterministic Finite Accepters (NFA)

NFAs allow multiple possible moves from a state on a given input symbol, or moves on the empty string λ.

Formal Definition: An NFA is a 5-tuple $M = (Q, \Sigma, \delta, q_0, F)$, where $Q, \Sigma, q_0, F$ are as in DFAs, but $\delta$ is different:

• $\delta: Q \times (\Sigma \cup \{\lambda\}) \rightarrow 2^Q$. The function maps a state and an input symbol (or λ) to a set of possible next states.

Operation:

• An NFA can be in multiple states simultaneously (conceptually).
• If $\delta(q, a)$ contains $p_1, p_2, \dots, p_k$, the NFA can transition to any of these states upon reading $a$ while in state $q$.
• If $\delta(q, \lambda)$ contains $p$, the NFA can transition from state $q$ to state $p$ without consuming any input symbol.
• If $\delta(q, a) = \emptyset$, there is no move defined (dead configuration for that path).

Extended Transition Function ($\delta^*$): For an NFA, $\delta^*(q_i, w)$ is the set of all states reachable from state $q_i$ by following paths labeled $w$ (including λ-transitions).

Acceptance: An NFA accepts $w$ if any possible sequence of moves results in the NFA being in any state from $F$ after processing $w$. Formally: $L(M) = \{w \in \Sigma^* : \delta^*(q_0, w) \cap F \neq \emptyset\}$.

Why Nondeterminism?

• Modeling: Can model search/backtracking algorithms naturally.
• Convenience: Often much simpler/smaller NFAs exist for a language compared to the minimal DFA (e.g., union of languages).
• Theory: Easier to prove certain properties (like closure under union, concatenation, star) using NFAs.

Equivalence of DFA and NFA

Theorem: For every NFA $M_N$, there exists a DFA $M_D$ such that $L(M_N) = L(M_D)$. The family of languages accepted by NFAs is exactly the family of regular languages.

Subset Construction (nfa-to-dfa procedure):

1. The states of $M_D$ are sets of states of $M_N$ (i.e., elements of $2^{Q_N}$).
2. The initial state of $M_D$ is the set containing $q_0$ and all states reachable from $q_0$ via λ-transitions (the λ-closure of $\{q_0\}$).
3. The transition $\delta_D(\{p_1, \dots, p_k\}, a)$ is the set of all states in $M_N$ reachable from any $p_i$ by reading $a$, followed by any number of λ-transitions.
4. A state $\{p_1, \dots, p_k\}$ in $M_D$ is final if at least one $p_i$ is a final state in $M_N$ ($p_i \in F_N$).

This construction might lead to a DFA with up to $2^{|Q_N|}$ states, though often fewer are reachable.

Minimization of the Number of States in a DFA

Finding the unique minimal DFA for a regular language involves identifying and merging indistinguishable states.

Definitions:

• Indistinguishable: States $p, q$ are indistinguishable if for all $w \in \Sigma^*$, $\delta^*(p, w) \in F \iff \delta^*(q, w) \in F$.
• Distinguishable: States $p, q$ are distinguishable if there exists some $w \in \Sigma^*$ such that one of $\delta^*(p, w)$ and $\delta^*(q, w)$ is in $F$ and the other is not.

Algorithm (mark and reduce):

1. Remove inaccessible states (states unreachable from $q_0$).
2. Initialize: Mark all pairs $(p, q)$ where one is final ($p \in F$) and the other is not ($q \notin F$) as distinguishable.
3. Iterate: Repeat until no new pairs are marked: For every unmarked pair $(p, q)$ and every $a \in \Sigma$, let $p_a = \delta(p, a)$ and $q_a = \delta(q, a)$. If the pair $(p_a, q_a)$ is already marked as distinguishable, mark $(p, q)$.
4. Merge: All pairs $(p, q)$ that remain unmarked are indistinguishable. Group states into equivalence classes based on indistinguishability.
5. Construct Minimal DFA: Create one state for each equivalence class. The initial state is the class containing $q_0$. A state (class) is final if it contains any original final state. Transitions are defined naturally: if $\delta(p, a) = q$, and $p$ is in class $E_i$ and $q$ is in class $E_j$, then the transition for the minimal DFA is $\delta'(E_i, a) = E_j$.

The resulting DFA is guaranteed to be minimal in the number of states and is unique (up to state relabeling).

3. Regular Expressions: An Algebraic Language Description

Regular expressions provide a text-based way to define regular languages.

Formal Definition:

1. Primitives: ∅, λ, and $a$ (for $a \in \Sigma$) are regular expressions.
2. Recursive Step: If $r_1$ and $r_2$ are regular expressions, then $(r_1 + r_2)$, $(r_1 \cdot r_2)$, and $(r_1^*)$ are regular expressions.
3. Only strings formed by rules 1 and 2 are regular expressions.

Language Denoted ($L(r)$):

• $L(\emptyset) = \emptyset$ (the empty language)
• $L(\lambda) = \{\lambda\}$ (the language containing only the empty string)
• $L(a) = \{a\}$ (the language containing only the string 'a')
• $L(r_1 + r_2) = L(r_1) \cup L(r_2)$ (Union)
• $L(r_1 \cdot r_2) = L(r_1) L(r_2)$ (Concatenation: $\{uv | u \in L(r_1), v \in L(r_2)\}$)
• $L(r_1^*) = (L(r_1))^*$ (Kleene Star: zero or more concatenations)

Conventions:

• Precedence: $^*$ (highest) > $·$ (concatenation) > $+$ (union).
• Concatenation dot ($·$) is often omitted (e.g., $r_1 r_2$).
• Parentheses $(...)$ group expressions.

Example: $L((0+1)^*00(0+1)^*) = \{w \in \{0,1\}^* \mid w \text{ contains the substring } 00\}$. Example: $L((1^*011^*)^*(0+\lambda) + 1^*(0+\lambda))$ or $L((1+01)^*(0+\lambda))$ describes strings over $\{0,1\}$ with no consecutive zeros. (Different expressions can denote the same language).

4. The Grand Equivalence: Expressions, NFAs, and DFAs

These three formalisms are equally powerful in describing regular languages.

Theorem: A language L is regular if and only if:

• L is accepted by some DFA.
• L is accepted by some NFA.
• L is described by some regular expression.

Constructions:

• RegEx → NFA: Build NFAs for primitive expressions (∅, λ, a). Combine them using λ-transitions to simulate union (parallel paths), concatenation (series connection), and star (feedback loop).
• NFA → DFA: Use the subset construction.
• DFA → RegEx: One method uses Generalized Transition Graphs (GTGs) where edge labels are regular expressions. Start with the DFA's graph. Systematically eliminate states one by one, recalculating edge labels (which become more complex regular expressions) to represent the paths through the eliminated state. Continue until only the start state and a single final state (or just the start state if it's final) remain. The expression(s) on the remaining edge(s) define the language. The process involves rules like $r_{pq}' = r_{pq} + r_{pk} (r_{kk})^* r_{kq}$ when eliminating state $q_k$.

5. Exploring the Properties of Regular Languages

Understanding the characteristics shared by all regular languages helps differentiate them from other language families.

Closure Properties

Regular languages are robust under many operations:

• Union, Concatenation, Kleene Star: Proved directly from the definition of regular expressions.
• Complementation: If $L$ is accepted by DFA $M=(Q, \Sigma, \delta, q_0, F)$, then $\overline{L}$ is accepted by $M'=(Q, \Sigma, \delta, q_0, Q-F)$. This relies on the DFA being deterministic and having a total transition function.
• Intersection: Can be proved constructively by building a product DFA. If $M_1=(Q_1, \Sigma, \delta_1, q_{0,1}, F_1)$ and $M_2=(Q_2, \Sigma, \delta_2, q_{0,2}, F_2)$, the intersection DFA $M_\cap$ has states $Q_1 \times Q_2$, initial state $(q_{0,1}, q_{0,2})$, final states $F_1 \times F_2$, and transitions $\delta_\cap((p,q), a) = (\delta_1(p,a), \delta_2(q,a))$. Alternatively, use DeMorgan's law: $L_1 \cap L_2 = \overline{\overline{L_1} \cup \overline{L_2}}$ and closure under union/complement.
• Difference: $L_1 - L_2 = L_1 \cap \overline{L_2}$. Follows from closure under complement and intersection.
• Reversal: Construct an NFA for $L^R$ by reversing edges and swapping start/final states of an NFA for $L$.
• Homomorphism: Replace terminals in a regular expression for $L$ with their string images under the homomorphism $h$ to get a regular expression for $h(L)$.
• Right Quotient ($L_1/L_2 = \{x : xy \in L_1 \text{ for some } y \in L_2\}$): If $L_1, L_2$ are regular, $L_1/L_2$ is regular. Construct a DFA for $L_1/L_2$ by modifying the final states of a DFA for $L_1$. A state $q$ becomes final if $\delta^*(q_0, x) = q$ and there exists some $y \in L_2$ such that $\delta^*(q, y)$ is an original final state.

The Pumping Lemma for Regular Languages (Detailed)

This is a crucial tool for proving non-regularity.

Pumping Lemma: Let L be a regular language. Then there exists a constant $m \ge 1$ (the pumping length, related to the number of states in a DFA for L) such that for any string $w \in L$ with $|w| \ge m$, $w$ can be divided into three substrings, $w = xyz$, satisfying:

1. $|y| \ge 1$ (the pumped part is non-empty).
2. $|xy| \le m$ (the part $xy$ occurs within the first $m$ symbols).
3. For all integers $i \ge 0$, the string $w_i = xy^i z$ is also in $L$. ($y^0 = \lambda$, so $xz \in L$).

Proof Idea: If $|w| \ge m$ (where $m$ is the number of states in a DFA for $L$), the path traced by $w$ in the DFA must visit at least $m+1$ states. By the pigeonhole principle, some state $q_r$ must be visited twice within the first $m$ transitions. Let $w=xyz$ where $x$ takes the DFA from $q_0$ to the first occurrence of $q_r$, $y$ takes it from $q_r$ back to $q_r$ (the cycle), and $z$ takes it from $q_r$ to a final state. Since the repeated state occurs within the first $m$ transitions, $|xy| \le m$. Since it's a cycle based on non-empty input, $|y| \ge 1$. Because $y$ loops from $q_r$ to $q_r$, we can traverse this loop $i$ times ($xy^iz$) and still end up in the same final state via $z$.

Using the Pumping Lemma (The Game):

1. Assume: $L$ is regular (for contradiction).
2. Lemma Gives: An adversary provides the pumping length $m$.
3. You Choose: Select a specific string $w \in L$ such that $|w| \ge m$. Your choice should strategically limit the adversary's options.
4. Adversary Decomposes: The adversary chooses some decomposition $w=xyz$ satisfying $|y| \ge 1$ and $|xy| \le m$. You must show the lemma fails for all valid choices they could make.
5. You Pump: Choose an integer $i \ge 0$ (often $i=0$ or $i=2$) such that the resulting string $w_i = xy^iz$ is provably not in $L$.
6. Contradiction: This violates the Pumping Lemma, so the initial assumption that $L$ was regular must be false.

Common Mistakes:

• Picking $m$ yourself.
• Choosing a $w$ with $|w| < m$.
• Assuming a specific decomposition $xyz$ (you must counter all possible decompositions allowed by the lemma).
• Picking an $i$ that does result in a string in $L$.
• Trying to use the lemma to prove a language is regular (it only proves non-regularity).

Myhill-Nerode Theorem and Regularity

The Myhill-Nerode theorem provides an alternative characterization of regular languages based on equivalence relations. For a language $L$ over Σ, define a relation $R_L$ on Σ* such that $x R_L y$ if and only if for all $z \in \Sigma^*$, $xz \in L \iff yz \in L$. This means $x$ and $y$ are indistinguishable with respect to $L$ if appending any suffix $z$ results in strings that are either both in $L$ or both not in $L$.

Theorem (Myhill-Nerode): A language $L$ is regular if and only if the relation $R_L$ has a finite number of equivalence classes (i.e., its index is finite).

The number of equivalence classes corresponds exactly to the number of states in the minimal DFA for $L$. This theorem provides another way to prove non-regularity (by showing an infinite number of equivalence classes) and is the theoretical foundation for DFA minimization algorithms.

Identifying Non-Regular Languages: Summary

1. Pumping Lemma: The primary method. Choose $w$ strategically, show all possible decompositions lead to a contradiction when pumped.
2. Closure Properties: Show that $L \cap R$, $h(L)$, $L/R$, etc., where $R$ is regular and $h$ is a homomorphism, results in a known non-regular language. If $L$ were regular, the result would have to be regular due to closure.
3. Myhill-Nerode: Show that $L$ induces an infinite number of equivalence classes under the relation $R_L$.

Decision Algorithms for Regular Languages

Key problems about regular languages are decidable, meaning algorithms exist:

• Membership ($w \in L$?): Simulate the minimal DFA for $L$ on input $w$. Time $O(|w|)$.
• Emptiness ($L = \emptyset$?): Check if any final state is reachable from the start state in the DFA graph (e.g., using BFS or DFS). Time polynomial in the number of states.
• Finiteness/Infiniteness ($|L| = \infty$?): Check if there is a cycle in the DFA graph that is reachable from the start state and from which a final state can be reached. Time polynomial in the number of states.
• Equality ($L_1 = L_2$?): Construct the minimal DFAs $M_1, M_2$. They accept the same language iff they are isomorphic (identical structure, perhaps different state names). Alternatively, construct a DFA for the symmetric difference $L_{\Delta} = (L_1 \cap \overline{L_2}) \cup (\overline{L_1} \cap L_2)$ using closure properties and check if $L_{\Delta} = \emptyset$. Time polynomial in state counts.
• Subset ($L_1 \subseteq L_2$?): Check if $L_1 \cap \overline{L_2} = \emptyset$. Follows from closure and emptiness check.

6. Regular Grammars: Rules for Regular Languages

Regular languages can also be defined using restricted forms of grammars.

Definitions:

• Right-Linear Grammar: All productions are $A \rightarrow aB$, $A \rightarrow B$, $A \rightarrow a$, or $A \rightarrow \lambda$ (where $A, B \in V, a \in T$). Often simplified to $A \rightarrow xB$ or $A \rightarrow x$ where $x \in T^*$. The key is at most one variable, always at the rightmost end.
• Left-Linear Grammar: All productions are $A \rightarrow Ba$, $A \rightarrow B$, $A \rightarrow a$, or $A \rightarrow \lambda$. Simplified: $A \rightarrow Bx$ or $A \rightarrow x$. At most one variable, always at the leftmost end.
• Regular Grammar: A grammar that is either entirely right-linear or entirely left-linear.

Example Right-Linear: $S \rightarrow abS | a$ generates $L((ab)^*a)$. Example Left-Linear: $S \rightarrow S_1 ab$, $S_1 \rightarrow S_1 ab | S_2$, $S_2 \rightarrow a$ generates $L(aab(ab)^*)$.

Equivalence: Regular Languages and Regular Grammars

Theorem: A language L is regular if and only if there exists a regular grammar G such that L = L(G).

Constructions:

• Right-Linear Grammar → NFA:
  • Create NFA states corresponding to grammar variables $V$, plus a dedicated final state $F_{new}$.
  • The NFA start state corresponds to the grammar start variable $S$.
  • For a production $A \rightarrow xB$ ($x=a_1\dots a_k$), create a path of $k$ transitions labeled $a_1, \dots, a_k$ from state $A$ to state $B$, possibly introducing intermediate states if $k>1$. If $x=\lambda$, add a λ-transition from $A$ to $B$.
  • For a production $A \rightarrow x$ ($x=a_1\dots a_k$), create a path labeled $a_1, \dots, a_k$ from state $A$ to the final state $F_{new}$. If $x=\lambda$, add a λ-transition from $A$ to $F_{new}$.
• DFA → Right-Linear Grammar:
  • Grammar variables $V$ correspond to DFA states $Q$.
  • Grammar terminals $T$ are the DFA alphabet Σ.
  • Grammar start variable $S$ corresponds to DFA start state $q_0$.
  • For each DFA transition $\delta(q_i, a) = q_k$, add the production $q_i \rightarrow a q_k$ to the grammar's productions $P$.
  • For each final state $q_f \in F$ in the DFA, add the production $q_f \rightarrow \lambda$ to $P$. (Alternatively, to avoid λ-productions directly, if $\delta(q_i, a) = q_f$ with $q_f \in F$, add both $q_i \rightarrow a q_f$ and $q_i \rightarrow a$).
• Left-Linear Grammars: They also generate exactly the regular languages. This can be shown by constructing an NFA that reads the input in reverse, simulating the left-linear derivation backwards, or by formally showing that $L(G_{left}) = (L(G_{right}))^R$ where $G_{right}$ is obtained by reversing the right-hand sides of $G_{left}$'s productions, and using the closure of regular languages under reversal.

This equivalence provides the final piece connecting the machine, expression, and grammatical views of regular languages.

Final Thoughts

We've significantly deepened our understanding of regular languages, formalizing their definitions via DFAs, NFAs, regular expressions, and regular grammars. We established their equivalence and explored key properties like closure, decidability, and the crucial Pumping Lemma for proving non-regularity. These concepts are the bedrock upon which more complex language families are built.