Font size
WorksheetsFinite Automata
Total questions: 50
Worksheet time: 50mins
There are ________ tuples in finite state machine.
4
5
6
7
Transition function maps.
Σ * Q -> Σ
Q * Q -> Σ
Σ * Σ -> Q
Q * Σ -> Q
Language of finite automata is.
Type 0
Type 1
Type 2
Type 3
Which of the following options is correct?
Statement 1: Initial State of NFA is Initial State of DFA.
Statement 2: The final state of DFA will be every combination of final state of NFA.
Statement 1 is true and Statement 2 is true
Statement 1 is true and Statement 2 is false
Statement 1 can be true and Statement 2 is true
Statement 1 is false and Statement 2 is also false
An automaton that presents output based on previous state or current input:
Acceptor
Classifier
Transducer
None of the mentioned.
NFA, in its name has ’non-deterministic’ because of :
The result is undetermined
The choice of path is non-deterministic
The state to be transited next is non-deterministic
All of the mentioned
The DFA shown below accepts the set of all strings over {0, 1} that
Contain the substring 00
End with 00
End with 0
Begin either with 0 or 1
From current state, on reading input symbol, it moves to more than one state
DFA
DFA with epsilon transitions
NFA
If a language L is accepted by NFA, then there exist a DFA to accept L
Yes
No
Equivalent automata that accepts regular language is
Turing Machine
Linear Bounded Automata
Push Down Automata
Finite Automata
A___________ is a collection of sentences of finite length all constructed from a finite alphabet of symbols.
string
word
language
alphabet
FA can be used for
calculating square root
string recognition
arithmetic operations
comparision
The finite state machine given in figure over alphabet {a,b} recognizes
Any string with odd number of 'a'
Any string with odd number of 'b'
Any string with odd number of 'a' and even number of 'b'
Any string with odd number of 'a' and odd number of 'b'
The automata represent which of the languages given below?
ba*b
bab
b*ab
b*ab*
Is the L(NFA) = L(DFA) ?
Yes
No
The method to convert NFA to DFA
set construction
sub-set construction
alphabet construction
transition construction
The initial state of both NFA and its equivalent DFA is same
True
False
The final state of DFA will be every combination of final state of NFA.
True
False
Every DFA is automatically an NFA
True
False
In this FSM (Finite State Machine) which is the Accept State?
S1
S2
0
1
Which of the following is a not a part of 5-tuple finite automata?
Input alphabet
Transition function
Initial State
Output Alphabet
{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}
In a DFA, initial state can be more than one?
Yes
No
A string is a finite sequence of symbols taken from
input alphabet
output alphabet
transition function
none of these
Input={ A-Z , a-z , 0-9 } belongs to:
English Alphabets
Binary number
Decimal number
Alphanumeric
A initial state is represented by:
simply by a circle
circle with an arrow
simply by an arrow
no representation at all
What is the study of Automata?
The study of automatic programming.
the study of automatic procedure.
The study of abstract computing devices or machines
None of these
The given automaton accepts strings starting with a or b.
True
False
Choose the best option
Deterministic Finite Automaton
Non-Deterministic Finite Automaton
q3 state is dead state in the given automaton.
True
False
Number of states require to accept string ends with 10.
3
2
1
can't be represented
Moore Machine is an application of:
Finite automata without input
Finite automata with output
Non- Finite automata with output
None of the mentioned
In Moore machine, output is produced over the change of:
transitions
states
Both
None of the mentioned
The output alphabet can be represented as:
δ
∆
∑
None of the mentioned
Concatenation Operation refers to which of the following set operations:
Union
Dot
Kleen
None
A DFA can be represented in the following format
Tree
Transition table
C Code
None of the mentioned
∑ is _________?
set of input symbols
set of output symbols
set of states
transitions
Non-empty finite set of states is represented by _______
∑
Q
F
q0
δ represents_______?
transition diagram
transition function
transition table
empty string
F represents________?
set of final states
final state
states
transitions
NFA and DFA are equivalent.
YES
NO
MAY BE
CAN'T Say
For a give Moore Machine, Given Input=’101’, thus the output would be of length
4
3
2
none
8. ε-closure of state is combination of self state and
ε-reachable state
initial state
final state
all the above
18. e-closure of (q0) is
{q0,q1,q2,q3,q4}
{q0,q1,q3,q4}
{q0,q1,q2,q3}
{q1,q2,q3}
aba
abaabb
aaba
babab
Which of the following is not an example of finite state machine system?
Control Mechanism of an elevator
Combinational Locks
Traffic Lights
Digital Watches
Given: ∑= {a, b}
L= {xϵ∑*|x is a string combination}
∑4 represents which among the following?
{aa, ab, ba, bb}
{aaaa, abab, ε, abaa, aabb}
{aaa, aab, aba, bbb}
All of the mentioned
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
Check the string aabbb is accepted or not
Accepted
Not accepted
Is the automata shown DFA or NFA?
DFA
NFA
