Introduction To Theory Of Computation! Hardest Trivia Quiz

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 Catherine Halcomb
Catherine Halcomb
Community Contributor
Quizzes Created: 1443 | Total Attempts: 6,686,485
| Attempts: 203
SettingsSettings
Please wait...
  • 1/18 Questions

    For the given FSA which is/are the final state and start state

    • Q0 start state , q1 and q2 final state
    • Q3 start state , q1 and q2 final state
    • Q1 start state , q3 and q2 final state
    • Q1start state , q0 and q3 final state
Please wait...
Introduction To Theory Of Computation! Hardest Trivia Quiz - Quiz
About This Quiz

Dive into the challenging world of automata with the 'Introduction to Theory Of Computation! Hardest Trivia Quiz'. Test your knowledge on DFAs, state minimization, and regular languages, focusing on string patterns and finite automata structures.

Quiz Preview

  • 2. 

    Moore machine is an FSM whose outputs depend on only the present state.

    • True

    • False

    Correct Answer
    A. True
    Explanation
    A Moore machine is a type of Finite State Machine (FSM) where the outputs are determined solely by the current state of the machine. This means that the outputs do not depend on any input signals or transitions between states, but rather only on the present state. Therefore, the given statement that "Moore machine is an FSM whose outputs depend on only the present state" is true.

    Rate this question:

  • 3. 

    Type 3 Grammer is

    • Unrestricted grammar

    • Context-sensitive grammar

    • Context-free grammar

    • Regular grammar

    Correct Answer
    A. Regular grammar
    Explanation
    A Type 3 Grammar, also known as a Regular Grammar, is the simplest form of grammar in the Chomsky hierarchy. It is characterized by rules of the form A -> aB or A -> a, where A and B are non-terminals and a is a terminal symbol. Regular grammars can generate regular languages, which are a subset of context-free languages. These grammars are less powerful than context-sensitive and context-free grammars, as they have fewer restrictions and can only generate languages that can be recognized by finite automata.

    Rate this question:

  • 4. 

    Type 0 Grammer is

    • Unrestricted grammar

    • Context-sensitive grammar

    • Context-free grammar

    • Regular grammar

    Correct Answer
    A. Unrestricted grammar
    Explanation
    Type 0 grammar, also known as unrestricted grammar, is the most powerful type of grammar in the Chomsky hierarchy. It has no restrictions on the production rules and can generate any language that can be recognized by a Turing machine. This means that it can generate any possible string of symbols, making it more expressive than context-sensitive, context-free, and regular grammars. Therefore, the correct answer is unrestricted grammar.

    Rate this question:

  • 5. 

    Type 1 Grammer is

    • Context-sensitive grammar

    • Unrestricted grammar

    • Context-free grammar

    • Regular grammar

    Correct Answer
    A. Context-sensitive grammar
    Explanation
    Type 1 grammar, also known as context-sensitive grammar, is a formal grammar that allows rules to have the form α→β, where α and β are strings of terminals and non-terminals, and the length of α is less than or equal to the length of β. This means that the grammar can rewrite any non-terminal symbol into a string of terminals and non-terminals, as long as the context surrounding the non-terminal allows it. Context-sensitive grammars are more powerful than context-free grammars, which have rules of the form A→β, and regular grammars, which have rules of the form A→a or A→aB.

    Rate this question:

  • 6. 

    Moore machine is an FSM whose outputs depend on the present state and input.

    • True

    • False

    Correct Answer
    A. False
    Explanation
    The statement is incorrect because a Moore machine is a finite state machine (FSM) whose outputs depend only on the present state, not on the input. In a Moore machine, the outputs are associated with the states, while in a Mealy machine, the outputs are associated with the transitions. Therefore, the correct answer is False.

    Rate this question:

  • 7. 

    Type 2 Grammer is

    • Context-free grammar

    • Unrestricted grammar

    • Context-sensitive grammar

    • Regular grammar

    Correct Answer
    A. Context-free grammar
    Explanation
    Context-free grammar is a type of grammar in formal language theory. It is characterized by production rules that consist of a single nonterminal symbol on the left-hand side and a sequence of terminal and/or nonterminal symbols on the right-hand side. This means that the left-hand side can be replaced by the right-hand side in any context without any restrictions. Context-free grammars are widely used in computer science and linguistics to describe the syntax of programming languages and natural languages, respectively.

    Rate this question:

  • 8. 
    Which one of the following is true for this automaton? - ProProfs

    Which one of the following is true for this automaton?

    • B*ab*ab*ab*

    • B*a(a+b)*

    • B*ab*ab*

    • (a+b)*

    Correct Answer
    A. B*a(a+b)*
    Explanation
    The correct answer is b*a(a+b)*. This is because the automaton accepts strings that start with zero or more occurrences of 'b', followed by 'a', followed by zero or more occurrences of 'a' or 'b'. The regular expression b*a(a+b)* represents this pattern accurately.

    Rate this question:

  • 9. 
    The diagram represents which regular expression - ProProfs

    The diagram represents which regular expression

    • Ab

    • A+b

    • A

    • (a+b)*

    Correct Answer
    A. Ab
    Explanation
    The diagram represents the regular expression "ab" because it shows two characters, "a" and "b", connected by an arrow. This indicates that the regular expression matches the sequence "ab" exactly.

    Rate this question:

  • 10. 
    The diagram represents which regular expression - ProProfs

    The diagram represents which regular expression

    • A

    • A+b

    • Ab

    • A*

    Correct Answer
    A. A
    Explanation
    The diagram represents the regular expression "a". This is because the diagram shows a single node labeled "a", indicating that the regular expression matches the string "a" exactly.

    Rate this question:

  • 11. 
    For the above FSA the equivalent minimum state automaton has the following number of states - ProProfs

    For the above FSA the equivalent minimum state automaton has the following number of states

    • 1

    • 2

    • 3

    • 4

    Correct Answer
    A. 2
    Explanation
    The given FSA has two states, one initial state and one final state. This means that the FSA can recognize a language with at least one string. Therefore, the equivalent minimum state automaton for this FSA will also have two states.

    Rate this question:

  • 12. 
    The DFA shown below accepts the set of all strings over {0, 1} that - ProProfs

    The DFA shown below accepts the set of all strings over {0, 1} that

    • End with 00

    • End with 0

    • Begin either with 0 or 1

    • Contain the substring 00

    Correct Answer
    A. End with 00
    Explanation
    The DFA shown in the question accepts the set of all strings over {0,1} that end with "00". This means that any string that is accepted by the DFA will have "00" as its last two characters. The DFA starts at the initial state and transitions through different states based on the input symbols (0 or 1). It reaches an accepting state only if the last two characters of the input string are "00". Therefore, the correct answer is "End with 00".

    Rate this question:

  • 13. 

    An automaton with a finite number of states is called a________

    Correct Answer
    finite automation , finite state machine
    Explanation
    An automaton with a finite number of states is called a finite automation or a finite state machine. This means that the automaton has a limited number of possible states it can be in, and it transitions between these states based on the inputs it receives. The term "finite" in both "finite automation" and "finite state machine" emphasizes the fact that the number of states is finite and not infinite.

    Rate this question:

  • 14. 

    The minimum number of states in any DFA accepting the regular language L = (111+11111)* is 

    • 9

    • 8

    • 11

    • 5

    Correct Answer
    A. 9
    Explanation
    To accept the regular language L = (111+11111)*, we need to consider two cases: when the input starts with 111 and when the input starts with 11111. In the first case, after reading the initial 111, we can either have another 111 or end the string. In the second case, after reading the initial 11111, we can either have another 11111 or end the string. Therefore, we need two states for each case, totaling four states. Additionally, we need a start state and an accepting state for both cases, totaling six states. Finally, we need two more states to handle the transitions between the two cases. Therefore, the minimum number of states in the DFA is 9.

    Rate this question:

  • 15. 

    NDFA is an abbreviation of ________

    Correct Answer
    Non-deterministic Finite Machine , Non-deterministic Finite Automaton,Non deterministic Finite Machine , Non deterministic Finite Automaton.
    Explanation
    The correct answer is "Non-deterministic Finite Machine, Non-deterministic Finite Automaton". This is because NDFA stands for Non-deterministic Finite Automaton, which is a theoretical model of computation used in computer science and formal language theory. It is a type of finite state machine that can be in multiple states at the same time and can transition to different states based on input symbols. The terms "Non-deterministic Finite Machine" and "Non-deterministic Finite Automaton" are alternative ways of referring to the same concept.

    Rate this question:

  • 16. 

    If P does not contain null string, then R = Q + RP has a unique solution that is R = QP* is a ________ Theorem

    Correct Answer
    Aderns, Arden’s , arden’s , ardens
    Explanation
    If the string P does not contain a null string, then the equation R = Q + RP has a unique solution, which is R = QP*. This is known as the Arden's Theorem.

    Rate this question:

Quiz Review Timeline (Updated): Mar 21, 2023 +

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

  • Current Version
  • Mar 21, 2023
    Quiz Edited by
    ProProfs Editorial Team
  • Aug 26, 2019
    Quiz Created by
    Catherine Halcomb
Back to Top Back to top
Advertisement
×

Wait!
Here's an interesting quiz for you.

We have other quizzes matching your interest.