Question 14134 – NIC-NIELIT Scientist-B 2020
December 9, 2023Question 5600 – NIELIT Junior Teachnical Assistant_2016_march
December 9, 2023Question 16904 – GATE 2023
Consider the language L over the alphabet {0, 1}, given below:
L = {w ε {0, 1}* | w does not contain three or more consecutive 1’s}.
The minimum number of states in a Deterministic Finite-State Automaton (DFA) for L is _____?
Correct Answer: A
Question 63 Explanation:
L = {ε, 0, 1, 01…….}
L’ = complement of L = {111,0111,1110,110111001,……..}
It’s easy to visualize L’ rather than L thus the given problem is simply a complement of minimal DFA having 3 consecutive 1’s over the input {0,1}.
We can take complement by simply changing the non-final state to the final state and vice-versa.
The Minimal DFA not containing 3 or more consecutive 1’s will require 4 states out of which 3 are final and 1 is dead state.
DFA for L is:
L’ = complement of L = {111,0111,1110,110111001,……..}
It’s easy to visualize L’ rather than L thus the given problem is simply a complement of minimal DFA having 3 consecutive 1’s over the input {0,1}.
We can take complement by simply changing the non-final state to the final state and vice-versa.
The Minimal DFA not containing 3 or more consecutive 1’s will require 4 states out of which 3 are final and 1 is dead state.
DFA for L is:
4
Subscribe
Login
0 Comments