NEW
Font size
WorksheetsNFA, DFA Definition
Total questions: 15
Worksheet time: 13mins
There are ________ tuples in finite state machine.
4
5
6
Unlimited
Transition function of DFA maps.
Σ * 1 -> Σ
Q * Q -> Σ
Σ * Σ -> Q
Q * Σ -> Q
An NFA’s transition function returns
A Boolean value
A state
An edge
A set of states
Which is true for Dead State?
It cannot be reached anytime
There is no necessity of the state
If control enters no way to come out from the state
If control enters FA deads
The Tuples for NDFA
∑,Q,q0,F,δ
Q,q0,F,δ
Θ,Q,q0,F,δ
F,Q,Δ,q0, δ
Which of the following is a not a part of
5-tuple finite automata?
Input alphabet
Transition function
Initial State
output Alphabet
The DFA shown accepts the set of all strings over {0, 1} that
End with 00
End with 0
Begin either with 0 or 1
Contain the substring 00
{w | w ends with 010}
{w | w starts with 010}
{w | w contains 010 as a substring}
{w | w does not contain 010 as a substring}
Number of states require to accept string ends with 10.
3
2
1
5
When in State S2 if the input is 1
The machine will remain in state S2
The machine will change state to S1
The Machine will return to the Start State
The machine will return the value of 0
In this DFA the accepted Input is
01
10
00
11
Starting at state S1 what state would input 'acd' change to
S1
S3
S4
S2
An input of 'ab' would result in state
S1
S2
S3
S4
From the starting state is input 'abc' valid (accepted)?
YES
NO
What state will the machine rest in with an input of 'aabacda'?
S4
S3
S2
S1
