Regular Languages & Finite Automata: Definitions, Models & Conversions

TAKEAWAYS:

• Regular languages are exactly those recognized by finite automata (DFA/NFA/ε-NFA) and defined by regular expressions, forming the lowest level of Chomsky hierarchy.
• DFAs are deterministic (one transition per input symbol) and always accept/reject, while NFAs may have multiple transitions and ε-transitions (silent moves).
• ε-NFAs extend NFAs with ε-transitions (no input symbol) and require ε-closure computation for language recognition.
• Conversion methods include:
  • Regex → NFA (Thompson’s construction),
  • NFA → DFA (subset construction),
  • DFA minimization (table-filling algorithm).
• Closure properties (union, concatenation, Kleene star) preserve regularity, while pumping lemma (next unit) proves non-regularity.
• Applications span lexical analysis (compilers), protocol validation, and real-world systems like eSewa’s transaction validation (DFA for input formats) and Khalti’s fraud detection (NFA for pattern matching).

1. Regular Languages: Definition and Examples

A regular language is any language over an alphabet Σ that can be:

• Defined by a regular expression (regex),
• Recognized by a finite automaton (DFA/NFA/ε-NFA),
• Generated by a right-linear grammar.

Key Properties

classDiagram
    class RegularLanguage {
        +Defined by: Regex
        +Recognized by: DFA/NFA/ε-NFA
        +Generated by: Right-linear grammar
        +Closure under: Union, Concatenation, Kleene star, Intersection, Complement, Homomorphism
    }
    class Regex {
        +Operators: Union (|), Concatenation (), Kleene star (*)
        +Example: (a+b)*abb
    }
    class FiniteAutomaton {
        +Types: DFA, NFA, ε-NFA
        +States: Finite, Initial, Final
        +Transitions: Deterministic (DFA) or Non-deterministic (NFA)
    }
    RegularLanguage --> Regex
    RegularLanguage --> FiniteAutomaton

Example: Regex for Even-Length Binary Strings Ending with 01

Language: $L=\{w\in \{0,1{\}}^{\ast }\mid |w|\text{ is even and }w\text{ ends with }01\}$. Regex: $$L=(0+1{)}^{\ast }01\cap (0+1{)}^{2k}\text{(even length)}$$ Simplified: $$L=(0+1{)}^{\ast }01(0+1{)}^{\ast }01\text{(but this overcounts)}$$ Correct Regex: $$L=(0+1{)}^{\ast }01(0+1{)}^{2k}\text{is not directly expressible; use DFA instead.}$$ Worked Example: For $L=\{w\mid w\text{ starts with odd digit and ends with even digit}\}$ over $\Sigma =\{1,2,\dots ,9\}$:

• Odd digits: $\{1,3,5,7,9\}$, even digits: $\{2,4,6,8\}$.
• Regex: $$L=[13579][2468]([123456789]\ast )[2468]$$ Trace: A string like 34568 is accepted (starts with 3, ends with 8).

2. Finite Automata: Types and Transitions

Finite automata process strings by moving between states via transitions triggered by input symbols.

Types of Finite Automata

DFA vs. NFA: Key Differences

flowchart TD
    A["DFA"] -->|"Single transition per input"| B["Deterministic"]
    A -->|"No ε-transitions"| C["Simpler to minimize"]
    D["NFA"] -->|"Multiple transitions per input"| E["Non-deterministic"]
    D -->|"ε-transitions allowed"| F["More expressive"]
    G["ε-NFA"] -->|"Extends NFA with ε-moves"| H["Used for grammar parsing"]

Example: DFA for Strings Ending with 01

States: $Q=\{q_0,q_1,q_2\}$, where:

• $q_0$: initial state,
• $q_1$: saw 0,
• $q_2$: accepting state (saw 01).

Transitions:

• From $q_0$: 0 → $q_1$, 1 → $q_0$.
• From $q_1$: 1 → $q_2$, 0 → $q_1$, 1 → $q_1$.
• From $q_2$: any input → $q_0$ (reset).

Trace for 0101:

