5 Finite Automata🔗

5.1 Regular Expressions🔗

At a fundamental level, a regular expression represents a set of strings that match the pattern, and viewing them this way provides a crucial perspective. This viewpoint will guide our approach to designing and implementing effective regular expression matching.

5.2 Alphabet, String, and Language🔗

First, let’s review some basic concepts.

Alphabet: An alphabet is a finite set of symbols, typically denoted by Σ (the Greek letter sigma). It defines the basic building blocks used to form strings in formal languages.

Ø is the empty set (it has no elements). Ø ≠ {ε} and Ø ≠ ε — these are distinct concepts.

Language: A language L is a set of strings formed from symbols of a given alphabet Σ. In other words, once we define an alphabet, we can describe a language as any collection of finite strings built using those symbols.

Formally:

L ⊆ Σ*

Here, Σ* (read “Sigma star”) represents the set of all possible strings, including the empty string ε, that can be constructed using symbols from Σ.

5.2.1 The Set of All Valid (Runnable) OCaml Programs🔗

Consider the language of all valid OCaml programs — that is, every possible sequence of characters that forms a syntactically correct and executable OCaml program. Each valid program (for example, print_endline "Hello";;) can be viewed as a string over a suitable alphabet that includes letters, digits, punctuation, and symbols used in the OCaml language.

This collection of all syntactically correct programs forms a language in the formal sense — a set of strings over an alphabet that satisfy certain grammatical rules (in this case, the OCaml grammar).

Later in the course, we will learn how such programming language grammars can be formally specified using tools more expressive than regular expressions. While regular expressions are powerful for describing many kinds of string patterns (like tokens, identifiers, or numbers), they are not sufficient to describe the full syntax of programming languages such as OCaml. To handle nested structures (like parentheses, let-bindings, or function definitions), we need more powerful formalisms such as context-free grammars (CFGs).

5.3 Operations on Languages🔗

Here is an Example:

Let L1 = { a, b }, L2 = { 1, 2, 3 } (and Σ = {a,b,1,2,3})

L1L2: { a1, a2, a3, b1, b2, b3 }

L1 ∪ L2: { a, b, 1, 2, 3 }

L1* : { ε, a, b, aa, bb, ab, ba, aaa, aab, bba, bbb, aba, abb, baa, bab, … }

5.4 Regular Languages🔗

In theoretical computer science and formal language theory, a regular language is a formal language that can be described using a regular expression (RE).

Regular expressions represent regular languages. They are not merely a convenient tool for describing string patterns — they have a precise mathematical meaning. Each regular expression corresponds to a specific regular language, which is the set of all strings that match the expression.

In short, regular expressions provide a formal notation for defining regular languages.

When we write a regular expression such as:

(a∣b)*ab

it denotes the language consisting of all strings over the Σ ={a,b} that end with “ab”.

While regular expressions and finite automata are powerful, not every language can be described by a regular expression. Some languages are simply too complex to be captured by the limited memory of a finite automaton.

Despite these limits, regular expressions remain extremely useful, especially in lexical analysis — the first stage of program compilation where the source code is broken into tokens. Tools like lex, flex, and many modern regex libraries use regular expressions to describe and recognize these patterns.

5.5 Semantics of Regular Expressions🔗

Regular expressions apply operations to symbols to generate a set of strings, also known as a language. (A formal definition will follow.)

If a string s ∈ L, where L is the language generated by a regular expression r, we say that r accepts, describes, or recognizes the string s.

Think of every string containing a distinct, hidden symbol at its start and at its end – these are written ^ and $

5.6 Implementing Regular Expressions🔗

Regular expressions can be implemented by converting them into an equivalent finite automaton — a computational model that recognizes exactly the same set of strings described by the expression.

In essence, a finite automaton serves as a machine that reads an input string symbol by symbol and determines whether it belongs to the regular language defined by the regular expression.

Simply put, to determine whether an input string matches a pattern, we first build a small machine based on the pattern. Then, we feed the string into the machine — if the machine accepts it, the string matches; if it rejects it, the string does not match.

Thus, every regular expression corresponds to a finite automaton, and every finite automaton defines a regular language.

5.6.1 Finite State Machine🔗

A Finite-State Machine (FSM) — also known as Finite-State Automaton (FSA), Finite Automata, or simply a State Machine — is a mathematical model of computation. It represents an abstract machine that can be in one and only one state at any given time.

In class, the terms FSM, FSA, and FA are all used to refer to a finite-state machine.

The machine can change from one state to another in response to certain inputs. Such a change is called a transition.

In summary, the FSM processes inputs one at a time, moving through states according to its transition rules. For example, consider the finite-state machine shown below:

• States are represented by circles, and transitions are represented by arrows.

• Set of states: {S0, S1}

• Start state: S0. — The state where the automaton begins computation. It is indicated by an incoming arrow with no origin. There is only one start state.

• Final (accepting) state: S1 — denoted by the double circles. There may be zero or multiple final states in general. Any state, including the start state, can be final

• Input symbols: {0,1}

• Transitions: {(S0, 0, S0), (S0, 1, S1), (S1, 1, S1), (S1, 0, S0)} - Each transition specifies how the automaton moves from one state to another when reading a particular input symbol.

The FSM’s next state depends only on its current state and the current input symbol, not on the sequence of inputs that led to the current state. In other words, the machine has no memory of past inputs beyond the current state it is in.

Now, let’s explain how a Finite Automaton processes an input string.

