Thomson's Construction

Thomson’s construction (also called Thompson’s construction) is a method for converting a regular expression into a non-deterministic finite automaton (NFA). It is a fundamental technique used in compiler design and automata theory, especially for implementing regular expression matching.

🧠 Why Thomson’s Construction?

  • It systematically builds an NFA from any regular expression.

  • The resulting NFA accepts the same language as the regular expression.

  • This NFA may include ε-transitions (transitions that consume no input).

  • It is simple and suitable for implementation in regex engines and lexical analyzers.

📘 Basic Idea

Thomson's construction defines how to build small NFAs for basic symbols and how to combine them using:

  • Concatenation

  • Union (| or +)

  • Kleene Star (*)

Each construction has a fixed pattern and introduces new start and accept (final) states.

🔨 Building Blocks

Let’s define the NFA for the following regular expression components:

1. Single Symbol – a



2. Epsilon (ε)

🔧 Operators

3. Concatenation (R1 · R2)

If we have two NFAs:

  • NFA for R1: from q1 to q2

  • NFA for R2: from q3 to q4

Then for R1R2:



4. Union (R1 + R2 or R1 | R2)

Create a new start and final state, and connect them using ε-transitions:

  • ε from new start to R1 and R2's start

  • ε from R1 and R2’s final states to new final

5. Kleene Star (R)*

Create a new start and final state:

  • Add ε-transition from:

    • new start to R's start

    • R's final to new final

    • R's final back to R's start

    • new start directly to final (for ε)

✅ Advantages of Thompson's Construction

  • Straightforward and mechanical

  • Resulting NFA is guaranteed to be correct and accept the regular language

  • The construction always results in an NFA with a number of states linear in the size of the regular expression

⚠️ Disadvantages

  • The resulting NFA has ε-transitions, which are not efficient for direct simulation

  • Need ε-closure computation for NFA simulation or conversion to DFA

  • The NFA may be non-deterministic, so not ideal for some applications unless converted to DFA

🧾 Use in Practice

  • Used in lexical analyzers (e.g., Lex)

  • Forms the basis for converting regex into state machines in compilers

  • Forms the first step in converting regular expressions to DFA (via ε-NFA → NFA → DFA)

🔁 Example: Regular Expression a(a + b)*ab

🔁 Example: Regular Expression a+b+ab



🔁 Example: Regular Expression identifiers: letter (letter+digit)*


🔁 Example: Regular Expression identifiers: (0+1)*1(0+1)

🔁 Example: Regular Expression identifiers: (a+b)*a




Comments

Post a Comment

Popular posts from this blog

Theory Of Computation PCCST302 KTU Semester 3 BTech 2024 Scheme

About Me Course Details and Syllabus Module-1 Foundations of Finite Automata Motivation-Computability Need for Mathematical Modelling and automata Introducing automata     on-off switch     coffee vending machine Alphabet, Strings, and Languages Formal Definition of Finite Automata Deterministic Finite Automata - DFA Dead state in DFA Categories of DFA      Category 1: Accept Only the Given Input      Category 2: Starts and ends with      Category 3: Contains substring      Category 4: Specific length     Category 5: Divisibility ( Binary Numbers) Examples  DFA( University Questions) DFA Implementation C Program Non Deterministic Finite Automata - NFA Epsilon NFA  (∈-NFA) Examples NFA( University Questions) Regular Languages Epsilon Closure of NFA Eliminating Epsilon Transitions from NFA Epsilon Free NFA to DFA Conversion - Examples DFA state minimization DFA vs NFA Applications of Fini...
Read more

Non deterministic Finite Automata NFA

Image
  🤖 Formal Definition of NFA An NFA (Nondeterministic Finite Automaton) is a theoretical machine used to recognize regular languages , like a DFA, but it allows multiple transitions for the same input or even no input at all (ε-transitions) . 📘 An NFA is defined as a 5-tuple : M = ( Q , Σ , δ , q 0 , F ) M = (Q, \Sigma, \delta, q_0, F) Where: Symbol Description Q Q A finite set of states Σ \Sigma A finite set called the input alphabet δ \delta The transition function : δ : Q × ( Σ ∪ { ε } ) → 2 Q \delta: Q \times (\Sigma \cup \{\varepsilon\}) \rightarrow 2^Q  (a set of states) q 0 q_0 ​ The initial state , q 0 ∈ Q q_0 \in Q F F The set of accepting states , F ⊆ Q F \subseteq Q 💡 Key Differences from DFA: DFA NFA Only one transition per input                Multiple transitions possible No ε-transitions                ε-transitions allowed Deterministic      ...
Read more

Example DFAs University Questions

Image
 Even number of a's ab as a substring empty set All strings except the empty set over the alphabet {0.1} Accept empty string and 0 every odd position of the string w is 1 begins with 1 ends with 0 {w| w contains at least 3 ones }  {w|w contains the substring 0101 ie; w=x0101y for some x and y} {w|w has length at least 3 and its third symbol is a zero} {w|w starts with 0 and has odd length , or starts with 1 and has even length } construct a DFA which accepts the language L = {a^N | N ≥ 1} String in {a,b} with odd number of a's starting with 01 over the alphabet [1,0} Strings ending with abc Program to build a DFA that checks if a string ends with "01" or "10" build a DFA to accept strings that start and end with same character build DFA that starts and end with 'a' from input (a, b) build a DFA that accepts strings starting and ending with different character DFA of a string starting with 0 and ends with 10? DFA of a string of a's and b's  st...
Read more