1. Start at $q_0$.
2. Read 0: $q_0\to q_1$.
3. Read 1: $q_1\to q_2$ (accept).
4. Read 0: $q_2\to q_0$.
5. Read 1: $q_0\to q_0$. Result: Rejected (last 1 doesn’t complete 01).

3. ε-NFAs and ε-Closure

An ε-NFA allows ε-transitions (moves without consuming input). The ε-closure of a state $q$ is the set of states reachable from $q$ via ε-transitions.

ε-Closure Example

ε-NFA for $L=\{w\mid w\text{ contains }01\}$:

stateDiagram-v2
    [*] --> q0
    q0 --> q1 : 0/ε
    q1 --> q2 : 1
    q2 --> [*] : ε
    q0 --> q0 : 1
    q1 --> q1 : 0

ε-Closure of $q_0$: $\{q_0,q_1\}$ (since $q_0\stackrel{ϵ}{\to }{q}_1$).

Trace for ε (empty string):

1. Start at $q_0$.
2. ε-closure: $\{q_0,q_1\}$.
3. From $q_1$, no input → accept via ε-transition to final state.

4. Conversion Methods

A. Regex to NFA (Thompson’s Construction)

Rules:

1. Concatenation: $R\cdot S$ → Connect $R$’s final to $S$’s initial.
2. Union: $R|S$ → Add a new start/end state with ε-transitions to $R$ and $S$.
3. Kleene Star: $R^{\ast }$ → Loop from final state back to initial via ε-transition.

Example: Convert $(a+b)\ast ab\ast$ to NFA.

stateDiagram-v2
    [*] --> q0
    q0 --> q1 : a/ε
    q0 --> q2 : b/ε
    q1 --> q0 : ε
    q2 --> q0 : ε
    q0 --> q3 : a
    q3 --> q4 : b
    q4 --> [*] : ε
    q3 --> q4 : b

B. NFA to DFA (Subset Construction)

Steps:

1. Start with the ε-closure of the NFA’s initial state.
2. For each subset of states and input symbol, compute the next subset via transitions.
3. Mark subsets containing final states as accepting.

Example: Convert the above NFA to DFA.

5. DFA Minimization (Table-Filling Algorithm)

Goal: Reduce states while preserving language recognition. Steps:

1. Initialize a table of state pairs.
2. Mark pairs where one state is final and the other isn’t.
3. For unmarked pairs, check if transitions lead to marked pairs. If yes, mark them.
4. Repeat until no new pairs are marked.
5. Merge unmarked pairs into a single state.

Example: Minimize the DFA from the previous table.

flowchart TD
    A["q0"] -->|"a"| B["q0,q1"]
    A -->|"b"| C["q0,q2"]
    B -->|"a"| D["q0,q1,q3"]
    B -->|"b"| E["q0,q1"]
    C -->|"a"| E
    C -->|"b"| C
    D -->|"a"| D
    D -->|"b"| F["q0,q1,q4"]
    F -->|"a"| E
    F -->|"b"| F

Result: Merge $\{q_0\}$ and $\{q_0,q_1\}$, etc., to get a 3-state DFA.

In the Real World

1. eSewa Transaction Validation

   • Idea Used: DFA for input format validation.
   • How: eSewa’s web form for bill payments uses a DFA to ensure user inputs (e.g., phone number, amount) match expected patterns (e.g., 10-digit Nepali number, valid currency). Invalid inputs (e.g., abc123 for amount) are rejected immediately.

2. Khalti Fraud Detection

   • Idea Used: NFA for suspicious pattern matching.
   • How: Khalti’s backend scans transactions for fraud patterns (e.g., rapid small-value transfers). An NFA with ε-transitions models sequences like:

     [high-value transaction] →ε→ [multiple low-value transactions] →ε→ [withdrawal]
     

     If the NFA reaches an accepting state, the transaction is flagged for review.

3. Daraz Order Queue Management

   • Idea Used: Finite automaton for order states.
   • How: An order’s lifecycle (placed → processed → shipped → delivered) is modeled as a DFA where each state transition depends on input events (e.g., "payment received," "warehouse update"). Example:

     State: Placed → Input: Payment → State: Processed
     

     This ensures no order is shipped before payment.

