1.
Consider the languages L1 = φ and L2 = {a}. Which one of the following represents L1.L2* U L1*
Correct Answer
A. {Є}
Explanation
The given regular expression represents the language L1.L2* U L1*, which means concatenation of L1 with zero or more repetitions of L2, or zero or more repetitions of L1. Since L1 is empty, L1.L2* will also be empty. L1* represents zero or more repetitions of L1, which is also empty. Therefore, the language represented by the regular expression is {Є}, which is the empty set.
2.
Given the language L = {ab, aa, baa}, which of the following strings are in L*?
1) abaabaaabaa
2) aaaabaaaa
3) baaaaabaaaab
4) baaaaabaa
Correct Answer
C. 1,2 and 4
Explanation
The language L* represents the set of all possible concatenations of strings in L, including the empty string.
In option 1, the string "abaabaaabaa" can be formed by concatenating the strings "ab", "aa", and "baa" from L.
In option 2, the string "aaaabaaaa" can be formed by concatenating the string "aa" twice from L.
In option 3, the string "baaaaabaaaab" cannot be formed by concatenating any combination of strings from L.
In option 4, the string "baaaaabaa" can be formed by concatenating the strings "baa" and "aa" from L.
Therefore, the strings in L* are 1, 2, and 4.
3.
Which one of the following languages over the alphabet {0,1} is described by the regular expression: (0+1)*0(0+1)*0(0+1)*?
Correct Answer
C. The set of all strings containing at least two 0’s.
Explanation
The regular expression (0+1)*0(0+1)*0(0+1)* matches any string in which there are at least two occurrences of the digit 0. The expression (0+1)* allows for any combination of 0s and 1s before and after the two 0s. Therefore, the correct answer is "The set of all strings containing at least two 0's."
4.
Which of the following is TRUE?
Correct Answer
B. Every finite subset of a non-regular set is regular.
5.
Which one do you like?
Correct Answer
A. {q0, q1, q2}
Explanation
The correct answer is {q0, q1, q2} because it includes all the options mentioned in the given list. The other options either include fewer elements or include elements that are not mentioned in the list.
6.
If ∑= {0,1}, then Ф* will result to:
Correct Answer
A. ε
Explanation
The symbol Ф* represents the Kleene star operation, which is used to denote the closure of a set or language. In this case, the set ∑ is given as {0,1}. The closure of a set includes all possible combinations of elements from that set, including the empty string. Therefore, the result of applying the Kleene star operation to ∑ would include the empty string, represented by the symbol ε.
7.
If P and Q are regular expressions then (P+Q)^{*} is equivalent to:
Correct Answer
C. Both a & b
Explanation
The correct answer is "Both a & b". The expression (P+Q)* means that either P or Q can occur any number of times, including zero, in any order. In option a, (P*+Q*)* means that either P or Q can occur any number of times, including zero, separately. In option b, (P* Q*)* means that P and Q can occur any number of times, including zero, together. Therefore, both options a and b are equivalent to (P+Q)*.
8.
Minimum number of states required in DFA to accept strings ending with '10'
Correct Answer
A. 3
Explanation
To accept strings ending with '10', we need to consider all possible combinations of the strings. The DFA should have states that represent different combinations of the string. In this case, we can have three possible states:
1. State 1: Initial state, where no input has been received yet.
2. State 2: After receiving the first '1' in the string.
3. State 3: After receiving '10' at the end of the string.
Thus, a minimum of 3 states is required in the DFA to accept strings ending with '10'.
9.
Which of the following is true?
Correct Answer
B. All DFA are NFA
Explanation
All DFA are NFA because DFA (Deterministic Finite Automaton) is a special case of NFA (Nondeterministic Finite Automaton) where each state has exactly one transition for each input symbol. Therefore, every DFA can be considered as an NFA, but not every NFA can be considered as a DFA.
10.
Choose the correct statement:
Correct Answer
D. Both (a) and (b) are correct
Explanation
The correct answer is "Both (a) and (b) are correct." This is because in general, the output length of an equivalent Moore machine is greater than the output length of a Mealy machine. This is because a Moore machine outputs a value based solely on the current state, whereas a Mealy machine outputs a value based on both the current state and the input. Therefore, the output length of a Moore machine can be larger because it does not depend on the input. However, there may be specific cases where the output lengths are equal, so option (c) is not correct.