Theory-of-Computation
December 6, 2023Question 9882 – Theory-of-Computation
December 6, 2023GATE 1999
|
Question 4
|
Consider the regular expression (0 + 1) (0 + 1)…. N times. The minimum state finite automation that recognizes the language represented by this regular expression contains
|
n states
|
|
|
n + 1 states
|
|
|
n + 2 states
|
|
|
None of the above
|
Question 4 Explanation:
Let’s draw both NFA and DFA and see which one requires less no. of state.
DFA:
So, DFA requires (n+2) state.
NFA:
So, NFA requires (n+1) state.
So, final answer will be,
min(n+1, n+2)
= n+1
DFA:
So, DFA requires (n+2) state.
NFA:
So, NFA requires (n+1) state.
So, final answer will be,
min(n+1, n+2)
= n+1
Correct Answer: B
Question 4 Explanation:
Let’s draw both NFA and DFA and see which one requires less no. of state.
DFA:
So, DFA requires (n+2) state.
NFA:
So, NFA requires (n+1) state.
So, final answer will be,
min(n+1, n+2)
= n+1
DFA:
So, DFA requires (n+2) state.
NFA:
So, NFA requires (n+1) state.
So, final answer will be,
min(n+1, n+2)
= n+1