4. NTC’s Traffic Light Control (Simplified)

   • Idea Used: DFA for signal timing.
   • How: A DFA controls traffic lights at a junction with states:
     • Red → Green (after timer),
     • Green → Yellow (after countdown),
     • Yellow → Red. Inputs are time signals, and the DFA ensures no two lights are green simultaneously.

6. Closure Properties of Regular Languages

Regular languages are closed under:

• Union: $L_1\cup L_2$ is regular if $L_1,L_2$ are.
• Concatenation: $L_1\cdot L_2$ is regular.
• Kleene Star: $L^{\ast }$ is regular.
• Intersection: $L_1\cap L_2$ is regular (via DFA product construction).
• Complement: ${\Sigma }^{\ast }\setminus L$ is regular.
• Homomorphism: $h(L)$ is regular for any homomorphism $h$.

Example: Prove $L=\{w\mid w\text{ has even number of }0\text{s}\}$ is regular.

• Use DFA with states $\{q_{\text{even}},q_{\text{odd}}\}$:
  • $q_{\text{even}}\stackrel{0}{\to }{q}_{\text{odd}}$, $q_{\text{even}}\stackrel{1}{\to }{q}_{\text{even}}$,
  • $q_{\text{odd}}\stackrel{0}{\to }{q}_{\text{even}}$, $q_{\text{odd}}\stackrel{1}{\to }{q}_{\text{odd}}$.
• Accepting state: $q_{\text{even}}$.

7. Non-Regular Languages (Preview)

While regular languages are powerful, some are not regular, proven via the pumping lemma (next unit). Examples:

1. $L=\{a^n{b}^n\mid n\ge 0\}$: Requires unbounded memory (stack).
2. $L=\{w\mid w\text{ has equal number of }0\text{s and }1\text{s}\}$: Needs counting.
3. $L=\{a^n\mid n\text{ is prime}\}$: No finite automaton can "know" primality.

Why?

• Finite automata have no memory beyond their current state.
• Languages requiring counting or nested structures need pushdown automata (PDA) or Turing machines.

Exam Tip

1. For Regex Problems:

   • Always verify your regex with small strings (e.g., test $(a+b)\ast ab\ast$ on a, ab, abb).
   • Use parentheses to group operations correctly (e.g., $a(b|c)\ast$ ≠ $ab|ac$*).

2. For DFA/NFA Construction:

   • Label all states (initial, final, intermediate).
   • For ε-NFAs, explicitly show ε-transitions and compute ε-closures in traces.
   • Minimization: Use the table-filling method step-by-step; partial credit is given for correct marking.

3. For Proofs (e.g., Non-Regularity):

   • Assume $L$ is regular and derive a contradiction using the pumping lemma.
   • Structure your proof:
     1. Assume $L$ is regular.
     2. Let $p$ be the pumping length.
     3. Pick a string $w$ longer than $p$ in $L$.
     4. Pump $w$ to get $w^{\prime }\notin L$, contradicting regularity.

4. Common Pitfalls:

   • Off-by-one errors in regex (e.g., $a^n$ vs. $a^{n+1}$).
   • Forgetting ε-transitions in NFA/ε-NFA constructions.
   • Incorrect final states in minimized DFAs (always verify with test strings).

5. Real-World Tie-Ins:

   • Examiners love questions like: "Design a DFA to validate Ncell’s 10-digit phone number format (must start with 98, followed by 8 digits)." Solution: Use a DFA with states for each digit position, rejecting invalid prefixes (e.g., 97...).

Visual Summary:

mindmap
  root((Regular Languages))
    Regex
      Operators: Union, Concatenation, Kleene star
      Example: (a+b)*abb
    DFA
      Deterministic
      Minimizable
      Example: Even-length strings
    NFA
      Non-deterministic
      ε-transitions
      Example: Pattern matching
    ε-NFA
      Extends NFA with ε-moves
      ε-closure computation
    Closure Properties
      Union, Intersection, Complement
    Non-Regular
      Pumping lemma
      Example: {a^n b^n}