Unit 1
Deterministic Finite Automaton (DFA)- Definition, Representation, Acceptability of a String and Language, Non Deterministic Finite Automaton (NFA), Equivalence of DFA and NFA, NFA with ε-Transition, Equivalence of NFA’s with and without ε-Transition
Q1 – The behaviour of a NFA can be simulated by a DFA
Always
Sometime
Never
Depend on NFA
Ans – (1)
Explanation – A Non-deterministic Finite Automaton (NFA) can always be simulated by a Deterministic Finite Automaton (DFA). For every NFA, we can construct an equivalent DFA that accepts exactly the same language as the NFA.
Q2 – Statement 1- A finite automaton can be represented using a directed graph.
Statement 2- Each vertex of the graph represents a state of the finite automaton.
Statement 3- Each labeled directed edge of the graph represents a transition function of the finite automaton.
Statement 4- Every graph with labeled edges and vertices necessarily represents a finite automaton.
.
Which of the following options is correct?
Statements 1, 2, and 3 are correct but Statement 4 is false
Statements 1 and 4 are correct while Statements 2 and 3 are false
Only Statement 4 is correct
All of the statements are correct
Ans – (4)
Explanation –
Statement 4 is false because
Not every labeled graph is a finite automaton
A finite automaton must satisfy specific rules like a defined start state, accepting states, and valid transition function
Q3 – The minimum number of states required to recognize an octal number divisible by 3 are/is
1
3
5
7
Ans – (2)
Explanation –
To check divisibility by 3, the automaton only needs to remember the remainder when the number is divided by 3.
Possible remainders when dividing by 3 are 0, 1 and 2
So, we need one state for each remainder. Since there are 3 possible remainders, the minimum number of states required is 3.
Q4 – A NFA can be enhanced to move to a next state without reading the input tape.
True
False
Can’t say
Depends upon NFA
Ans – (1)
Explanation – In a Non-deterministic Finite Automaton (NFA), it is possible to move from one state to another without reading any input symbol.
This type of transition is called an ε (epsilon) transition.
Q5 – Which of the following is not a part of 5-tuple finite automata?
Input alphabet
Transition function
Initial State
Output Alphabet
Ans – (4)
Explanation –
A finite automaton is formally defined by a 5-tuple, written as
M = (Q, Σ, δ, q₀, F)
Where
Q – set of states
Σ – input alphabet
δ – transition function
q₀ – initial (start) state
F – set of final (accepting) states
Now check the options one by one –
Input alphabet – part of the 5-tuple
Transition function – part of the 5-tuple
Initial state – part of the 5-tuple
Output alphabet – not included
Q6 – A FA having more than one reading head has
More power than one reading head FA
Equal power as one reading head FA
More storage than one reading head FA
Both 2 and 3
Ans – (2)
Explanation – A finite automaton (FA) has only finite control and no extra memory.
Even if we give an FA more than one reading head, it still cannot store extra information beyond its finite states. So, option is 2.
Q7 – If an Infinite language is passed to Machine M, the subsidiary which gives a finite solution to the infinite input tape is ______________
Compiler
Interpreter
Loader and Linkers
None of the mentioned
Ans – (1)
Explanation – The compiler turns that finite specification into a finite machine-level program that runs on Machine M to handle inputs (which could be infinite in variety).
Q8 – The number of elements in the set for the Language
L = {x ϵ (∑r)*|length if x is at most 2} and ∑ = {0,1} is _________
7
6
8
5
Ans – (1)
Explanation –
“At most 2” means length 0, length 1 & length 2
Now count strings of each length.
Length 0
Only the empty string ε
Number of strings = 1
Length 1
0, 1
Number of strings = 2
Length 2
00, 01, 10, 11
Number of strings = 4
Now add all of them
1 + 2 + 4 = 7
Q9 – The palindrome unit can not be recognized by a FA because
A FA can’t determine the midpoint of a palindrome
A FA can’t remember its previous input
A FA head has read – only capability and can’t move in both directions
Both 1 and 2
Ans – (4)
Explanation – An FA reads the input only once from left to right and has no way to know where the middle of the string is, especially when the length is not fixed.
An FA has finite memory (only states), so it cannot store an unbounded number of symbols to compare later.
Q10 – The transitional function of a DFA is
Q X Σ→Q
Q X Σ→2^Q
Q X Σ→2n
Q X Σ→Qn
Ans – (1)
Explanation –
In a Deterministic Finite Automaton (DFA), for every state and every input symbol, there is exactly one next state.
So, the transition function of a DFA is defined as
δ – Q × Σ → Q
Q11 – The transitional function of a NFA is
Q X Σ→Q
Q X Σ→2^Q
Q X Σ→2n
Q X Σ→Qn
Ans – (2)
Explanation – In an NFA, for one state and one input symbol, the automaton can move to more than one next state.
So, the transition function must return a set of states, not a single state.
That is why the transition function of an NFA is defined as Q × Σ → 2^Q.
Q12 – Maximum number of states of a DFA converted from a NFA with n states is
n
n^2
2^n
None of these
Ans – (3)
Explanation –
When an NFA with n states is converted into an equivalent DFA, we use the subset construction method.
In this method,
each state of the DFA represents a subset of NFA states.
An NFA with n states has 2ⁿ possible subsets.
In the worst case, all subsets can become reachable DFA states.
Q13 – For the following change of state representation in a Finite Automaton (FA), which of the following transition notations is incorrect?
δ(m, 1) = n
δ(n, 0) = m
δ(m, 0) = ε
δ(n, 1) = n
Ans – (3)
Explanation –
ε is NOT a state
ε means “empty string”, not a state name
A finite automaton cannot move to ε as a state
Q14 – 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}
None of the above
Ans – (4)
Explanation – Σ = {a, b} and Σ⁴ represents the set of all strings of exactly length 4 formed using symbols a and b. This means every string must contain four symbols only, and each symbol must be either a or b. Strings of length 2 or 3 are not allowed, and the empty string ε is also not allowed because its length is 0.
Q15 – Which of the following not an example Bounded Information?
fan switch outputs {on, off}
electricity meter reading
colour of the traffic light at the moment
none of the mentioned
Ans – (2)
Explanation – Bounded information means the information can take values from a fixed and limited set. The reading keeps increasing and has no fixed upper limit, so it is unbounded.
Q16 – Basic limitations of finite state machine is
It cannot remember arbitrarily large amount of information
It cannot remember state transitions
It cannot remember grammar for a language
It cannot remember language generated from a grammar
Ans – (1)
Explanation – A Finite State Machine (FSM) has only finite memory, which is stored in the form of a finite number of states. Because of this limitation, it cannot store or remember an arbitrarily large amount of information.
Q17 – A finite automata recognizes
Any Language
Context Sensitive Language
Context Free Language
Regular Language
Ans – (4)
Explanation –
A finite automaton has finite memory and no extra storage like a stack or tape. Because of this limitation, it can recognize only the simplest class of languages.
Q18 – A Language for which no DFA exist is a________
Regular Language
Non-Regular Language
May be Regular
Cannot be said
Ans – (2)
Explanation – A Deterministic Finite Automaton (DFA) exists if and only if the language is regular.
So, every regular language can be accepted by some DFA.
If no DFA exists for a language, it means the language is not regular.
Q19 – A DFA cannot be represented in the following format
Transition graph
Transition Table
C code
None of the mentioned
Ans – (4)
Explanation – A Deterministic Finite Automaton (DFA) can be represented in many equivalent ways. Since all the given formats are valid representations of a DFA, there is no incorrect option.
Q20 – What the following DFA accepts?
Strings such that it ends with ‘101’ accepted by DFA
x is a string such that it ends with ‘101’
x is a string such that it ends with ‘01’
x is a string such that it has odd 1’s and even 0’s
x is a strings such that it has starting and ending character as 1
Ans – (1)
Explanation – The given DFA accepts all strings that end with 101. From the transition diagram, we can see that the automaton keeps tracking the last three input symbols. It reaches the accepting state only when the final sequence read is 101, and any extra symbol after that moves the DFA away from the accepting state. This means the condition for acceptance depends only on the ending pattern 101, not on the entire string. Therefore, the correct description of the language accepted by the DFA is that x is a string such that it ends with 101.
