- 2073 Magh · 2+6 marks
Design NFA for strings ending with aba
Short answer
An NFA uses states q0 (start), q1, q2, q3 (final). From q0, reading a guesses either stay or move to q1 to start final suffix; then b to q2, a to q3. Accepts strings ending with aba.
Define Non-Deterministic Finite State Automata. Design a finite-state automaton that accepts only those set of strings over {a,b} which ends with aba. Precisely, only those strings which end with aba should accepted and other strings over {a, b} should be rejected. Your design should include the proper definition of the finite-state automaton, the transition table and the transition diagram.
Definition
A non-deterministic finite automaton (NFA) is a 5-tuple M = (Q, Σ, δ, q₀, F), where Q is a finite set of states, Σ a finite input alphabet, q₀ ∈ Q the start state, F ⊆ Q the set of accepting (final) states, and δ : Q × Σ → P(Q) the transition function. For a state and input symbol, δ gives a set of possible next states (possibly empty or more than one). A string is accepted if at least one sequence of choices ends in a final state.
Design of the NFA for strings ending with aba
Idea: q₀ keeps reading anything. On an a, the machine guesses "this a may start the final aba" and also stays in q₀. It then checks b, then a. If the input ends exactly there, it is accepted.
Formal definition: M = ({q₀, q₁, q₂, q₃}, {a, b}, δ, q₀, {q₃})
Transition table
| State | a | b |
|---|---|---|
| → q₀ | {q₀, q₁} | {q₀} |
| q₁ | ∅ | {q₂} |
| q₂ | {q₃} | ∅ |
| *q₃ (final) | ∅ | ∅ |
Transition diagram
a,b (loop on q0)
+---+
v |
->(q0)-+--a-->(q1)--b-->(q2)--a-->((q3))
(q₀ has two moves on a: it stays in q₀ or goes to q₁. q₃ is final.)
Check
- Input baba: q₀ -b→ q₀ -a→ q₁ (guess) -b→ q₂ -a→ q₃ and the string ends, so it is accepted.
- Input abab: the run that reaches q₃ after "aba" dies on the last b, because q₃ has no moves. The run that guesses at the second a ends in q₂, and the run that stays in q₀ ends in q₀. No run ends in q₃, so the string is rejected.
- Input aba, bbaba are accepted; ab, abaa, bb are rejected.
I also tested this table by brute force on all strings up to length 10: it accepts exactly the strings ending in aba.
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- Design FSA for strings beginning with baa · Discrete Structure, chapter 2
- Design FSA accepting odd number of b's · Discrete Structure, chapter 2 · asked 4×
- Define FSM; design FSA with two consecutive a's · Discrete Structure, chapter 2 · asked 4×
- Design FSA accepting even number of a's · Discrete Structure, chapter 2 · asked 4×
- Differentiate Finite State Machine and Automata · Discrete Structure, chapter 2 · asked 2×
- Language of grammar; grammar for strings not ending in ab · Discrete Structure, chapter 2
- Functional vs non-functional; include and extend · Object Oriented Analysis and Design, chapter 2
- DFA starts or ends with 01 · Theory of Computation, chapter 2
- TM for aⁿcbⁿ (single tape, deterministic) · Theory of Computation, chapter 4