1Which of the following is a valid identity for Regular Expressions?
A.
B.
C.
D.
Correct Answer:
Explanation:
Taking the union of any language represented by with the empty language results in the original language. Hence, .
Incorrect! Try again.
2What is the equivalent regular expression for ?
A.
B.
C.
D.
Correct Answer:
Explanation:
The '+' operator in regular expressions denotes the union of languages. Since the union of a set with itself is the same set, . This is the idempotent property.
Incorrect! Try again.
3What is the simplified form of ?
A.
B.
C.
D.
Correct Answer:
Explanation:
Applying the Kleene star operation multiple times does not generate any new strings beyond the first application. Therefore, .
Incorrect! Try again.
4Which of the following regular expressions represents the language of all strings over ?
A.
B.
C.
D.
Correct Answer:
Explanation:
The expression generates any combination of 'a' and 'b' of any length, which encompasses all possible strings over the alphabet .
Incorrect! Try again.
5The regular expression for the language of strings of even length over is:
A.
B.
C.
D.
Correct Answer:
Explanation:
The expression produces all strings of exactly length 2. Applying the Kleene star to this grouping, , allows only even-length combinations.
Incorrect! Try again.
6Which identity correctly describes the relationship between the Kleene star and the positive closure ?
A.
B.
C.
D.
Correct Answer:
Explanation:
The positive closure includes all strings of except the empty string (unless is already in ). Thus, is the correct algebraic relation.
Incorrect! Try again.
7What does the -closure of a state in an NFA represent?
A.The set of states that can reach using -transitions.
B.Only the state itself.
C.The set of states reachable from using any transition.
D.The set of states reachable from using only -transitions.
Correct Answer: The set of states reachable from using only -transitions.
Explanation:
The -closure of is the set of all states that can be reached from along paths containing entirely (null) transitions, including itself.
Incorrect! Try again.
8In terms of language recognition, how does the power of a Non-deterministic Finite Automaton with null moves (-NFA) compare to a standard DFA?
A.It can recognize context-free languages.
B.It is strictly more powerful than a DFA.
C.It has the exact same computational power as a DFA.
D.It is less powerful because -transitions create ambiguity.
Correct Answer: It has the exact same computational power as a DFA.
Explanation:
Although -NFAs provide more flexibility in design, any language accepted by an -NFA can also be accepted by a standard DFA. They define the exact same class of regular languages.
Incorrect! Try again.
9Let denote the -closure of state . Is always true?
A.No, a state is never in its own -closure.
B.Yes, trivially by taking zero -transitions.
C.No, only if there is an explicit self-loop with .
D.Yes, but only if is an accepting state.
Correct Answer: Yes, trivially by taking zero -transitions.
Explanation:
By definition, the -closure of a state always contains the state itself because you can reach it by making zero transitions.
Incorrect! Try again.
10The transition function for an -NFA is defined as ?
A.
B.
C.
D.
Correct Answer:
Explanation:
Because it is non-deterministic, from any state using an input symbol or , the machine can transition to a set of states. This is represented by the power set .
Incorrect! Try again.
11When converting an -NFA to a standard NFA without -moves, what determines if a state becomes a final state?
A.If has an outgoing -transition.
B.If has no incoming transitions.
C.If the -closure of contains at least one final state.
D.If is the start state.
Correct Answer: If the -closure of contains at least one final state.
Explanation:
If a state can reach an original accepting state using only -moves, it must be marked as an accepting state in the newly constructed -free NFA.
Incorrect! Try again.
12The standard algorithm used to convert a Non-deterministic Finite Automaton (NFA) to a Deterministic Finite Automaton (DFA) is called:
A.Thompson's Construction
B.Arden's Method
C.Myhill-Nerode Construction
D.Subset Construction
Correct Answer: Subset Construction
Explanation:
The Subset Construction (or powerset construction) algorithm systematically builds DFA states as subsets of the original NFA states to eliminate non-determinism.
Incorrect! Try again.
13If an NFA has states, what is the maximum number of states the equivalent DFA could possibly have?
A.
B.
C.
D.
Correct Answer:
Explanation:
Since the Subset Construction algorithm models DFA states as elements of the power set of NFA states, and a set of size has subsets, the maximum number of DFA states is .
Incorrect! Try again.
14In the Subset Construction algorithm, a state in the constructed DFA is considered an accepting (final) state if:
A.It is the subset containing only the start state.
B.It contains at least one accepting state of the NFA.
C.It contains all the states of the NFA.
D.It is an empty set.
Correct Answer: It contains at least one accepting state of the NFA.
Explanation:
Because an NFA accepts a string if there is any valid path to a final state, the equivalent DFA must accept if the subset of current possible states includes at least one of those final states.
Incorrect! Try again.
15During the conversion of an NFA to a DFA, a "dead state" is often introduced. This dead state typically corresponds to which subset of NFA states?
A.The subset containing the start state.
B.The set of all final states.
C.The empty subset .
D.The -closure of the start state.
Correct Answer: The empty subset .
Explanation:
If an NFA has no valid transitions for a particular symbol from a set of states, the resulting subset is empty (). In a DFA, this must transition to a trap/dead state.
Incorrect! Try again.
16What is the primary practical reason for converting an NFA to a DFA?
A.To make the automaton deterministic for straightforward implementation in software or hardware.
B.To increase the theoretical set of recognizable languages.
C.To minimize the physical number of states.
D.To allow the automaton to handle context-sensitive languages.
Correct Answer: To make the automaton deterministic for straightforward implementation in software or hardware.
Explanation:
NFAs are easier to design theoretically but hard to program directly without simulating multiple paths. DFAs provide single, deterministic paths making them trivial to implement as state machines in code.
Incorrect! Try again.
17Arden's Theorem is primarily used in automation theory for:
A.Converting a Transition System (DFA/NFA) into a Regular Expression.
B.Minimizing the number of states in a DFA.
C.Converting a Regular Expression to an NFA.
D.Proving that a particular language is not regular.
Correct Answer: Converting a Transition System (DFA/NFA) into a Regular Expression.
Explanation:
Arden's Theorem provides an algebraic method to solve systems of equations representing finite automata, ultimately yielding the equivalent regular expression.
Incorrect! Try again.
18According to Arden's Theorem, if , and does not contain , then the unique solution for is:
A.
B.
C.
D.
Correct Answer:
Explanation:
By repeatedly substituting into the equation (), the geometric series leads to the unique solution assuming .
Incorrect! Try again.
19Solve the state equation using Arden's Theorem.
A.
B.
C.
D.
Correct Answer:
Explanation:
The equation is in the form , where and . According to Arden's theorem, the solution is , which gives .
Incorrect! Try again.
20What specific condition must be satisfied for Arden's Theorem () to guarantee a unique solution?
A.The language must be infinite.
B.The language must not contain .
C.The language must not contain .
D.The language must be empty.
Correct Answer: The language must not contain .
Explanation:
If , the equation has multiple solutions. The uniqueness of requires that does not contain the empty string.
Incorrect! Try again.
21Thompson's Construction algorithm is utilized specifically to:
A.Convert an NFA to a DFA.
B.Construct an -NFA equivalent to a given Regular Expression.
C.Prove the equivalence of two regular languages.
D.Find the minimal equivalent DFA.
Correct Answer: Construct an -NFA equivalent to a given Regular Expression.
Explanation:
Thompson's Construction is a recursive algorithm that builds an -NFA structurally mimicking the abstract syntax tree of a regular expression.
Incorrect! Try again.
22In Thompson's Construction, the base case for recognizing a single alphabet symbol produces an NFA with exactly how many states?
A.2
B.1
C.3
D.4
Correct Answer: 2
Explanation:
For a single symbol 'a', Thompson's construction creates an initial state and a final state, with a single transition labeled 'a' connecting them. Total states = 2.
Incorrect! Try again.
23When applying Thompson's Construction for the union of two regular expressions (), how many completely new states are introduced?
A.2
B.0
C.4
D.1
Correct Answer: 2
Explanation:
The union operation adds one new overarching start state and one new overarching final state, with -transitions connecting to and from the sub-machines for and .
Incorrect! Try again.
24When applying Thompson's Construction for the Kleene Star operation , how many new -transitions are added?
A.1
B.2
C.4
D.3
Correct Answer: 4
Explanation:
Four -transitions are added: new start to old start, new start to new final (bypassing), old final to old start (looping), and old final to new final.
Incorrect! Try again.
25Which of the following properties is universally true for automata generated directly by Thompson's Construction?
A.They never contain -transitions.
B.They allow single transitions mapping to strings of length > 1.
C.They always have exactly one final (accepting) state.
D.They are always minimal DFAs.
Correct Answer: They always have exactly one final (accepting) state.
Explanation:
By design, Thompson's Construction always ensures the resulting -NFA has precisely one initial state and one accepting state.
Incorrect! Try again.
26Two finite automata are formally defined to be equivalent if and only if:
A.They have identical start and final states.
B.They accept exactly the same language.
C.They have the same number of states.
D.They have isomorphic transition graphs.
Correct Answer: They accept exactly the same language.
Explanation:
Automata equivalence strictly depends on their behavior (the language they recognize). Two machines with completely different structures are equivalent if .
Incorrect! Try again.
27A standard, definitive method to test the equivalence of two DFAs, and , is to:
A.Count and compare their number of states.
B.Run them on an infinite string.
C.Minimize both DFAs and check if the resulting graphs are isomorphic.
D.Check if their start states have similar outgoing transitions.
Correct Answer: Minimize both DFAs and check if the resulting graphs are isomorphic.
Explanation:
Because the minimal DFA for a regular language is unique (up to state renaming), two DFAs accept the same language if and only if their minimized versions are identical.
Incorrect! Try again.
28Are the regular expressions and equivalent?
A.No, the second one cannot generate the string 'aba'.
B.Yes, they generate the exact same language.
C.Yes, but only for finite subsets.
D.No, the first one cannot generate the string 'aabb'.
Correct Answer: Yes, they generate the exact same language.
Explanation:
Both expressions define the universal language over . The expression allows any sequence of 's and 's to be repeated, which is equivalent to .
Incorrect! Try again.
29Which of the following regular expressions is NOT equivalent to ?
A.
B.
C.
D.
Correct Answer:
Explanation:
The expression represents strings of only 'a's OR strings of only 'b's. It cannot generate a string with mixed characters like 'ab', unlike , so they are not equivalent.
Incorrect! Try again.
30If and are regular languages, which of the following operations is NOT guaranteed to produce a regular language?
A.Complementation ()
B.Intersection ()
C.Infinite Union of arbitrary regular languages
D.Finite Union ()
Correct Answer: Infinite Union of arbitrary regular languages
Explanation:
Regular languages are closed under finite union, but an infinite union of regular sets can produce non-regular languages (e.g., is not regular).
Incorrect! Try again.
31Regular languages are mathematically closed under which of the following operations?
A.Complementation only.
B.Intersection only.
C.Both Complementation and Intersection.
D.Neither Complementation nor Intersection.
Correct Answer: Both Complementation and Intersection.
Explanation:
By De Morgan's laws and cross-product DFA construction, if and are regular, both their intersection and their complement are guaranteed to be regular.
Incorrect! Try again.
32The complement of a regular language over an alphabet is represented as:
A.
B.
C.
D.
Correct Answer:
Explanation:
The complement of a language contains all valid strings over the alphabet that are not in . This is precisely .
Incorrect! Try again.
33If is a regular language, then the language (the reversal of all strings in ) is:
A.Always finite.
B.Context-Free but strictly non-regular.
C.Undecidable.
D.Regular.
Correct Answer: Regular.
Explanation:
Regular languages are closed under string reversal. One can simply reverse all transitions in an NFA and swap the start and final states to construct a machine for .
Incorrect! Try again.
34The primary purpose of the Pumping Lemma for Regular Sets in automata theory is to:
A.Construct a regular expression from a state machine.
B.Convert an NFA to a minimal DFA.
C.Prove a language is regular.
D.Prove a language is strictly NOT regular.
Correct Answer: Prove a language is strictly NOT regular.
Explanation:
The Pumping Lemma provides a necessary property that all regular languages must possess. If a language fails this property, it is proven to be non-regular.
Incorrect! Try again.
35In the Pumping Lemma for regular sets, an arbitrary string (where ) is divided into three parts: . Which part represents the "pumpable" substring?
A.
B.
C.
D.
Correct Answer:
Explanation:
The substring corresponds to a cycle in the DFA. By repeating (pumping) any number of times , the resulting string must remain in the language.
Incorrect! Try again.
36According to the conditions of the Pumping Lemma for the decomposition , which strict requirement must hold true?
A.
B.
C.
D.
Correct Answer:
Explanation:
For the lemma to work, the pumped portion cannot be empty. If , pumping wouldn't change the string. Thus, the length of must be at least 1.
Incorrect! Try again.
37Let be the pumping length. According to the Pumping Lemma, the length of the prefix must satisfy:
A.
B.
C.
D.
Correct Answer:
Explanation:
By the Pigeonhole Principle, within the first transitions on a DFA with states, a state must repeat. Thus, the loop must complete within the first characters: .
Incorrect! Try again.
38Which of the following classical languages is typically proven to be NON-regular using the Pumping Lemma?
A.
B.
C.
D.
Correct Answer:
Explanation:
The language requires the automaton to "count" the number of 'a's to ensure an equal number of 'b's. Since finite automata have finite memory, they cannot do this for arbitrary , making it non-regular.
Incorrect! Try again.
39Is the Pumping Lemma a sufficient condition to definitively prove that a language IS regular?
A.No, it is only a necessary condition; some non-regular languages can also satisfy the Pumping Lemma.
B.No, because no regular language actually satisfies the Pumping Lemma.
C.Yes, if a language satisfies the Pumping Lemma, it is guaranteed to be regular.
D.Yes, provided the language is defined over a finite alphabet.
Correct Answer: No, it is only a necessary condition; some non-regular languages can also satisfy the Pumping Lemma.
Explanation:
The Pumping Lemma is a necessary but not sufficient condition for regularity. There exist specific non-regular languages that can still be "pumped" without leaving the language.
Incorrect! Try again.
40Which of the following decision properties regarding regular languages is NOT decidable?
A.The Finiteness problem
B.The Emptiness problem
C.None of the above (they are all decidable)
D.The Equivalence problem
Correct Answer: None of the above (they are all decidable)
Explanation:
For regular languages (unlike context-free or Turing-recognizable languages), nearly all standard questions—including emptiness, finiteness, membership, and equivalence—have algorithmic decidable solutions.
Incorrect! Try again.
41The Membership Problem for a regular language essentially asks whether:
A.The language is finite or infinite.
B.The language contains the empty string .
C.Two given regular expressions denote the same language.
D.A specifically given string belongs to the language .
Correct Answer: A specifically given string belongs to the language .
Explanation:
Membership decides if . For regular languages, it is easily solved by simulating the string on the DFA and checking if it halts on an accepting state.
Incorrect! Try again.
42How can the Emptiness problem (?) for a regular language represented by a DFA be decided algorithmically?
A.By applying the Pumping Lemma.
B.By checking if the start state is an accepting state.
C.By analyzing the regular expression for a Kleene star.
D.By performing a graph search to check if ANY final state is reachable from the start state.
Correct Answer: By performing a graph search to check if ANY final state is reachable from the start state.
Explanation:
If no accepting state can be reached from the initial state via valid transitions, the automaton accepts no strings, and the language is empty.
Incorrect! Try again.
43The Finiteness problem (is finite or infinite?) for a DFA can be decided by:
A.Checking if the start state is also a final state.
B.Seeing if the equivalent regular expression contains a union operator.
C.Checking if the number of final states is greater than 1.
D.Checking if there is a cycle on a path from the start state to any final state.
Correct Answer: Checking if there is a cycle on a path from the start state to any final state.
Explanation:
If a DFA graph contains a cycle that is reachable from the start state and can reach a final state, the machine can generate infinitely many strings. Otherwise, the language is finite.
Incorrect! Try again.
44The foundational Myhill-Nerode Theorem states that a language is regular if and only if:
A.The language can be accepted by an -NFA.
B.It can be generated by a Context-Free Grammar.
C.The language strictly obeys the Pumping Lemma.
D.The number of equivalence classes of the relation is finite.
Correct Answer: The number of equivalence classes of the relation is finite.
Explanation:
The Myhill-Nerode Theorem asserts a language is regular exactly when its distinguishing equivalence relation partitions all possible strings into a finite number of equivalence classes.
Incorrect! Try again.
45In the context of the Myhill-Nerode Theorem, the equivalence relation defined over strings is:
A.Right-invariant
B.Left-invariant
C.Reflexive but not symmetric
D.Symmetric but not transitive
Correct Answer: Right-invariant
Explanation:
The relation is right-invariant (or right congruence). This means if strings and are equivalent, then for any string , and must also be equivalent with respect to .
Incorrect! Try again.
46According to the Myhill-Nerode Theorem, the number of equivalence classes of the relation for a regular language corresponds exactly to:
A.The total number of states in any non-deterministic finite automaton (NFA) accepting .
B.The number of states in the minimal deterministic finite automaton (DFA) accepting .
C.The number of symbols in the alphabet .
D.The pumping length of the language.
Correct Answer: The number of states in the minimal deterministic finite automaton (DFA) accepting .
Explanation:
Each equivalence class of maps uniquely to one state in the minimal DFA. Thus, minimizing a DFA equates to finding these equivalence classes.
Incorrect! Try again.
47In DFA minimization algorithms based on Myhill-Nerode, two states and are considered distinguishable if:
A.They both transition to a dead state on some specific input.
B.There exists a string such that exactly one of or ends in an accepting state.
C.They belong to the exact same equivalence class.
D.They have different incoming transitions from the start state.
Correct Answer: There exists a string such that exactly one of or ends in an accepting state.
Explanation:
States and are distinguishable if feeding the same suffix string to both yields different acceptance outcomes (one accepts, one rejects). They must be kept as separate states.
Incorrect! Try again.
48Which mathematical approach is structurally used to combine indistinguishable states and find the minimal DFA?
A.Equivalence Class Partitioning
B.Power Set Construction
C.Subset Construction
D.State Splitting
Correct Answer: Equivalence Class Partitioning
Explanation:
The minimization algorithm starts with a coarse partition (Final vs. Non-Final) and iteratively refines it by partitioning states into finer equivalence classes until no more splits can occur.
Incorrect! Try again.
49Which of the following is an immediate practical application of the Myhill-Nerode Theorem?
A.Finding the shortest path string in a DFA graph.
B.Proving that an ambiguous grammar is minimal.
C.Finding the unique, minimal DFA for a given regular language.
D.Converting an NFA rapidly into a DFA.
Correct Answer: Finding the unique, minimal DFA for a given regular language.
Explanation:
The Myhill-Nerode Theorem's most direct application is identifying indistinguishable strings, allowing the construction of the provably minimal DFA with the fewest possible states.
Incorrect! Try again.
50A regular language is known to be mathematically closed under "homomorphism". What does this operation entail?
A.Converting a standard DFA into a probabilistic NFA.
B.Replacing individual symbols of the alphabet uniformly with specific strings.
C.Extracting all valid subsets of the language.
D.Reversing all strings in the regular language.
Correct Answer: Replacing individual symbols of the alphabet uniformly with specific strings.
Explanation:
A homomorphism maps symbols to strings. Since we can substitute the corresponding regular expression for each symbol in the original language's regex, the result remains regular.
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 →