--- title: "Design NFA for strings ending with aba" subject: "Discrete Structure" chapter: 2 key: "semester_4/discrete_structure:nfa-strings-ending-aba" source: https://www.bctengineer.com/q/semester_4/discrete_structure/nfa-strings-ending-aba site: BCT Engineering --- # Design NFA for strings ending with aba Discrete Structure · Chapter 2: Finite State Automata - Asked in: 2073 Magh, 2+6 marks - Video: [Theory of Computation: Example for NFA and DFA (Substring problem)](https://www.youtube.com/watch?v=hQ39Yb9lu20) — Anita R - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_4/discrete_structure/nfa-strings-ending-aba - Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-2 ## Question 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. ## 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. ## Answer #### 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** ```text 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*. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. What is the transition function of an NFA? A. δ : Q × Σ → Q, giving exactly one next state B. δ : Q → Σ C. δ : Q × Σ → F D. δ : Q × Σ → P(Q), giving a set of possible next states Answer: D. An NFA may have zero, one or several next states for a state and symbol. (Key point: NFA definition) 2. When does an NFA accept a string? A. If at least one sequence of choices ends in a final state B. If every sequence of choices ends in a final state C. If the first choice ends in a final state D. If it never reaches a state with no move Answer: A. One successful path is enough. (Key point: Acceptance in NFA) 3. What does q0 do on reading a? A. Goes to q1 only B. Goes to q3 C. Goes to {q0, q1}: it stays, or guesses this a starts the final aba D. Goes to q0 only Answer: C. The non-determinism lets it guess where the last aba begins. (Key point: Guessing the final aba) 4. Why is abab rejected? A. q3 is reached but is not final B. The string does not contain aba C. q0 has no move on b D. The branch reaching q2 has no move on the last b, and the q0 branch is not final Answer: D. The only way to q3 needs the string to end right after aba. (Key point: Rejecting abab) ## Related in Discrete Structure - [Design FSA for strings beginning with baa](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-strings-beginning-baa) — Discrete Structure, chapter 2 - [Design FSA accepting odd number of b's](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-odd-number-of-b) — Discrete Structure, chapter 2, asked 4× - [Define FSM; design FSA with two consecutive a's](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-two-consecutive-a) — Discrete Structure, chapter 2, asked 4× - [Design FSA accepting even number of a's](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-even-number-of-a) — Discrete Structure, chapter 2, asked 4× - [Differentiate Finite State Machine and Automata](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsm-vs-fsa-difference) — Discrete Structure, chapter 2, asked 2× - [Language of grammar; grammar for strings not ending in ab](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Alanguage-of-grammar-and-grammar-not-ending-ab) — Discrete Structure, chapter 2 ## Related in other subjects - [Functional vs non-functional; include and extend](https://www.bctengineer.com/question.md?key=semester_6%2Fobject_oriented_analysis_and_design%3Afunctional-nonfunctional-include-extend) — Object Oriented Analysis and Design, chapter 2 - [DFA starts or ends with 01](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Adfa-starts-or-ends-01) — Theory of Computation, chapter 2 - [TM for aⁿcbⁿ (single tape, deterministic)](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-an-c-bn) — Theory of Computation, chapter 4