Automata And Compiler Design Quiz 2

Reviewed by Editorial Team

The ProProfs editorial team is comprised of experienced subject matter experts. They've collectively created over 10,000 quizzes and lessons, serving over 100 million users. Our team includes in-house content moderators and subject matter experts, as well as a global network of rigorously trained contributors. All adhere to our comprehensive editorial guidelines, ensuring the delivery of high-quality content.

Learn about Our Editorial Process

| By Trivedipawan74

Trivedipawan74

Community Contributor

Quizzes Created: 1 | Total Attempts: 216

| Attempts: 216

Questions

Feedback

During the Quiz End of Quiz

Difficulty

Easy First Hard First Sequential

Share on Facebook Share on Twitter Share on Whatsapp Share on Pinterest Share on Email Copy to Clipboard Embed on your website

1/10 Questions

Which one do you like?
- {q0, q1, q2}
- {q0, q1}
- {q0, q1, q2, q3}
- {q3}

About This Quiz

This quiz focuses on topics of automata theory and compiler design, exploring language operations, regular expressions, and fundamental concepts of computability within formal language theory.

Automata And Compiler Design Quiz 2 - Quiz

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
Correct Answer

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

Rate this question:
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
Correct Answer

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

Rate this question:
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
Correct Answer

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

Rate this question:
5.

Minimum number of states required in DFA to accept strings ending with '10'
- 3
- 2
- 1
- Can not be represented
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'.

Rate this question:
6.

If ∑= {0,1}, then Ф* will result to:
- ε
- Ф
- ∑
- None of the mentioned
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 ε.

Rate this question:
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
Correct Answer

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

Rate this question:
8.

If P and Q are regular expressions then (P+Q)^* is equivalent to:
- (P^*+Q^*)^*
- (P^* Q^*)^*
- Both a & b
- None of these
Correct Answer

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

Rate this question:
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.
Correct Answer

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

Consider the languages L1 = φ and L2 = {a}. Which one of the following represents L1.L2* U L1*
- {Є}
- φ
- A^*
- {Є, a}
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.

Rate this question:

Quiz Review Timeline (Updated): Jan 16, 2025 +

Our quizzes are rigorously reviewed, monitored and continuously updated by our expert board to maintain accuracy, relevance, and timeliness.

Current Version
Jan 16, 2025

Quiz Edited by
ProProfs Editorial Team
Sep 17, 2019

Quiz Created by
Trivedipawan74

Automata And Compiler Design Quiz 2

Which one do you like?

Quiz Preview

Choose the correct statement:

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

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

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

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

Which of the following is true?

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

Which of the following is TRUE?

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

Automata And Compiler Design Quiz 2

Which one do you like?

Quiz Preview

Choose the correct statement:

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

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

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

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

Which of the following is true?

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

Which of the following is TRUE?

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

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

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