• The machine begins in the start (initial) state.

• It processes the input string symbol by symbol until the end of the string is reached:

  • Read the next symbol σ ∈ Σ from the string.

  • Follow the transition edge labeled with σ to the next state.

• After the entire string has been read, the string is accepted if the automaton is in a final (accepting) state; otherwise, it is rejected.

After processing all input symbols, the machine ends in S1, which is a final (accepting) state. Therefore, the input string “0 0 1 0 1 1” is accepted by the FSM.

Thus, the input string “0 0 1 0 1 0” is rejected by the FSM.

From the FSM above, notice that state S3 has no outgoing transitions. This means that once the machine enters S3, it cannot leave. Such a state is called a dead state.

In some cases, we simplify an FSM by omitting dead states. If a transition is not explicitly defined, it is assumed to lead to a dead state.

Based on the examples, what do you think is the language recognized by the FSM above?

The FSM accepts all strings that can be generated by the regular expression a*b*c*.

5.7 FSM Exercises🔗

Define an FSM over Σ = {0,1} that accepts strings with an odd number of 1s.

Define an FSM over Σ = {a,b} that accepts strings containing an even number of a’s and any number of b’s

Define an FSM over Σ = {0,1} that accepts strings containing two consecutive 0s followed by two consecutive 1s.

Define an FSM over Σ = {0,1} that accepts strings END with two consecutive 0s followed by two consecutive 1s.

Define an FSM over Σ = {0,1} that accepts strings containing an odd number of 0s and odd number of 1s.

5.8 DFA and NFA🔗

5.9 Reducing Regular Expressions to NFAs🔗

Given a regular expression A, our goal is to construct an equivalent NFA, denoted as ⟨A⟩ = (Σ, Q, q₀, F, δ).

Regular expressions are defined recursively from primitive RE languages. Each component of a regular expression corresponds to a small NFA fragment, and these fragments are combined according to the operators used in the expression.

Throughout the construction, we maintain the invariant |F| = 1, meaning that each NFA we build will have exactly one final state.

We will define <A> for base cases: σ , ε , ∅ where σ is a symbol in Σ and and for inductive cases: AB, A|B, A*

Recall: NFA is (Σ, Q, q0, F, δ)
  where 
    Σ is the alphabet
    Q is set of states
    q0 is starting state
    F is set of final states
    δ is transition relation

For a single symbol σ, we construct an NFA with two states: the start state and the final state. The start state transitions to the final state on input σ.

<σ> = ({σ}, {S0, S1}, S0, {S1}, {(S0, σ, S1)} )
      ( Σ,      Q,    q0,  F,        δ        )

Base case: ε

To recognize ε, the empty string, we create an NFA with a single state that serves as both the start and the final state.

<ε> = (∅, {S0}, S0, {S0}, ∅)

Base case: ∅ To represent the empty set (∅), we construct an NFA with two states: a start state and a final state. There are no transitions between them, so the final state is unreachable from the start state. This automaton accepts no strings.

<∅> = (∅, {S0, S1}, S0, {S1}, ∅)

Now, let us look at the inductive cases.

Concatenation

Given a machine A and B, we want to build a concatenation AB.

<A> =  (ΣA, QA, qA, {fA}, δA)
<B> =  (ΣB, QB, qB, {fB}, δB)

We construct the new NFA by adding an ε-transition from the final state of A to the start state of B. The start state of the combined NFA is the start state of A, and the final state is the final state of B.

<A> =  (ΣA, QA, qA, {fA}, δA)
<B> =  (ΣB, QB, qB, {fB}, δB)
<AB> =  (ΣA ∪ ΣB, QA ∪ QB, qA, {fB}, δA ∪ δB ∪ {(fA,ε,qB)} )

Union

Given a machine A and B, we want to build a union A|B.

<A> =  (ΣA, QA, qA, {fA}, δA)
<B> =  (ΣB, QB, qB, {fB}, δB)

<A|B> =  (ΣA ∪ ΣB, QA ∪ QB ∪ {S0,S1}, S0, {S1},
         δA ∪ δB ∪ {(S0,ε,qA), (S0,ε,qB), (fA,ε,S1), (fB,ε,S1)})

Closure (Kleene Star)

Given a machine A and B, we want to build A*.

<A> =  (ΣA, QA, qA, {fA}, δA)

<A*> =  (ΣA, QA ∪ {S0,S1}, S0, {S1},
         δA ∪ {(fA,ε,S1), (S0,ε,qA), (S0,ε,S1), (S1,ε,S0)})

RE to NFA Example

RE: ab*|cd

5.10 Subset Construction (NFA to DFA Conversion)🔗

where p is an NFA state.

5.10.1 Subset Construction Algorithm🔗

Let r0 = e-closure(δ, q0)
add r0 to R
While ∃ an unmarked state r ∈ R:
  Mark r
  For each σ ∈ Σ
     Let m = move(delta, r, σ)
     Let e = e-closure(δ, m)
     If e ∉ R
        Let R = R ∪ {e}
     Let δ' = δ'∪ { r, σ, e }
 Let F = { r ∣ ∃ s ∈ r  with  s ∈ F n }

5.10.2 Example 1🔗

NFA:

DFA:

5.10.3 Example 2🔗

NFA:

5.10.4 Example 3🔗

DFA:

5.10.5 Example 4🔗

5.10.6 Example 5🔗

NFA:

DFA:

5.10.7 Example 6🔗

Language: (a|b)*bb

NFA:

DFA: