Automata Theory

MCQs - Formal Automata Part 3

Prev
NEXT
Distribute Education
Menu
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

Q41 – The lexical analysis for a modern language such as Java needs the power of which one of the following machine models in a necessary and sufficient sense?
  1. Finite state automata
  2. Deterministic pushdown automata
  3. Non-deterministic pushdown automata
  4. Turing machine

Ans – (1)

Explanation –

Lexical analysis means breaking a program into tokens like keywords, identifiers, numbers, and operators.
In languages like Java, all these tokens can be described using regular expressions.

Regular expressions are implemented using Finite State Automata (FSA).
So, finite state automata are enough and necessary to perform lexical analysis.

More powerful machines like pushdown automata or Turing machines are not required for this task.

Q42 – The total time needed to run any input string in DFA is ……. than time required in NFA.
  1. More
  2. None of these
  3. Equal
  4. Less

Ans – (4)

Explanation –

A DFA has exactly one transition for each input symbol from a state.
So, for every input symbol, the DFA makes only one move. There is no choice, no branching.

An NFA, on the other hand, may have

  • multiple possible transitions for the same input symbol, or

  • ε-transitions.

Because of this, an NFA may need to explore multiple paths (conceptually or during simulation), which can take more time.

Q43 – The sum of minimum and maximum number of final states for a DFA n states is equal to
  1. n+1
  2. n
  3. n-1
  4. n+2

Ans – (1)

Explanation – For a DFA having n states, the minimum number of final states is taken as 1 in exam-oriented questions, because a DFA is generally assumed to recognize a non-empty language. A DFA with zero final states accepts the empty language, which is usually not considered unless clearly stated. The maximum number of final states can be n, when all states are accepting. Therefore, the sum of the minimum and maximum number of final states is 1 + n

Q44 – Dead state is not required in which of the following?
  1. FA
  2. NFA
  3. DFA
  4. All of these

Ans – (2)

Explanation – A dead state (trap state) is not required in an NFA. In an NFA, it is allowed that for a given state and an input symbol, no transition is defined. The automaton can simply stop along that path, so there is no need to explicitly add a dead state.

Q45 – Which of the following statements is correct about a dead (trap) state in a DFA
  1. Every DFA must have a dead state
  2. A DFA never has a dead state
  3. A DFA may or may not have a dead state
  4. A DFA must have more than one dead state

Ans – (3)

Explanation – A dead (trap) state in a DFA is used when, for some state and input symbol, there is no meaningful transition, and we still want the DFA to remain complete. If all transitions for every state and every input symbol already lead to valid states, then a dead state is not required. Therefore, a DFA can have a dead state, but it is not compulsory.

Q46 – What is the complement of the language accepted by the NFA shown below?
TOC FA Part 3 Question
(Assume ∑ = {a} and ε is the empty string)
  1. Φ
  2. ε
  3. a
  4. {a, ε}

Ans – (2)

Explanation –

  • The string a is accepted (direct transition to the final state).

  • The string ε is not accepted, because there is no path that reaches a final state without consuming input.

Hence, the language accepted by the NFA is { a }.

  • Accepted language = { a }

  • Complement language = { ε }

Q47 – The maximum sum of in degree and out degree over a state in a DFA can be determined as:
∑= {a, b, c, d}
  1. 4+4
  2. 4+16
  3. 4+0
  4. depends on the Language

Ans – (4)

Explanation –

In-degree

The in-degree of a state in a finite automaton is the number of transitions that enter that state from other states. In simple words, it counts how many arrows are coming into the state. The in-degree of a state depends on how many transitions from different states point to it, so it is not fixed and can vary from one automaton or language to another.

Out-degree

The out-degree of a state in a finite automaton is the number of transitions that leave that state. In a DFA, the out-degree of every state is fixed and equal to the size of the input alphabet, because for each input symbol there must be exactly one outgoing transition from every state.

In a DFA, the out-degree of every state is fixed and equal to the size of the alphabet.
Here, ∑ = {a, b, c, d}, so the out-degree of any state is 4.

However, the in-degree of a state is not fixed. It depends on

  • how many states are there in the DFA, and

  • how the transitions are designed, which completely depends on the language being recognized.

So, since the maximum in-degree varies with the structure of the DFA, and the structure depends on the language, the maximum sum of in-degree and out-degree cannot be fixed.

Q48 – The maximum number of transition which can be performed over a state in a DFA?
∑= {a, b, c}
  1. 1
  2. 2
  3. 3
  4. 4

Ans – (3)

Explanation – In a DFA, for each state and for each input symbol from the alphabet, there must be exactly one outgoing transition.
Therefore, the maximum (and exact) number of transitions that can be performed from a state in a DFA is equal to the size of the alphabet, which is 3.

Q49 – Which of the following statements is true for a DFA?
  1. It has multiple start states.
  2. It has multiple accept states.
  3. It can have epsilon transitions.
  4. It has a unique next state for each input symbol.

Ans – (4)

Explanation – A Deterministic Finite Automaton (DFA) is defined by the property of determinism. This means that for every state and for each input symbol, there is exactly one defined next state.

Q50 – A DFA is called deterministic because
  1. It has a fixed number of states.
  2. It can deterministically decide whether to accept or reject a string.
  3. It does not accept epsilon transitions.
  4. It has multiple transitions for a single input symbol.

Ans – (2)

