6.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).

6.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.

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 a finite state machine, each state represents what has occurred so far. For example, in the machine above, each state can be interpreted as follows:

6.8.1 Deterministic Finite Automaton (DFA)🔗

• A DFA is a finite-state machine in which each state and input symbol pair has exactly one next state.

• It reads input symbols one at a time and moves deterministically from one state to the next.

• An input string is accepted if the machine ends in a final state after processing all input symbols.

• Example:

  

• Formally, A deterministic finite automaton (DFA) is a 5-tuple (Σ, Q, q0, F, δ) where

  • Σ is an alphabet

  • Q is a nonempty set of states

  • q0 ∊ Q is the start state

  • F ⊆ Q is the set of final states

  • δ : Q x Σ → Q specifies the DFA’s transitions

  A DFA accepts s if it stops at a final state on s.

  For example, the DFA below can be represented as:

  

  Σ = {0, 1}
  Q = {S0, S1}
  q0 = S0
  F = {S1}
  δ =  {(S0,0,S0), (S0,1,S1),(S1,0,S0), (S1,1,S1) }

  We can also represent the transitions as a table, called transition table:

  States	0	1
  S0	S0	S1
  S1	S0	S1

6.8.2 Nondeterministic Finite Automaton (NFA)🔗

Below are the DFA and NFA that recognize the regular language described by the regular expression (a|b)*abb. When processing the string babaabb, the DFA follows a single deterministic path, whereas the NFA can follow multiple paths reaching different states. One of these paths reaches S3, resulting in the string being accepted.

Now, let us use the NFA below to accept the strings aba and ababa:

• aba: S0 → S1 → S2 → S0

• ababa: S0 → S1 → S2 (via epsilon) → S0 → S1 → S2 → S0

If we consume the input a on the transition from S2 to S0, the NFA will reject the string.

Due to the flexibility of NFAs, for a given regular language, an NFA is often smaller than the corresponding DFA. The DFA and NFA below both represent the same regular language, (ab|aba)*.

6.10.1 RE to NFA Examples🔗

• RE: ab

  

• RE: ab | cd

  

• RE: (ab)*

  

• RE: ab*|cd

  

6.11.1 Subroutines🔗

The algorithm relies on two helper functions:

• ε-closure(δ, p) — returns the set of all NFA states reachable from state p using only ε-transitions (zero or more), without consuming any input symbol. This captures all the "free moves" an NFA can make. When applied to a set of states Q, it is the union of ε-closures of each state in Q.

  ε-closure(δ, p) = {q | (p, ε,q) ∈ δ }

  ε-closure(δ, Q) = { q | p ∈ Q, (p, ε,q) ∈ δ }

  Notes: ε-closure(δ, p) always includes p

  Example:

  Then ε-closure(δ, A) = {A, B, C} — starting at A, we follow ε to B, then ε to C. D is not included because reaching it requires consuming input a, not an ε-transition.

• move(δ, Q, σ) — returns the set of all NFA states reachable from any state in set Q by reading exactly one symbol σ.

  move(δ, p, σ) = { q | (p, σ, q) ∈ δ}

  move(δ, Q, σ) = { q | p ∈ Q, (p, σ, q) ∈ δ}

  Note: move(δ, p, σ) = Ø when no transition (p, σ, q) ∈ δ exists for any q.

  Example:

  Using the same NFA from above:

  • move(δ, {B}, a) = {D} — B has an a-transition to D.

  • move(δ, {A, B}, a) = {D} — A has no a-transition; B reaches D, so the union is {D}.

  • move(δ, {A}, a) = Ø — A has no a-transition (only an ε-transition to B).

6.11.2 The Subset Construction Algorithm🔗

Let r0 = ε-closure(δ, q0)    ; DFA start state = ε-closure of NFA start state
add r0 to R                   ; R is the set of DFA states discovered so far
While ∃ an unmarked state r ∈ R:
  Mark r                      ; "marked" means we have processed this state
  For each σ ∈ Σ:
    Let m = move(δ, r, σ)    ; NFA states reachable from r by reading σ
    Let e = ε-closure(δ, m)  ; then take all free ε-moves
    If e ∉ R:
      Let R = R ∪ {e}         ; e is a new DFA state we haven't seen yet
    Let δ' = δ' ∪ {(r, σ, e)} ; record DFA transition r --σ--> e
Let Fd = { r | ∃ s ∈ r with s ∈ Fn }  ; DFA final states

6.11.3 Step-by-Step Explanation🔗

6.11.4 Why This Works🔗

The DFA state r represents "the NFA could currently be in any of these states." When the DFA reads symbol σ from state r, it moves to the state that represents all NFA states reachable by reading σ and then following ε-transitions. Because move and ε-closure capture every possible NFA path, the DFA faithfully simulates all NFA executions in parallel.

6.11.5 Complexity🔗

An NFA with n states can produce up to 2^n DFA states in the worst case (one for each subset of Q). In practice, most subsets are often unreachable, so the resulting DFA is typically much smaller.

6.11.6 NFA to DFA: Example 1🔗

NFA:

DFA:

6.11.7 NFA to DFA: Example 2🔗

NFA:

6.11.8 NFA to DFA: Example 3🔗

DFA:

6.11.9 NFA to DFA: Example 4🔗

6.11.10 NFA to DFA: Example 5🔗

NFA:

DFA:

6.11.11 NFA to DFA: Example 6🔗

Language: (a|b)*bb

NFA:

DFA:

6.13.1 Intuition🔗

Two states are distinguishable if there exists some string that leads to an accepting state from one but not the other. States that are not distinguishable by any input are equivalent and can be safely merged.

The key observation: if states x and y end up in different accept/non-accept outcomes on the same input, they must be in different equivalence classes.

6.13.2 Algorithm🔗

1. Construct the initial partition. Split all states into two groups: accepting states F and non-accepting states Q \ F.

2. Iteratively refine partitions. For each partition group and each symbol σ ∈ Σ, check whether all members transition into the same partition. If not, split the group into sub-groups that agree on their σ-destination partition.

3. Repeat until no partition can be split further (fixed point).

4. Build the minimal DFA. Each final partition becomes one state. Update transitions accordingly and remove any dead (unreachable) states.

Two states x and y end up in the same partition if and only if, for every σ ∈ Σ, δ(x, σ) and δ(y, σ) belong to the same partition.

6.13.3 Example: Minimizing a 4-State DFA🔗

Consider the DFA over Σ = {a, b} that accepts all strings ending in ’b’. A straightforward construction gives four states:

States B and D are both accepting; states A and C are both non-accepting. Apply the algorithm:

• Initial partition: P₀ = {{B, D}, {A, C}}.

• Refine {B, D}:

  • On a: B → C and D → C — both land in {A, C}. ✓

  • On b: B → B and D → D — both stay in {B, D}. ✓

  No split needed.

• Refine {A, C}:

  • On a: A → C and C → C — both in {A, C}. ✓

  • On b: A → B and C → D — both in {B, D}. ✓

  No split needed.

• Fixed point reached. Final partition: {{B, D}, {A, C}}.

Merging B and D into [BD], and A and C into [AC], yields the minimal 2-state DFA:

This minimal DFA correctly accepts exactly the strings over {a, b} that end in b, using only two states instead of four.

6.14.1 Example: Complementing a DFA🔗

Consider the DFA over Σ = {a, b} that accepts all strings containing "aa" as a substring. It has three states: q0 (no ’a’ seen), q1 (one ’a’ seen), and q2 (accepting sink — "aa" seen).

The DFA is already complete — every (state, symbol) pair has a defined transition, so no dead state needs to be added.

Applying the complement: flip q2 from accepting to non-accepting, and flip q0 and q1 from non-accepting to accepting:

The resulting DFA accepts exactly the strings over {a, b} that do not contain "aa" — i.e., strings where no two consecutive as appear. For example, ε, b, ab, bab, and aba are accepted, while aa, baa, and aab are rejected.

6.16.1 Languages🔗

1. Regular Languages

   • These are the simplest class of languages.

   • They can be described by regular expressions or recognized by finite state machines (FSMs).

   • Examples: strings matching simple patterns like (a|b)* or 0*1*.

2. Context-Free Languages

   • A broader class that includes languages generated by context-free grammars (CFGs).

   • Recognized by pushdown automata (PDAs), which are like FSMs but with a stack for memory.

   • Useful for describing programming languages’ syntax.

3. Recursive Languages

   • These languages are decided by Turing machines that always halt (deciders).

   • They are more general than context-free languages and include all languages for which membership can be decided algorithmically in finite time.

4. Recursively Enumerable Languages

   • This is the largest class in the diagram.

   • These languages can be recognized by Turing machines, but the machines may not halt for strings not in the language.

   • Includes all languages where membership can be semi-decided (if the string is in the language, the machine eventually accepts, but it may run forever otherwise).

5. Unrestricted Grammars

   • Grammars without restrictions generate recursively enumerable languages.

   • Equivalent in power to Turing machines.

6.16.2 Machines🔗

Here’s the role of each computational machine in the language hierarchy, explaining what kind of languages they recognize or decide:

1. Finite State Machines (FSMs)

   • Role: Recognize Regular Languages.

   • Capabilities:

     • Use a finite amount of memory (just states).

     • Can process input by moving between states based on input symbols.

     • Cannot remember counts or nested structures.

   • Examples: Pattern matching, simple token recognition in text.

2. Pushdown Automata (PDAs)

   • Role: Recognize Context-Free Languages.

   • Capabilities:

     • Like FSMs but equipped with a stack (a memory structure with LIFO behavior).

     • Can handle nested structures such as balanced parentheses, which FSMs cannot.

   • Examples: Parsing programming languages, arithmetic expressions.

3. Turing Machines (TMs)

   • Role: Recognize Recursively Enumerable Languages (semi-decision) and decide Recursive Languages (decision).

   • Capabilities:

     • Have an infinite tape as memory, can read/write and move left/right.

     • Model of general computation; can simulate any algorithm.

     • If the TM halts on every input, it decides a recursive language; if it may run forever on some inputs, it recognizes a recursively enumerable language.

   • Examples: Any computable function or algorithm, including those beyond context-free capabilities.

4. Unrestricted Grammars

   • Role: Generate all Recursively Enumerable Languages.

   • Capabilities:

     • No restrictions on production rules.

     • Equivalent in power to Turing machines for language generation.

   • Examples: Formal descriptions of the most general computable languages.

Summary of the role flow:

• FSMs → simplest, recognize regular patterns.

• PDAs → add memory (stack) to handle nested structures.

• Turing Machines → full computation power, handle any algorithmically definable language.

• Unrestricted Grammars → generate any language recognizable by a Turing machine.

This layered progression reflects how adding more memory or computational power enables recognition of increasingly complex languages.