Question:
The minimum number of states in a DFA accepting \( L = \{ w | w \text{ ends with } 01 \} \) over \( \Sigma = \{0, 1\} \) is _______ .
The minimum number of states in a DFA accepting \( L = \{ w | w \text{ ends with } 01 \} \) over \( \Sigma = \{0, 1\} \) is _______ .
Show Hint
For regular languages, the minimum number of states in a DFA depends on the pattern or condition being checked, such as "ends with 01."
Updated On: Jun 16, 2025
- 2
- 3
- 4
- 5
Show Solution
Verified By Collegedunia
The Correct Option is B
Solution and Explanation
A DFA that accepts strings ending with "01" needs at least three states: one to track if the last character was a "0", another to track if the last character was a "1", and a third to indicate the final acceptance state when the string ends with "01".
Therefore, the minimum number of states required is 3.
Was this answer helpful?
0
0
Top AP PGECET Theory of Computation Questions
- The maximum number of transitions which can be performed over a state in a DFA? \( \Sigma = \{a, b, c\} \)
- Which of the following is a regular language?
- The minimum number of nodes in a DFA that recognizes strings over \( \{a, b\} \) with length mod 3 = 0 are _______ .
- If the production rules are given as:
\( S \to XY | W \)
\( X \to aXb | \epsilon \)
\( Y \to cY | \epsilon \)
\( W \to aWc | bZ | \epsilon \)
\( Z \to bZ | \epsilon \)
Then the language generated by these rules is _______ . - Let \( P \) be a regular language and \( Q \) be a context free language such that \( Q \) is a subset of \( P \). Then which of the following is ALWAYS regular?
View More Questions
Top AP PGECET Regular expressions and finite automata Questions
- The maximum number of transitions which can be performed over a state in a DFA? \( \Sigma = \{a, b, c\} \)
- Which of the following is a regular language?
- The minimum number of nodes in a DFA that recognizes strings over \( \{a, b\} \) with length mod 3 = 0 are _______ .
- Let \( P \) be a regular language and \( Q \) be a context free language such that \( Q \) is a subset of \( P \). Then which of the following is ALWAYS regular?
- Which of the following is FALSE?
Top AP PGECET Questions
- If 125V is applied across a 250V, 100W incandescent bulb, the power consumed will be _____ .
- The power consumed by a coil is 300 watts when connected to a 30V DC source and 108 watts when connected to a 30V AC source. The reactance of the coil is ____ .
The supply voltage magnitude \( |V| \) of the circuit shown below is ____ .
A two-port network is defined by the relation
\(\text{I}_1 = 5V_1 + 3V_2 \)
\(\text{I}_2 = 2V_1 - 7V_2 \)
The value of \( Z_{12} \) is:- Which of the following theorems is the dual of Norton’s theorem?
View More Questions