Automata And Compiler Design Quiz 2

Approved & Edited by ProProfs Editorial Team

The editorial team at ProProfs Quizzes consists of a select group of subject experts, trivia writers, and quiz masters who have authored over 10,000 quizzes taken by more than 100 million users. This team includes our in-house seasoned quiz moderators and subject matter experts. Our editorial experts, spread across the world, are rigorously trained using our comprehensive guidelines to ensure that you receive the highest quality quizzes.

Learn about Our Editorial Process

| By Trivedipawan74

Trivedipawan74

Community Contributor

Quizzes Created: 1 | Total Attempts: 206

Questions: 10 | Attempts: 206 | Updated: Mar 17, 2023

Questions

Settings

Feedback

During the Quiz End of Quiz

Difficulty

Sequential Easy First Hard First

Play as

Quiz Flashcard

Create your own Quiz

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

Questions and Answers

1.

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

Given the language L = {ab, aa, baa}, which of the following strings are in L*? 1) abaabaaabaa 2) aaaabaaaa 3) baaaaabaaaab 4) baaaaabaa
- A.
  
  1, 2 and 3
- B.
  
  2, 3 and 4
- C.
  
  1,2 and 4
- D.
  
  1, 3 and 4
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.

Rate this question:
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)*?
- A.
  
  The set of all strings containing the substring 00.
- B.
  
  The set of all strings containing at most two 0’s.
- C.
  
  The set of all strings containing at least two 0’s.
- D.
  
  The set of all strings that begin and end with either 0 or 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."

Rate this question:
4.

Which of the following is TRUE?
- A.
  
  Every subset of a regular set is regular.
- B.
  
  Every finite subset of a non-regular set is regular.
- C.
  
  The union of two non-regular sets is not regular.
- D.
  
  Infinite union of finite sets is regular.
Correct Answer
B. Every finite subset of a non-regular set is regular.
5.

Which one do you like?
- A.
  
  {q0, q1, q2}
- B.
  
  {q0, q1}
- C.
  
  {q0, q1, q2, q3}
- D.
  
  {q3}
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.

Rate this question:
6.

If ∑= {0,1}, then Ф* will result to:
- A.
  
  ε
- B.
  
  Ф
- C.
  
  ∑
- D.
  
  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.

If P and Q are regular expressions then (P+Q)^* is equivalent to:
- A.
  
  (P^*+Q^*)^*
- B.
  
  (P^* Q^*)^*
- C.
  
  Both a & b
- D.
  
  None of these
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)*.

Rate this question:
8.

Minimum number of states required in DFA to accept strings ending with '10'
- A.
  
  3
- B.
  
  2
- C.
  
  1
- D.
  
  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:
9.

Which of the following is true?
- A.
  
  All NFA are DFA
- B.
  
  All DFA are NFA
- C.
  
  Both (a) and (b)
- D.
  
  NFA and DFA have different power
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.

Rate this question:
10.

Choose the correct statement:
- A.
  
  Output length of equivalent Moore machine is greater than output length of Mealy machine
- B.
  
  Output length of equivalent Mealy machine is less than output length of Moore machine
- C.
  
  Output length of equivalent Moore machine is one less than output length of Mealy machine
- D.
  
  Both (a) and (b) are correct
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.

Rate this question:

Quiz Review Timeline +

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

Current Version
Mar 17, 2023

Quiz Edited by
ProProfs Editorial Team
Sep 17, 2019

Quiz Created by
Trivedipawan74

Automata And Compiler Design Quiz 2

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

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

Which of the following is TRUE?

Which one do you like?

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

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

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

Which of the following is true?

Choose the correct statement:

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: