Automata And Compiler Design Quiz 2

1. Which one do you like?

{q0, q1, q2}

{q0, q1}

{q0, q1, q2, q3}

{q3}

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.

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.

2. Choose the correct statement:

Output length of equivalent Moore machine is greater than output length of Mealy machine

Output length of equivalent Mealy machine is less than output length of Moore machine

Output length of equivalent Moore machine is one less than output length of Mealy machine

Both (a) and (b) are correct

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.

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.

3. Given the language L = {ab, aa, baa}, which of the following strings are in L*? 1) abaabaaabaa 2) aaaabaaaa 3) baaaaabaaaab 4) baaaaabaa

1, 2 and 3

2, 3 and 4

1,2 and 4

1, 3 and 4

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.

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.

4. 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)*?

The set of all strings containing the substring 00.

The set of all strings containing at most two 0’s.

The set of all strings containing at least two 0’s.

The set of all strings that begin and end with either 0 or 1

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."

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."

5. Minimum number of states required in DFA to accept strings ending with '10'

3

2

1

Can not be represented

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'.

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'.

6. If ∑= {0,1}, then Ф* will result to:

ε

Ф

∑

None of the mentioned

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 ε.

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. Which of the following is true?

All NFA are DFA

All DFA are NFA

Both (a) and (b)

NFA and DFA have different power

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.

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.

8. If P and Q are regular expressions then (P+Q)^* is equivalent to:

(P*+Q*)*

(P* Q*)*

Both a & b

None of these

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)*.

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)*.

9. Which of the following is TRUE?

Every subset of a regular set is regular.

Every finite subset of a non-regular set is regular.

The union of two non-regular sets is not regular.

Infinite union of finite sets is regular.

not-available-via-ai

Explanation

not-available-via-ai

10. Consider the languages L1 = φ and L2 = {a}. Which one of the following represents L1.L2* U L1*

{Є}

φ

A*

{Є, a}

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.

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.