Deterministic Finite Automata and Regular Languages

Alphabet (Σ)

In formal language theory, an alphabet is any finite, non-empty set of symbols. Common examples include the binary alphabet {0, 1}, the Latin alphabet {a, b, ..., z}, or a set of digits and operators {0,1,...,9, +, ×}. The alphabet defines the basic building blocks for strings.

String over an Alphabet

A string over an alphabet Σ is a finite sequence of symbols chosen from Σ. Examples: 0100101 over {0,1}, abba over {a,b,c}. The length of a string s, denoted #(s), is the number of symbols it contains (e.g., #(abba) = 4). The unique string of length 0 is the empty string, denoted by ε (epsilon).

Σ* (Kleene Star)

The notation Σ* (Kleene star) represents the infinite set of all possible strings that can be formed using symbols from the alphabet Σ, including the empty string ε. For example, if Σ = {a}, then Σ* = {ε, a, aa, aaa, ...}.

Concatenation of Strings

The concatenation of two strings s and t, written as st, is the string formed by appending t to the end of s. Example: if s = abb and t = ba, then st = abbba. The empty string is the identity element for concatenation: εs = sε = s.

Language (Formal Definition)

A language L over an alphabet Σ is any subset of Σ*. In other words, it is a set of strings, where each string is composed of symbols from Σ. Examples: L1 = {a, aa, aaa} over {a}; L2 = {w ∈ {0,1}* | w contains an even number of 0s}.

DFA Components: Q, Σ, s, F

A DFA is a 5-tuple M = (Q, Σ, δ, s, F).

• Q: Finite set of states.

• Σ: Input alphabet.

• s ∈ Q: The start state.

• F ⊆ Q: Set of final (accepting) states.

DFA Transition Function (δ)

The transition function δ is the core of a DFA: δ: Q × Σ → Q. For a current state q and input symbol σ, δ(q, σ) = q' uniquely determines the next state q'. This makes the automaton deterministic. Notation: q --σ--> q'.

DFA Acceptance - Pebble Method

To check acceptance: place a "pebble" on the start state. Read the input left to right. For each symbol, move the pebble along the arrow with that label. After the last symbol, if the pebble is on a final state, the string is accepted; otherwise, rejected.

DFA Acceptance - Formal Definition

A DFA M accepts string x = σ1σ2...σn if a sequence of states r0, r1, ..., rn exists where: 1) r0 = s, 2) δ(ri-1, σi) = ri for all i, and 3) rn ∈ F. The language L(M) is the set of all accepted strings.

Regular Language Definition

A language L is a regular language if there exists some DFA M such that L = L(M). In essence, L is regular if a DFA can be built to accept exactly its strings.

Closure under Union

Regular languages are closed under union. If L1 and L2 are regular, then L1 ∪ L2 (strings in L1 OR L2) is also regular. This can be proven using constructions like the product of automata or by using non-deterministic finite automata (NFA).

Closure under Intersection

Regular languages are closed under intersection. If L1 and L2 are regular, then L1 ∩ L2 (strings in L1 AND L2) is also regular. The standard proof uses the product construction to build a DFA that simulates both original DFAs in parallel.

Closure under Complement

Regular languages are closed under complement. If L is regular over alphabet Σ, then its complement ~L = Σ* - L (all strings over Σ not in L) is regular. Proof: take a DFA for L, swap its final and non-final states.

Product Construction (Purpose)

The product construction is a method to combine two DFAs, M1 and M2, to create a new DFA that accepts the intersection of their languages, L(M1) ∩ L(M2). It works by simulating both automata running in parallel.

Product Construction (Formal Build)

Given M1=(Q1,Σ,δ1,s1,F1) and M2=(Q2,Σ,δ2,s2,F2), their product DFA M3 is:

• States: Q1 × Q2 (ordered pairs).
• Start: (s1, s2).
• Transitions: δ3((q1,q2), σ) = (δ1(q1,σ), δ2(q2,σ)).
• Final States: F1 × F2 (both components must be final in their original DFAs).

Lexical Analysis (Role of FAs)

In compiler design, lexical analysis (scanning) is the first phase. It reads the source code character by character and groups characters into lexical tokens (e.g., keywords, identifiers, numbers). This process is typically implemented using a DFA defined by regular expressions.

Parsing (Role in Compilation)

Parsing is the second major phase in compilation, following lexical analysis. It takes the stream of tokens from the scanner and analyzes their grammatical structure according to the rules of the programming language, producing an abstract syntax tree. This requires more power than FAs and uses context-free grammars (CFGs) and pushdown automata (PDA).