Theory of Computation · Unit 2 · 8 hrs
Introduction to Finite Automata
Exam-focused notes for Introduction to Finite Automata (Theory of Computation, CSC262): what the TU syllabus asks and how it has actually been tested, with 11 solved past questions from this unit.
What this unit covers
- Introduction to Finite Automata
- Introduction of Finite State Machine
- Deterministic Finite Automata (DFA)
- Notations for DFA
- Language of DFA
- Extended Transition Function of DFA
- Non-Deterministic Finite Automaton (NFA)
- Notations for NFA
- Language of NFA
- Extended Transition
- Equivalence of DFA and NFA
- Subset-Construction
- Method for reduction of NFA to DFA
- Theorems for equivalence of Language accepted by DFA and NFA
- Finite Automaton with Epsilon Transition (ε - NFA)
- Notations for ε - NFA
- Epsilon Closure of a State
- Extended Transition Function of ε – NFA
- Removing Epsilon Transition using the concept of Epsilon Closure
- Equivalence of NFA and ε –NFA
- Equivalence of DFA and ε – NFA
- Finite State Machines with output: Moore machine and Mealy Machines
Epsilon Closure of a State
Define ε\varepsilonε-closure of a state. Differentiate between Moore and Mealy machine. [5]
--- Definition: ε-closure of a state is the set of all states that can be reached from a particular state without reading any input symbol, i.e., by reading only ε (epsilon) transitions. Formally, for a state q, the ε-closure(q) includes: - The state q itse...
Full solved answer →Explain the ε\varepsilonε-closure of states on an ε\varepsilonε-NFA with suitable examples. [5]
ε-closure of a state q is the set of all states that can be reached from state q by following zero or more ε (epsilon) transitions, without consuming any input symbol. Formally: ε-closure(q) = { p ∈ Q p is reachable from q using only ε-transitions } Key poi...
Full solved answer →Deterministic Finite Automata
Design the DFA that accepts binary string ending with '00' and show its extended transition function for the string 111000. [5]
- Alphabet: $\Sigma = \{0, 1\}$ - Language: $L = \{w \in \Sigma^ \mid w \text{ ends with } 00\}$ - Test string for extended transition function: $111000$ No numeric data missing; the problem is fully solvable. We track the relevant suffix (last two symbols)...
Full solved answer →Design a DFA that accepts single line and multi-line comments of the C-Language. [5]
- Single-line comment: begins with //, terminates at newline \n. - Multi-line comment: begins with /, terminates at first /. - Alphabet symbols needed: /, , \n, and other (any character that is not /, , or \n). No numeric matrices are involved; this is a co...
Full solved answer →Give the formal definition of DFA. Construct a DFA accepting all strings of {0, 1} with even number of 0's and even number of 1's. [5]
A Deterministic Finite Automaton (DFA) is a 5-tuple: $$M = (Q, \Sigma, \delta, q0, F)$$ Where: Component Description ------------------------ $Q$ A finite, non-empty set of states $\Sigma$ A finite set of input symbols (alphabet) $\delta$ A transition funct...
Full solved answer →Method for reduction of NFA to DFA
What is NFA? How is it different from DFA? How is NFA to DFA conversion done? Convert the following NFA into DFA.[10]
The question asks for definitions and a conversion. The specific NFA to be converted was not provided in the question text (the diagram or table is missing), so the worked example below uses this standard NFA: State a b ------------- →q₀ {q₀, q₁} {q₀} q₁ ∅ ...
Full solved answer →Give the formal definition of DFA and NFA. How NFA can be converted into equivalent DFA? Explain with suitable example.[10]
--- A DFA is a 5-tuple: $$M = (Q, \Sigma, \delta, q0, F)$$ Where: Component Description ------------------------ $Q$ Finite, non-empty set of states $\Sigma$ Finite set of input symbols (alphabet) $\delta$ Transition function: $\delta: Q \times \Sigma \righ...
Full solved answer →Construct a NFA accepting language of {0, 1} with each string ending with 01 and convert it into equivalent DFA. [5]
Language: L = { w w ∈ {0,1} and w ends with 01 } Example strings: 01, 001, 101, 0001, 1101, ... We need 3 states: State Role ------------- q0 Start state (reading any symbol, staying in loop) q1 Just read '0' (possible start of ending "01") q2 Just read '01...
Full solved answer →Equivalence of DFA and NFA
Show that, for any NFA $N=(Q,\Sigma,\delta,q_0,F)$ accepting language $L=\Sigma^*$, there is a DFA $D=(Q',\Sigma',q_0',\delta',F')$ accepting the same language $L$.[10]
For any NFA N = (Q, Σ, δ, q₀, F) accepting language L, there exists a DFA D = (Q', Σ, δ', q₀', F') such that L(D) = L(N) = L. --- The core insight is that while an NFA can be in multiple states simultaneously, a DFA must be in exactly one state at any point...
Full solved answer →Extended Transition
Describe the extended transition function of NFA. Construct a NFA, using transition table and transition diagram, over {0, 1} that accept the string having substring 01 and ends with 1. Show the acceptance of 0111.[10]
- Alphabet: $\Sigma = \{0, 1\}$ - Language: strings containing substring 01 AND ending with 1 - Test string: 0111 --- For an NFA $M = (Q, \Sigma, \delta, q0, F)$ where $\delta : Q \times \Sigma \to 2^Q$, the ordinary transition function processes only a sin...
Full solved answer →Finite State Machines with output
Design a Mealy machine over {a, b} that generates output 'A' if the input string ends with aa else output 'B' if the string ends with bb. [5]
A Mealy Machine is a 6-tuple M = (Q, Σ, Δ, δ, λ, q₀) where: - Q = finite set of states - Σ = input alphabet - Δ = output alphabet - δ = transition function (Q × Σ → Q) - λ = output function (Q × Σ → Δ) - q₀ = initial state Note: In a Mealy machine, output d...
Full solved answer →Make Unit 2 stick
Practice CSC262 with flashcards & quizzes