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
T
Trivedipawan74
Community Contributor
Quizzes Created: 1 | Total Attempts: 216
| Attempts: 216
SettingsSettings
Please wait...
  • 1/10 Questions

    Which one do you like?

    • {q0, q1, q2}
    • {q0, q1}
    • {q0, q1, q2, q3}
    • {q3}
Please wait...
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

Quiz Preview

  • 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

Popular Topics

+ Show more
Back to Top Back to top
Advertisement
×

Wait!
Here's an interesting quiz for you.

We have other quizzes matching your interest.