GATE CS 2024 Set 2 — Question 41
Go beyond PYQs with Success TrackerAI-powered personalised practice and doubt support. Unlimited practice on eligible plans; AI usage limits apply.MCQ+2 / -0.67MediumNFAFinite Automata & Regular LanguagesTheory of ComputationRegular Expressions
Theory of Computation → Finite Automata & Regular Languages → NFA
Last updated
Question
Let be the 5-state NFA with -transitions shown in the diagram below.
Which one of the following regular expressions represents the language accepted by ?
Correct answer
(B) 0^ + (1 + 0(00)^)(11)^
Solution
The language accepted by the NFA can be analyzed by decomposing it into paths:
The language is the union of the bottom path alone and the top path (extended by the bottom loop):Analyzing the Options:
1.Top Path (States 1, 2, 3, 5):
- Start at state 1, go to state 2 via .
- Loop between states 2 and 3: . This loop generates .
- To reach the final state 5, we must transition from 2 to 3 (reading '0') and then from 3 to 5 (reading ).
- So, the path purely through the top component generates strings of the form , which represents an odd number of 0s.
- Start at state 1, go to state 4 via .
- Transition (reading '1').
- Loop between states 5 and 4: . This loop generates .
- So, the path purely through the bottom component generates strings of the form , which represents an odd number of 1s.
- The NFA allows transitioning from the top component to the bottom component because state 5 is shared.
- Once the automaton reaches state 5 via the top path (consuming ), it is in an accepting state.
- However, from state 5, it can also traverse the bottom loop () any number of times, generating sequences of .
- Therefore, strings generated by going through the top path and then optionally looping in the bottom component are of the form .
The language is the union of the bottom path alone and the top path (extended by the bottom loop):Analyzing the Options:
- (A) : Represents even 0s or odd 1s. Incorrect.
- (B) : This expands to . The term correctly captures the "Odd 0s followed by Even 1s" pattern derived above. The term captures the "Odd 1s" pattern. Although adds even 0s (which aren't strictly in the derived language), this option is the only one that correctly describes the mixing of 0s and 1s ().
- (C) : The mixing term represents Even 0s followed by Even 1s. Incorrect.
- (D) : The mixing term is a subset of and misses strings like . Incorrect.
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…