1What is an alphabet in the context of Automata Theory?
A.A finite, non-empty set of symbols
B.An infinite set of characters
C.A finite set of states
D.A set of all possible words over a language
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.1
C.Undefined
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.Intersection
B.Union
C.Concatenation
D.Kleene Star
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.A finite set of states
C.A finite set of input symbols
D.The transition function
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.Linear Bounded Automaton
B.Pushdown Automaton
C.Finite Automaton
D.Turing Machine
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.Zero or one
B.Exactly one
C.More than one
D.Exactly zero
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.It accepts formal languages
B.It has a finite set of states
C.It has a designated start state
D.Multiple transitions from a single state on the same input symbol
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, but only if the language is finite.
B.No, because they accept different classes of languages.
C.Yes, a DFA is a special case of an NDFA where each state has exactly one transition per input symbol.
D.No, because a DFA does not allow multiple transitions.
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.NDFA is more powerful than DFA
C.They have equal computational power
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 shaded node
B.By an incoming arrow not originating from any other state
C.By a double circle
D.By a dotted circle
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 set of all possible initial states
B.The next state after reading a single symbol
C.The final state reached from state after reading the entire string
D.The length of the string
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.Contains all states of
B.Contains at least one state in
C.Contains no states in
D.Is exactly equal to
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.Dead state (or Trap state)
B.Accepting state
C.Start state
D.Final 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.Rejected
D.Passed to an NDFA
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.State Elimination Method
C.Myhill-Nerode Construction
D.Hopcroft's Algorithm
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.
B.Both are deterministic
C.They have identical transition diagrams
D.They have the same number of states
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 at least one final state of the NDFA
B.It contains all the states of the NDFA
C.It contains only final states of the NDFA
D.It is the start 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 without consuming any input symbol (including itself)
B.The set of all states reachable from on a specific input symbol
C.The set of final states reachable from
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.Both the current state and the current input
C.The final state
D.Only 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.For every Moore machine, there is an equivalent Mealy machine and vice versa
B.Mealy machines have more computational power than Moore machines
C.Neither machine can be converted into the other
D.Moore machines have more computational power than Mealy machines
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.Subset Construction
B.Thompson's 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 are non-final states
B.One is a final state and the other is a non-final state
C.Both are final states
D.Both have self-loops
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.Dead states
B.The start state
C.States that are either both final or both non-final
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.Removing all final states
B.Making all states accepting
C.Removing all unreachable states from the start state
D.Converting the DFA to an NDFA
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.Unique up to isomorphism (renaming of states)
B.Always containing a single final state
C.Never unique
D.Dependent on the initial NDFA
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.Pumping Lemma
B.Arden's Theorem
C.Kleene'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.The set of all strings ending in 0
D.
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.Context-Sensitive Languages
B.Recursively Enumerable Languages
C.Regular Languages
D.Context-Free 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.Never Regular
B.Always Regular
C.Context-Free but not Regular
D.Undecidable
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.Convert it to an NDFA
B.Change the start state to a final state
C.Reverse all transition arrows
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.Closed under union
B.Accepted by a Finite Automaton
C.Can represent strings requiring an unbounded memory (like for )
D.Closed under intersection
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.
C.All strings of length 1
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.False, finite automata can accept infinite languages like .
B.True, because finite automata have finite memory.
C.True, infinite languages require Turing Machines.
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 ).
Incorrect! Try again.
Did this save you a night before the exam?
LPU Notes is free, and it stays free. Ads cover part of the server bill.
The rest comes out of a student's own pocket: the domain, the storage,
and keeping the site up through the weeks everyone needs it at once.
The payment button didn't load. An ad blocker or a filtered network is the usual reason.
to try again.
Nothing here is ever locked, and nothing unlocks. Chip in only if it was worth it.
What it pays for →