GATE CS 2017 Set 1 — Question 22
Go beyond PYQs with Success TrackerAI-powered personalised practice and doubt support. Unlimited practice on eligible plans; AI usage limits apply.NAT+1 / -0EasyDFA MinimizationFinite Automata & Regular LanguagesTheory of ComputationRegular Expressions
Theory of Computation → Finite Automata & Regular Languages → DFA Minimization
Last updated
Question
Consider the language given by the regular expression over the alphabet . The smallest number of states needed in a deterministic finite-state automaton (DFA) accepting is __________.
Correct answer
4 to 4
Solution
The regular expression represents the set of all strings over where the second symbol from the right is 'b'.To construct the minimal DFA, we need to keep track of the recent history of inputs to determine if the condition is met. Specifically, we need to know if the last symbol read was 'b' (which would make the current symbol valid as the last symbol of an accepted string) or not.The states can be defined based on the relevant suffixes read so far:
1.: Start state, or the last symbol was 'a' and the one before it was not 'b' (e.g., suffix or ).
2.: The last symbol read was 'b' (e.g., suffix or ). This is a potential start of the pattern .
3.: The last two symbols were . Since the second-to-last was 'b', this is an accepting state.
4.: The last two symbols were . Since the second-to-last was 'b', this is an accepting state. Also, the last symbol is 'b', so we stay in a state indicating the last symbol is 'b'.
Transitions:- From (suffix or ):
- Input (suffix , condition not met)
- Input (suffix , last is )
- From (suffix ):
- Input (suffix , accepted)
- Input (suffix , accepted)
- From (suffix , accepted):
- Input (suffix , 2nd last is , reject)
- Input (suffix , 2nd last is , reject; last is )
- From (suffix , accepted):
- Input (suffix , 2nd last is , accept)
- Input (suffix , 2nd last is , accept)
Continue learning with Success Tracker
A step still unclear? Work through it with support
Use Success Tracker to ask about the reasoning, then try another GATE CS question to check your understanding.
AI-powered practice· Unlimited practice on eligible plans
- PYQs with solutions
- Attempt available previous-year questions, then compare your reasoning with the worked solution. Coverage varies by stream.
- Practice that adapts
- Choose a topic, work on weaker areas and bookmark questions to revisit. Your attempts feed your progress tracking.
- AI doubt support
- Ask follow-up questions about a step or concept while practising, instead of stopping at the final answer.
Unlimited practice is available on eligible plans. Free practice and AI usage have limits; check the current plan allowances before choosing.
This page stays readable without an account. AI responses can be wrong; check them against the solution and source material.
More questions on Finite Automata & Regular Languages
2026 Set 2 Q13Which one of the following statements is equivalent to the following assertion? Turing machine …2026 Set 1 Q25Consider the following grammar where is the start symbol, and and are terminal symbols.…2026 Set 1 Q26Let be a nondeterministic finite automaton (NFA) with 6 states over a finite alphabet. Which of…2026 Set 2 Q29Which of the following grammars is/are ambiguous?2026 Set 2 Q47Consider the following two finite automata and . [figure] Which of the following…