Explanation – A DFA is called deterministic because for every state and for every input symbol, the next state is completely fixed. There is no choice or ambiguity while processing the input. Because of this fixed behavior, the DFA can deterministically decide whether a given input string will be accepted or rejected.

Q51 – For a DFA accepting binary numbers whose decimal equivalent is divisible by 5, what are all the possible remainders?
  1. 0
  2. 0, 1, 2
  3. 0, 1, 2, 3
  4. 0, 1, 2, 3, 4

Ans – (4)

Explanation – When checking divisibility by 5, the possible remainders are 0 to 4. Hence, the DFA will have 5 states, each representing one remainder.

Q52 – Which of the following option is correct?
A = {{abc, aaba}. {ε, a, bb}}
  1. abcbb ∈ A
  2. ε ∈ A
  3. ε may not belong to A
  4. abca ∈ A

Ans – (2)

Explanation – A = {{abc, aaba}. {ε, a, bb}}, the dot is used to represent union, so the set A becomes {abc, aaba, ε, a, bb}. This means all these strings are elements of A. Now checking the options, the string abcbb does not belong to A, and abca is also not present in the set. Since ε is explicitly included in the set, it does belong to A. Therefore, the correct option is option 2 – ε ∈ A.

Q53 – Which of the following will the given DFA won’t accept?

  1. ε
  2. 11010
  3. 10001010
  4. String of letter count 11

Ans – (1)

Explanation –

From the given DFA, there are three states arranged in a cycle. From every state, on input 0 or 1, the DFA always moves to the next state in the cycle. The start state is q1, and q3 is the only final state.

Because of this structure, the DFA accepts only those strings whose length is congruent to 2 modulo 3. In simple words, a string is accepted only if the number of symbols read is 2, 5, 8, 11, ….

Now ε has length 0, so the DFA stays in q1, which is not a final state. Hence, ε is not accepted.

Q54 – State true or false:
Statement: Both NFA and e-NFA recognize exactly the same languages.
  1. true
  2. false
  3. may be
  4. can’t say

Ans – (1)

Explanation – Both NFA and ε-NFA recognize exactly the same class of languages, which are the regular languages. Even though an ε-NFA allows transitions without consuming any input symbol, it does not increase the expressive power of the automaton. Every ε-NFA can be converted into an equivalent NFA (and further into a DFA) that accepts the same language.

Q55 – According to the 5-tuple representation i.e. FA= {Q, ∑, δ, q, F}
Statement 1: q ϵ Q’; Statement 2: F ϵ Q
  1. Statement 1 is true, Statement 2 is false
  2. Statement 1 is false, Statement 2 is true
  3. Statement 1 is false, Statement 2 may be true
  4. Statement 1 may be true, Statement 2 is false

Ans – (2)

Q56 – In a DFA, the transition function
  1. Maps a state and an input symbol to multiple states.
  2. Maps a state and an input symbol to a single state.
  3. Maps a state and an input symbol to an output symbol.
  4. Maps a state and an output symbol to an input symbol.

Ans – (2)

Explanation –

In a Deterministic Finite Automaton (DFA), the transition function is defined as
δ : Q × Σ → Q

This means that for every current state and every input symbol, there is exactly one next state. This property is what makes the automaton deterministic.

Q57 – The language accepted by a DFA is
  1. free
  2. Context-sensitive
  3. Regular
  4. Recursively enumerable

Ans – (3)

Explanation – A Deterministic Finite Automaton (DFA) has only finite memory, stored in the form of a finite number of states. Because of this limitation, it can recognize only regular languages. Regular languages are exactly the class of languages that can be described by regular expressions and accepted by finite automata.

Q58 – In a DFA, what happens if there is no valid transition for a given input symbol from a particular state?
  1. The DFA halts and rejects the input.
  2. The DFA moves to a random state.
  3. The DFA accepts the input.
  4. The DFA returns to the start state.

Ans – (1)

Explanation – In a DFA, the transition function must be defined for every state and every input symbol. If, conceptually, there is no valid transition for a given input symbol from a particular state, the DFA cannot proceed further. This situation is equivalent to moving into a dead (trap) state, from which no accepting state can be reached. As a result, the input string is rejected.

Q59 – The set of all strings over the alphabet {0, 1} that contain an even number of 1s can be recognized by
  1. None of the above
  2. A PDA
  3. A Turing machine
  4. A DFA

Ans – (4)

Explanation –

The set of all strings over {0, 1} that contain an even number of 1s is a regular language. We only need to remember whether the number of 1s seen so far is even or odd, which can be done using two states. Since this requires only finite memory, a Deterministic Finite Automaton (DFA) is sufficient to recognize this language.

More powerful machines like PDA or Turing machine are not required for this simple condition.

Q60 – The complement of a language recognized by a DFA can be obtained by
  1. Reversing the transitions.
  2. Swapping the accept and non-accept states.
  3. Making the start state an accept state.
  4. Removing the start state.

Ans – (2)

Explanation –

For a DFA, the complement of the language can be obtained only if the DFA is complete. In that case, we simply swap the accepting (final) states with the non-accepting states, while keeping the transitions and start state the same. This makes every string that was previously accepted get rejected, and vice versa.

The other options do not produce the complement language.

PREV
NEXT

BOOKS

Peter linz Theory of Computation

TOC by KLP Mishra

Automata Theory by John E. Hopcraft

GATE Study Material
Previous Year Paper
Assignements