1What is an alphabet in the context of Automata Theory?
A.A finite set of states
B.A set of all possible words over a language
C.A finite, non-empty set of symbols
D.An infinite set of characters
Correct Answer: A finite, non-empty set of symbols
Explanation:
In automata theory, an alphabet is formally defined as a finite, non-empty set of symbols, typically denoted by .
Incorrect! Try again.
2Which of the following represents the set of all possible strings over an alphabet , including the empty string?
A.
B.
C.
D.
Correct Answer:
Explanation:
The Kleene star operation, denoted as , represents the set of all possible strings (of any length ) that can be generated from the alphabet , which inherently includes the empty string .
Incorrect! Try again.
3What is the length of the empty string, denoted by ?
A.0
B.Undefined
C.1
D.
Correct Answer: 0
Explanation:
The empty string is a string containing no symbols, so its length is exactly 0. That is, .
Incorrect! Try again.
4If an alphabet , which of the following correctly represents ?
A.
B.
C.
D.
Correct Answer:
Explanation:
represents the set of all strings of length exactly 2 over the alphabet . For , these are .
Incorrect! Try again.
5The operation of appending one string to the end of another string is known as?
A.Union
B.Kleene Star
C.Concatenation
D.Intersection
Correct Answer: Concatenation
Explanation:
Concatenation is the operation of joining two strings end-to-end. If and , their concatenation is .
Incorrect! Try again.
6A Deterministic Finite Automaton (DFA) is mathematically defined as a?
A.4-tuple
B.5-tuple
C.6-tuple
D.7-tuple
Correct Answer: 5-tuple
Explanation:
A DFA is formally defined as a 5-tuple: .
Incorrect! Try again.
7In the formal definition of a DFA, , what does represent?
A.The set of final states
B.The transition function
C.A finite set of states
D.A finite set of input symbols
Correct Answer: A finite set of states
Explanation:
In the 5-tuple definition of a DFA, denotes a finite, non-empty set of states.
Incorrect! Try again.
8In a DFA, what is the mathematical mapping of the transition function ?
A.
B.
C.
D.
Correct Answer:
Explanation:
For a DFA, the transition function takes a current state (from ) and an input symbol (from ) and maps it to exactly one next state (in ).
Incorrect! Try again.
9Which of the following computational models requires no auxiliary memory (like a stack or tape)?
A.Pushdown Automaton
B.Finite Automaton
C.Turing Machine
D.Linear Bounded Automaton
Correct Answer: Finite Automaton
Explanation:
A Finite Automaton acts as a recognizer with only a finite amount of internal state memory and does not possess an unbounded auxiliary memory structure like a stack or tape.
Incorrect! Try again.
10In a DFA, for a given state and a specific input symbol, how many transitions are possible?
A.More than one
B.Exactly zero
C.Exactly one
D.Zero or one
Correct Answer: Exactly one
Explanation:
The 'Deterministic' nature of a DFA guarantees that from any state, for every input symbol in , there is exactly one transition to a next state.
Incorrect! Try again.
11In a Non-deterministic Finite Automaton (NDFA), the transition function maps to?
A.
B.
C.
D.
Correct Answer:
Explanation:
In an NDFA, a state can transition to multiple states on a single input. Thus, , where is the power set of .
Incorrect! Try again.
12Which of the following features is permitted in an NDFA but NOT in a standard DFA?
A.Multiple transitions from a single state on the same input symbol
B.It has a finite set of states
C.It has a designated start state
D.It accepts formal languages
Correct Answer: Multiple transitions from a single state on the same input symbol
Explanation:
Non-determinism allows an NDFA to branch into multiple execution paths simultaneously by having multiple valid transitions for a single (state, input) combination. A DFA allows only one.
Incorrect! Try again.
13An -NFA allows transitions without reading any input symbol. What does represent in this context?
A.An error state
B.End of file
C.The empty string
D.A wild-card character
Correct Answer: The empty string
Explanation:
represents the empty string, meaning the automaton can change its state spontaneously without consuming any symbols from the input string.
Incorrect! Try again.
14Is every DFA also an NDFA?
A.Yes, a DFA is a special case of an NDFA where each state has exactly one transition per input symbol.
B.No, because a DFA does not allow multiple transitions.
C.No, because they accept different classes of languages.
D.Yes, but only if the language is finite.
Correct Answer: Yes, a DFA is a special case of an NDFA where each state has exactly one transition per input symbol.
Explanation:
Every DFA acts as an NDFA that happens to have exactly one transition for each input from every state. Hence, a DFA is strictly a subset of an NDFA.
Incorrect! Try again.
15Regarding their computational power (the ability to recognize languages), how do DFA and NDFA compare?
A.DFA is more powerful than NDFA
B.They have equal computational power
C.NDFA is more powerful than DFA
D.It depends on the size of the alphabet
Correct Answer: They have equal computational power
Explanation:
Every NDFA can be converted into an equivalent DFA that accepts the exact same language (using Subset Construction). Thus, they both recognize the class of Regular Languages.
Incorrect! Try again.
16In a transition diagram (graph) of a Finite Automaton, what do the vertices (nodes) represent?
A.Input symbols
B.Transitions
C.Final languages
D.States
Correct Answer: States
Explanation:
In the graphical representation of finite automata, states are represented by vertices (circles), and transitions are represented by directed edges.
Incorrect! Try again.
17How is the start state typically denoted in a transition diagram?
A.By a dotted circle
B.By a double circle
C.By an incoming arrow not originating from any other state
D.By a shaded node
Correct Answer: By an incoming arrow not originating from any other state
Explanation:
The initial (start) state is conventionally indicated by a straight arrow pointing to it from 'nowhere' (no originating state).
Incorrect! Try again.
18What does the extended transition function compute in a DFA?
A.The length of the string
B.The final state reached from state after reading the entire string
C.The set of all possible initial states
D.The next state after reading a single symbol
Correct Answer: The final state reached from state after reading the entire string
Explanation:
The extended transition function generalizes to apply to strings rather than single characters, returning the state reached after processing the whole string starting from .
Incorrect! Try again.
19For a DFA, what is the value of ?
A.An empty set
B.
C.
D.The final state
Correct Answer:
Explanation:
Processing an empty string means making no transitions, so the automaton simply remains in the state it started in. Thus, .
Incorrect! Try again.
20For a DFA, which equation correctly represents the recursive definition of the extended transition function for a string (where and )?
A.
B.
C.
D.
Correct Answer:
Explanation:
To process string , the DFA first processes string from state reaching , and then applies the single-character transition for symbol .
Incorrect! Try again.
21A string is strictly accepted by a DFA if and only if?
A.
B.
C.
D.
Correct Answer:
Explanation:
By definition, a string is accepted by a DFA if processing the entire string starting from the initial state leads to a state that belongs to the set of final states .
Incorrect! Try again.
22The language accepted by a DFA , denoted as , is formally defined as?
A.
B.
C.
D.
Correct Answer:
Explanation:
The language of a DFA consists of all strings in such that the extended transition function maps the start state and the string to a final state in .
Incorrect! Try again.
23In an NDFA, a string is considered accepted if the set of states reached after reading from the start state?
A.Is exactly equal to
B.Contains no states in
C.Contains all states of
D.Contains at least one state in
Correct Answer: Contains at least one state in
Explanation:
An NDFA accepts a string if there exists at least one valid computational path that consumes the entire string and ends in a final/accepting state.
Incorrect! Try again.
24A state from which the machine cannot reach any final state for any sequence of input symbols is known as a?
A.Accepting state
B.Final state
C.Start state
D.Dead state (or Trap state)
Correct Answer: Dead state (or Trap state)
Explanation:
A dead state (or trap state) is a non-final state that transitions to itself for every input symbol, meaning acceptance is impossible once it is entered.
Incorrect! Try again.
25If a DFA processes an input string completely and halts in a state that does not belong to , the string is?
A.Accepted
B.Looped infinitely
C.Passed to an NDFA
D.Rejected
Correct Answer: Rejected
Explanation:
If the extended transition function results in a non-final state, the string is rejected by the automaton.
Incorrect! Try again.
26The standard algorithm used to convert an NDFA to an equivalent DFA is known as?
A.Subset Construction Algorithm
B.Myhill-Nerode Construction
C.Hopcroft's Algorithm
D.State Elimination Method
Correct Answer: Subset Construction Algorithm
Explanation:
The Subset Construction Algorithm (or powerset construction) is the standard method used to systematically build a DFA that accepts the same language as a given NDFA.
Incorrect! Try again.
27If an NDFA has exactly states, what is the theoretical maximum number of states in its equivalent constructed DFA?
A.
B.
C.
D.
Correct Answer:
Explanation:
Because the subset construction maps sets of NDFA states to single DFA states, the maximum number of DFA states is the size of the power set of the NDFA's states, which is .
Incorrect! Try again.
28Two finite automata and are strictly said to be equivalent if?
A.Both are deterministic
B.They have the same number of states
C.They have identical transition diagrams
D.
Correct Answer:
Explanation:
Two automata are defined to be equivalent if and only if they recognize (accept) exactly the same language.
Incorrect! Try again.
29During the conversion from NDFA to DFA using the Subset Construction algorithm, a state in the resulting DFA is marked as a final state if?
A.It contains only final states of the NDFA
B.It contains all the states of the NDFA
C.It is the start state of the NDFA
D.It contains at least one final state of the NDFA
Correct Answer: It contains at least one final state of the NDFA
Explanation:
A subset of NDFA states becomes a final state in the new DFA if that subset contains one or more states that were final states in the original NDFA.
Incorrect! Try again.
30To process strings in an -NFA, one uses the -closure. What is the -closure of a state ?
A.The set of all states reachable from on a specific input symbol
B.The set of final states reachable from
C.The set of all states reachable from without consuming any input symbol (including itself)
D.The state only
Correct Answer: The set of all states reachable from without consuming any input symbol (including itself)
Explanation:
The -closure of a state includes itself and all states that can be reached from by following only -transitions.
Incorrect! Try again.
31A Moore machine is a finite state machine with output. In a Moore machine, the output depends on?
A.The initial state
B.Both the current state and the current input
C.Only the current state
D.Only the current input
Correct Answer: Only the current state
Explanation:
By definition, the output function in a Moore machine associates an output solely with the state the machine is currently in, independent of the input transition.
Incorrect! Try again.
32A Mealy machine is a finite state machine with output. In a Mealy machine, the output depends on?
A.Only the current state
B.Only the current input
C.The final state
D.Both the current state and the current input
Correct Answer: Both the current state and the current input
Explanation:
In a Mealy machine, the output is produced during the transition between states. Thus, the output depends on both the current state and the specific input symbol being read.
Incorrect! Try again.
33In a Moore machine, if an input string of length is processed, what is the length of the generated output string?
A.
B.
C.
D.
Correct Answer:
Explanation:
A Moore machine outputs a symbol for the initial state before any input is read. Therefore, it produces an output sequence of length for an input sequence of length .
Incorrect! Try again.
34In a Mealy machine, if an input string of length is processed, what is the length of the generated output string?
A.
B.
C.
D.
Correct Answer:
Explanation:
Since a Mealy machine generates output only on transitions, it produces exactly one output symbol per input symbol. An input of length yields an output of length .
Incorrect! Try again.
35Let be the output alphabet. In the 6-tuple formal definition of a Moore machine, the output function maps from?
A.
B.
C.
D.
Correct Answer:
Explanation:
Because Moore machine outputs depend only on the current state, its output function maps the state space to the output alphabet .
Incorrect! Try again.
36Let be the output alphabet. In the 6-tuple formal definition of a Mealy machine, the output function maps from?
A.
B.
C.
D.
Correct Answer:
Explanation:
Since Mealy machine outputs depend on both the current state and the input symbol, its output function maps to the output alphabet .
Incorrect! Try again.
37Which of the following statements about Mealy and Moore machines is TRUE?
A.Neither machine can be converted into the other
B.Moore machines have more computational power than Mealy machines
C.Mealy machines have more computational power than Moore machines
D.For every Moore machine, there is an equivalent Mealy machine and vice versa
Correct Answer: For every Moore machine, there is an equivalent Mealy machine and vice versa
Explanation:
Mealy and Moore machines have the exact same computational power. Algorithms exist to transform any Moore machine into a Mealy machine and vice versa.
Incorrect! Try again.
38The process of reducing the number of states of a DFA to construct an equivalent DFA with the fewest possible states is called?
A.Thompson's Construction
B.Subset Construction
C.DFA Minimization
D.DFA Maximization
Correct Answer: DFA Minimization
Explanation:
DFA Minimization is the algorithmic process of merging equivalent states in a DFA to produce an equivalent DFA with the absolute minimum number of states.
Incorrect! Try again.
39In the table-filling algorithm for DFA minimization, two states and are initially marked as distinguishable (0-distinguishable) if?
A.Both have self-loops
B.Both are final states
C.Both are non-final states
D.One is a final state and the other is a non-final state
Correct Answer: One is a final state and the other is a non-final state
Explanation:
The base step of the table-filling algorithm is to mark pairs of states where one is an accepting state and the other is a non-accepting state, because the empty string distinguishes them.
Incorrect! Try again.
40Two states and in a DFA are said to be equivalent if, for every string , transitions from and on lead to?
A.States that are either both final or both non-final
B.The start state
C.Dead states
D.The exact same state
Correct Answer: States that are either both final or both non-final
Explanation:
States and are equivalent if there is no string that distinguishes them; meaning processing from both states will either both lead to final states or both lead to non-final states.
Incorrect! Try again.
41What is the first necessary step before applying a DFA minimization algorithm?
A.Converting the DFA to an NDFA
B.Removing all final states
C.Removing all unreachable states from the start state
D.Making all states accepting
Correct Answer: Removing all unreachable states from the start state
Explanation:
Before minimizing, any state that cannot be reached from the initial state must be eliminated, as they play no role in the language accepted by the DFA.
Incorrect! Try again.
42The minimum state DFA recognizing a given regular language is?
A.Always containing a single final state
B.Dependent on the initial NDFA
C.Never unique
D.Unique up to isomorphism (renaming of states)
Correct Answer: Unique up to isomorphism (renaming of states)
Explanation:
For any regular language, the minimal DFA is structurally unique. Any two minimal DFAs for the same language differ only by the arbitrary names given to their states.
Incorrect! Try again.
43Which theorem provides the mathematical foundation for DFA minimization and states that a language is regular if and only if it has a finite number of equivalence classes?
A.Kleene's Theorem
B.Pumping Lemma
C.Arden's Theorem
D.Myhill-Nerode Theorem
Correct Answer: Myhill-Nerode Theorem
Explanation:
The Myhill-Nerode Theorem establishes that a language is regular iff its prefix equivalence relation has a finite number of classes, which correspond directly to the states of the minimal DFA.
Incorrect! Try again.
44If a minimized DFA for a language over has exactly one state which is both the initial and the final state, what is ?
A.
B.
C.
D.The set of all strings ending in 0
Correct Answer:
Explanation:
A single-state DFA where the start state is also final, and has transitions to itself for all inputs, accepts every possible string. Hence, the language is .
Incorrect! Try again.
45The class of languages natively accepted by Finite Automata is called?
A.Regular Languages
B.Context-Sensitive Languages
C.Context-Free Languages
D.Recursively Enumerable Languages
Correct Answer: Regular Languages
Explanation:
Languages that can be recognized by Finite Automata are defined as Regular Languages. They form the simplest class in the Chomsky hierarchy.
Incorrect! Try again.
46If a language is accepted by a DFA, then its complement is?
A.Undecidable
B.Context-Free but not Regular
C.Always Regular
D.Never Regular
Correct Answer: Always Regular
Explanation:
Regular languages are closed under complementation. If a DFA exists for , a DFA can easily be constructed for .
Incorrect! Try again.
47How can one easily construct a DFA for the complement language given a complete DFA for ?
A.Reverse all transition arrows
B.Convert it to an NDFA
C.Change the start state to a final state
D.Swap the sets of final and non-final states
Correct Answer: Swap the sets of final and non-final states
Explanation:
To accept , simply take the DFA for and make all its final states non-final, and all its non-final states final.
Incorrect! Try again.
48Which of the following is NOT a true property of regular languages?
A.Can represent strings requiring an unbounded memory (like for )
B.Closed under intersection
C.Closed under union
D.Accepted by a Finite Automaton
Correct Answer: Can represent strings requiring an unbounded memory (like for )
Explanation:
Finite automata cannot count arbitrarily high due to finite memory. Thus, languages like are context-free but not regular.
Incorrect! Try again.
49Consider a structurally valid finite automaton with states and transitions, but possessing no final states. What language does it accept?
A.The empty language
B.All strings of length 1
C.
D.
Correct Answer: The empty language
Explanation:
If the set of final states is empty, the automaton can never reach an accepting state, regardless of the input. It accepts no strings, yielding the empty language .
Incorrect! Try again.
50A regular language must consist of a finite number of strings. Is this statement true or false?
A.True, because finite automata have finite memory.
B.True, infinite languages require Turing Machines.
C.False, finite automata can accept infinite languages like .
D.False, regular languages cannot be finite.
Correct Answer: False, finite automata can accept infinite languages like .
Explanation:
A 'finite' automaton refers to the number of states, not the size of the language it accepts. Regular languages can be finite or infinite (e.g., , or ).