Non-Deterministic Finite Automata Study Notes
Non-Deterministic Finite Automata
Introduction
Presentation by Dr. Clare Martin from the School of Engineering, Computing and Mathematics, Oxford Brookes University
Date of presentation: 20th January 2026
References
Introduction to Languages and the Theory of Computation by John Martin
Introduction to the Theory of Computation (2012) by Michael Sipser (Sections 1.2-1.3)
Overview of Topics
Non-deterministic finite automata (NDFAs)
Conversion of NDFAs to deterministic finite automata (DFAs)
Kleene’s theorem
Context-free grammars
Regular grammars
Importance of nondeterminism in automata theory
1. Non-Deterministic Finite Automata
Definition
Nondeterministic finite automata (NDFAs) contain choices of movement (transitions) at any given state.
The machine has various potential moves at any point, making it impossible to predict which option will be chosen at any moment.
NDFAs can include 'free moves' labeled as λ (lambda), enabling transitions without reading an input symbol.
Examples of Operation
Example Language via Regular Expression: 1(0 + 1)∗0
Drawing an NDFA:
States and transitions:
State A (start state) --> 1 --> State B
State B --> {0,1} --> State C
State C --> 0 --> (Accept state)
Conversion to DFA:
State A --> 1 --> State B
State B --> 1 --> State B (loopback)
State B --> 0 --> State C
State C is an accept state.
Another Example
Language defined by the regular expression (ab + ba)∗
NDFA Representation:
States: A, C, B
Edges:
From A to B via 'a'
From A to D via λ (free move)
etc.
NDFA Behavior
An NDFA processes an input string symbol by symbol.
When at state X, if multiple transitions are available, nondeterministic choices can be made.
If a chosen path does not lead to an accept state, the automaton continues exploring other options until an accept state is found or all possibilities are exhausted.
The acceptance of a string can be confirmed even if the exact path taken remains unknown.
Inquiry on NDFA
Given another NDFA, determine its acceptance of strings:
Options include strings such as 1, 0, 10, 001.
Another Query Example
Given NDFA representation, which of the strings aba, abab, aaabbb, aaabb are accepted?
Conversion of NDFAs to DFAs
Every NDFA can be converted into a DFA.
Start by representing transition relations as a transition table.
For example let’s assume transitions are from states A to C to B based on various input symbols.
Transition Table Example
States: A, B, C
Example Transition Table:
| State | Input | Next State |
| A | 1 | B |
| B | 0,1 | C |
Drawing the Equivalent DFA
The DFAs retain the same start state as the original NDFA, with any state including the original accept state also being an accept state in the DFA.
2. Grammars
Overview of Languages and Grammar
Human languages follow grammatical constructions rules that evolve over time based on usage.
Computer programming languages also utilize formal grammars that dictate how various units (syntax) are structured.
Example Language and Grammar Definition
Given the language L = {ω ∈ {a, b}∗ | ω contains an even number of a’s}:
DFA Representation: transitions will occur between states based on the inputs.
Grammar with production rules:
S → aT | bS | λ
T → aS | bT
Derivations within Grammar
To verify a string's derivability, transformations based on production rules are executed.
Example: String 'baa' derived as:
S → bS → baT → baaS → baaλ = baa
Conversely, strings containing an odd number of 'a's, like 'ab', cannot reach a derivable state.
Formal Notation
If grammar G over an alphabet Σ enables the derivation of string t from string s, we denote it as s →∗ t.
The set L(G), which represents the language generated by grammar G, includes all ω ∈ Σ∗ where S →∗ ω.
Conventional Notations
Lowercase symbols represent terminal symbols; uppercase symbols represent non-terminals.
The left-hand side (LHS) of any production rule must hold at least one non-terminal.
The start symbol originates from the first rule.
Task: Grammar Creation
Given language L = {ω ∈ {a, b}∗ | ω contains exactly one a}, analyze and create a grammar accordingly.
Example Grammar
Consider G defined by:
S → aSb | λ
The set of derivable strings illustrates that the grammar can yield balanced pairs of 'a's and 'b's.
Hence, L(G) = {a^n b^n | n ≥ 0}.
Regular Grammars
A grammar is considered regular if all productions are structured as either right-linear (A → xB | C → y | D → λ) or left-linear (A → Bx | C → y | D → λ).
A common goal is to express all regular grammars in right-linear form.
Conversion of Right Linear Grammars to NDFAs
Every right-linear grammar generates a regular language, and hence can represent an NDFA.
Each terminal corresponds to transitions in the NDFA, and variables correspond to states.
For example, A → xB translates to NDFA arc from A to B with input x.
Accepting States in NDFAs
Production rules such as C → y determine states that do not correlate to any non-terminals.
Rules that imply λ transitions, such as D → λ, denote accepting states in the NDFA.
Summary of Grammar Conversions
Grammar rules can be systematically applied to facilitate conversions from NDFA to DFA.
3. Appendix
Additional Examples
Grammar for Arithmetic Expressions:
S → S + S | S - S | S * S | S / S | ( S ) | V
V → x | y | z
Derivation example: a derivation chain for the expression (x - y) * z.
Examples of Derivations for HTML Tags
Representing derivations for HTML tags and from a defined grammar.
A →
B → C | /C
C → hD | em
Summary of Key Points
The relationship between NDFAs and DFAs demonstrates the equivalence in expressive power while maintaining different operational modalities.
NDFAs allow for patterns and transitions that leverage nondeterminism, while DFAs operate with a single path throughout any input processing.
Understanding regular grammars and their conversion to automata is critical for parsing and understanding computational languages.