Theory Of Computation! Computer Science Trivia

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 Prof. Rakesh
P
Prof. Rakesh
Community Contributor
Quizzes Created: 4 | Total Attempts: 2,141
| Attempts: 241
Quiz Flashcard
SettingsSettings
Please wait...
  • 1/25 Questions

    Let A = {0,1}, The Possible strings of the length of 'n' that can be formed by elements of the set A is

    • N!
    • N^2
    • N^n
    • 2^n
Please wait...
About This Quiz

Dive into the essentials of theoretical computer science with this quiz focused on computation theory. Test your understanding of finite state machines, regular expressions, and the pumping lemma, crucial for anyone studying computer science.

Theory Of Computation! Computer Science Trivia - Quiz

Quiz Preview

  • 2. 

    The major difference between a Moore and a Mealy machine is that

    • The output of the former depend on the present state and the current input

    • The output of the former depend on the present state

    • The output of the former depend solely on the current state

    • None of these

    Correct Answer
    A. The output of the former depend solely on the current state
    Explanation
    The major difference between a Moore machine and a Mealy machine lies in how they handle output. The key distinction is in when the output is produced—whether it's based solely on the current state (Moore) or on both the current state and input (Mealy).

    Rate this question:

  • 3. 

    The recognizing capability of NDFSM and DFSM

    • May be different

    • Must be different

    • Must be the same

    • None of these

    Correct Answer
    A. Must be the same
    Explanation
    The recognizing capability of Nondeterministic Finite State Machines (NDFSM) and Deterministic Finite State Machines (DFSM) must be the same. This means that both types of machines should be able to recognize the same set of languages. While NDFSMs have the ability to have multiple transitions for a single input symbol, DFSMs have a unique transition for each input symbol. However, by converting an NDFSM to a DFSM using methods like the subset construction algorithm, the recognizing capability can be preserved, ensuring that the two types of machines recognize the same languages.

    Rate this question:

  • 4. 

    FSM can recognize

    • Any grammer

    • Only CFG

    • Any unambiguous grammar

    • Only regular grammar

    Correct Answer
    A. Only regular grammar
    Explanation
    The correct answer is "only regular grammar". A Finite State Machine (FSM) is a computational model that can recognize languages defined by regular grammars. Regular grammars are a subset of formal grammars that can be described using regular expressions or regular language rules. FSMs are not capable of recognizing languages defined by context-free grammars or any other type of grammar. Therefore, the statement "only regular grammar" accurately describes the recognition capabilities of a FSM.

    Rate this question:

  • 5. 

    Pumping lemma is generally used for proving

    • A given grammar is regular

    • A given grammar is not regular

    • Whether two given regular expressions are equivalent

    • None of these

    Correct Answer
    A. A given grammar is not regular
    Explanation
    The pumping lemma is a tool used in formal language theory to prove that a given grammar is not regular. It provides a set of conditions that must hold true for all regular languages, and if these conditions are violated, then the language is not regular. By applying the pumping lemma to a given grammar and finding a contradiction, we can conclude that the grammar is not regular.

    Rate this question:

  • 6. 

    Which of the following pairs of regular expressions are equivalent

    • 1(01)*0 and (10)*10

    • X(xx)* and (xx)*x

    • (ab)*a and a*b*b

    • X*y and x*x'y

    Correct Answer
    A. X(xx)* and (xx)*x
    Explanation
    The given regular expressions "x(xx)*" and "(xx)*x" are equivalent because they both represent strings that start and end with the same character 'x', followed by any number of occurrences of the substring 'xx' in between. The order of the occurrences of 'xx' does not matter, hence the two regular expressions are equivalent.

    Rate this question:

  • 7. 

    The basic limitation of an FSM is that

    • It can't remember arbitrary large amount of information

    • It sometimes recognizes grammars that are not regular

    • It sometimes fails to recognize grammars that are regular

    • All of these

    Correct Answer
    A. It can't remember arbitrary large amount of information
    Explanation
    An FSM, or Finite State Machine, is a computational model that can be in one of a finite number of states at any given time. The basic limitation of an FSM is that it can't remember an arbitrary large amount of information. This means that it has a limited memory capacity and can only store a certain amount of information about its past states and inputs. Therefore, it is unable to remember and process a vast amount of data, which is a significant limitation of this model.

    Rate this question:

  • 8. 

    An FSM can be considered a TM

    • Of finite tape length, rewinding capability and unidirectional tap movement

    • Of finite tape length, without rewinding capability and unidirectional tape movement

    • Of finite tape length, without rewinding capability and bidirectional tape movement

    • Of finite tape length, rewinding capability and bidirectional tape movement

    Correct Answer
    A. Of finite tape length, without rewinding capability and unidirectional tape movement
    Explanation
    An FSM (Finite State Machine) can be considered a TM (Turing Machine) of finite tape length, without rewinding capability and unidirectional tape movement. This means that an FSM operates on a tape with a limited length, it cannot rewind the tape, and it can only move the tape in one direction. This is in contrast to a TM with rewinding capability or bidirectional tape movement, which have more flexibility in their tape operations.

    Rate this question:

  • 9. 

    TM is more powerful than FSM because

    • The tape movement is confined to one direction

    • It has no finite state control

    • It has the capability to remember arbitrary long sequences of input symbols

    • None of these

    Correct Answer
    A. It has the capability to remember arbitrary long sequences of input symbols
    Explanation
    TM (Turing Machine) is more powerful than FSM (Finite State Machine) because it has the capability to remember arbitrary long sequences of input symbols. Unlike FSM, which has a finite number of states and can only remember a limited amount of information, TM has an unbounded tape that allows it to store and retrieve an infinite amount of data. This ability to remember and manipulate unlimited input sequences gives TM a higher level of computational power, making it more versatile and capable of solving complex problems.

    Rate this question:

  • 10. 
    The FSM pictured in fig is a - ProProfs

    The FSM pictured in fig is a

    • Mealy Machine

    • Moore Machine

    • Kleene Machine

    • None of these

    Correct Answer
    A. Mealy Machine
    Explanation
    The FSM pictured in the figure is a Mealy Machine because it is a finite state machine that outputs a value based on both its current state and the input. In a Mealy Machine, the outputs are associated with the transitions between states, meaning that the output is determined by the current state and the input that triggers the transition. This is different from a Moore Machine where the outputs are associated with the states themselves. A Kleene Machine is not a recognized term in the context of finite state machines.

    Rate this question:

  • 11. 

    Which of the following pairs of a regular expressions are not equivalent?

    • (ab)*a and a(ba)*

    • (a+b)* and (a* + b)*

    • (a* +b)* and (a+b)*

    • None of these

    Correct Answer
    A. None of these
    Explanation
    The given regular expressions are all equivalent. In the first pair, both expressions match any string that starts with zero or more occurrences of "ab" followed by an "a". In the second pair, both expressions match any string that consists of zero or more occurrences of "a" or "b". In the third pair, both expressions also match any string that consists of zero or more occurrences of "a" or "b". Therefore, none of the pairs of regular expressions are not equivalent.

    Rate this question:

  • 12. 

    Set of regular languages over a given alphabet set is not closed under

    • Union

    • Complementation

    • Intersection

    • None the of these

    Correct Answer
    A. None the of these
    Explanation
    The set of regular languages over a given alphabet set is closed under union, complementation, and intersection. This means that when we take the union, complement, or intersection of two regular languages, the resulting language is also regular. Therefore, the correct answer is "none of these" because the set of regular languages is closed under all of these operations.

    Rate this question:

  • 13. 
    The FSM in fig recongizes - ProProfs

    The FSM in fig recongizes

    • Any string of odd number of a's

    • Any string of odd number a's and even number b's

    • Any string of even number of a's and even number of b's

    • Any string of even number of a's and odd number of b's

    Correct Answer
    A. Any string of even number of a's and even number of b's
    Explanation
    The FSM in the figure recognizes any string of even number of a's and even number of b's because it starts at state A and transitions to state B when it encounters an 'a', then transitions back to state A when it encounters another 'a'. Similarly, it transitions to state C when it encounters a 'b' and transitions back to state A when it encounters another 'b'. This pattern ensures that the number of 'a's and 'b's in the string is always even.

    Rate this question:

  • 14. 

    Any given Transition graph has an equivalent

    • Regular expression

    • DFSM

    • NDFSM

    • All of these

    Correct Answer
    A. All of these
    Explanation
    The given transition graph can be converted into a regular expression, a deterministic finite state machine (DFSM), or a non-deterministic finite state machine (NDFSM). This means that all of these options are correct. Regular expressions represent a pattern of strings that can be accepted by the transition graph. A DFSM is a computational model that can recognize and accept or reject strings based on the transitions in the graph. Similarly, an NDFSM can also recognize and accept or reject strings, but it allows for multiple possible transitions at each state. Therefore, all of these options are valid representations of the given transition graph.

    Rate this question:

  • 15. 
    The below CFG is equivalent to which regular expression - ProProfs

    The below CFG is equivalent to which regular expression

    • All of these

    • (a + b)*

    • (a + b)(a + b)*

    • (a + b)*(a + b)

    Correct Answer
    A. All of these
    Explanation
    The given CFG is equivalent to all of the regular expressions mentioned - (a + b)*, (a + b)(a + b)*, and (a + b)*(a + b). This means that any string that can be generated by the CFG can also be generated by any of these regular expressions. Conversely, any string generated by any of these regular expressions can also be generated by the CFG. Therefore, all of these regular expressions are equivalent to the given CFG.

    Rate this question:

  • 16. 
    Any string of terminals that can be generated by the following CFG - ProProfs

    Any string of terminals that can be generated by the following CFG

    • Has at least one b

    • Should end in an 'a'

    • Has no consecutive a's or b's

    • Has at least two a's

    Correct Answer
    A. Has at least two a's
    Explanation
    The correct answer states that any string of terminals generated by the given CFG must have at least two 'a's. This means that in order for a string to be valid, it must contain at least two occurrences of the letter 'a'.

    Rate this question:

  • 17. 

    The set {a^nb^n | n=1,2,3......} can be generated by CFG

    • S → ab /aSb

    • S → aaSbb /ab

    • S → ab /aSb /€

    • None of these

    Correct Answer
    A. S → ab /aSb
    Explanation
    The given correct answer is S → ab / aSb. This is because the set {a^nb^n | n=1,2,3......} consists of strings where the number of 'a's is equal to the number of 'b's, and each 'a' is followed by a 'b'. The production rule S → ab / aSb generates strings of this form. The first option, S → aaSbb / ab, generates strings where there are more than one 'a's followed by more than one 'b's, which is not a part of the given set. The third option, S → ab / aSb / ε, includes the possibility of generating empty strings, which is not mentioned in the given set. Therefore, the correct answer is S → ab / aSb.

    Rate this question:

  • 18. 

    Choose the correct statements

    • All languages can be generated by CFG

    • Any regular language has an equivalent CFG.

    • Some non-regular languages can be generated by any CFG

    • Some regular languages can't be generated by any CFG.

    Correct Answer
    A. Any regular language has an equivalent CFG.
    Explanation
    The answer states that any regular language can be generated by a context-free grammar (CFG). This means that for every regular language, there exists a CFG that can generate it. This is a fundamental result in formal language theory, where regular languages are a subset of context-free languages. The statement implies that CFGs are powerful enough to generate regular languages, but it does not imply that all languages can be generated by CFGs.

    Rate this question:

  • 19. 

    CFG is not closed under

    • Union

    • Kleene Star

    • Complementation

    • Product

    Correct Answer
    A. Complementation
    Explanation
    The correct answer is "Complementation" because when we take the complement of a context-free language, the resulting language may not be context-free. Complementation involves swapping the accepting and non-accepting states of a language, which can lead to a change in the structure and properties of the language. Therefore, the complement of a context-free language may not be context-free, making CFG not closed under complementation.

    Rate this question:

  • 20. 

    The set A={an bnan | n=1,2,3,….} is an example of a grammar that is

    • Regular

    • Context free

    • Not context free

    • None of these

    Correct Answer
    A. Not context free
    Explanation
    The set A={an bnan | n=1,2,3,...} is not context-free because it cannot be generated by a context-free grammar. In a context-free grammar, the number of a's and b's on either side of the middle symbol (bn) must be equal. However, in this set, the number of a's on the left side is dependent on the value of n, while the number of a's on the right side is dependent on the value of 2n. Therefore, the set A is not context-free.

    Rate this question:

  • 21. 

    L= {an bnan | n=1,2,3,….} is an example of a language that is

    • Context free

    • Not context free

    • Not context free whose complement is  not CF

    • Context free but whose complement is not CF

    Correct Answer
    A. Not context free
    Explanation
    The language L = {an bnan | n=1,2,3,...} is not context free. This can be proved using the pumping lemma for context-free languages. According to the pumping lemma, if a language is context free, then there exists a constant p (the pumping length) such that any string in the language with length greater than or equal to p can be divided into five parts uvwxy, satisfying certain conditions. However, in the language L, the number of a's and b's are related, and it is not possible to satisfy the conditions of the pumping lemma. Therefore, L is not context free.

    Rate this question:

  • 22. 

    The intersection of a CFL and a regular language.

    • Need not be regular

    • Need not be context free

    • Is complement of regular 

    • Is always CF

    Correct Answer
    A. Is always CF
    Explanation
    The intersection of a context-free language (CFL) and a regular language can be context-free. This is because the intersection of these two languages can be recognized by a pushdown automaton, which is a type of automaton that can recognize context-free languages. Therefore, the intersection is always context-free.

    Rate this question:

  • 23. 
    The following grammar is - ProProfs

    The following grammar is

    • Context free

    • Regular

    • Context sensitive

    • LR(k)

    Correct Answer
    A. Context sensitive
    Explanation
    The given grammar is classified as context-sensitive because it allows for rules where the length of the right-hand side can be greater than or equal to the length of the left-hand side. Context-sensitive grammars are more powerful than regular grammars and context-free grammars, as they can handle a wider range of languages.

    Rate this question:

  • 24. 

    Which of following conversion is not possible algorithmically?

    • Regular Grammar to Context free Grammar

    • Non deterministic FSA to Deterministic FSA

    • Non deterministic PDA to Deterministic PDA

    • Non deterministic TM to Deterministic TM

    Correct Answer
    A. Non deterministic PDA to Deterministic PDA
    Explanation
    The conversion from a non-deterministic pushdown automaton (PDA) to a deterministic PDA is not possible algorithmically. This is because a non-deterministic PDA can have multiple possible transitions for a given input symbol and stack symbol, while a deterministic PDA can only have one. Therefore, it is not possible to determine which transition to take in the deterministic PDA, leading to the impossibility of algorithmically converting a non-deterministic PDA to a deterministic one.

    Rate this question:

  • 25. 

    The number of internal states of a UTM should be at least

    • 1

    • 2

    • 3

    • 4

    Correct Answer
    A. 2
    Explanation
    A Universal Turing Machine (UTM) is a theoretical machine that can simulate any other Turing machine. In order to simulate the behavior of any Turing machine, a UTM needs to have at least two internal states. One state is required to represent the current state of the machine being simulated, and the other state is needed to keep track of the current position on the tape. With these two states, a UTM can effectively simulate the operation of any Turing machine, making 2 the minimum number of internal states required.

    Rate this question:

Quiz Review Timeline (Updated): Feb 4, 2024 +

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

  • Current Version
  • Feb 04, 2024
    Quiz Edited by
    ProProfs Editorial Team
  • Apr 23, 2020
    Quiz Created by
    Prof. Rakesh

Related Topics

Recent Quizzes

Is Computer Science Right For Me? Quiz Is Computer Science Right For Me? Quiz
Algorithmic Evolution: A Quiz on Evolutionary Computing Techniques Algorithmic Evolution: A Quiz on Evolutionary Computing Techniques
Test Your Knowledge: Meta-learning Fundamentals Quiz Test Your Knowledge: Meta-learning Fundamentals Quiz
Rule-Based Machine Learning Quiz: Test Your Knowledge Rule-Based Machine Learning Quiz: Test Your Knowledge
computer science final exam review computer science final exam review
Quiz 1 Set A Quiz 1 Set A
mPhilGEPS Infra Server Installation and Deployment mPhilGEPS Infra Server Installation and Deployment
mPhilGEPS Infra Monitoring and Server Acces mPhilGEPS Infra Monitoring and Server Acces
Computer Science Test Trivia: Quiz! Computer Science Test Trivia: Quiz!

Featured Quizzes

Are You Ready For IQ Quiz: Test Your Intelligence Now Are You Ready For IQ Quiz: Test Your Intelligence Now
Can You Guess These Asian's Nationality? Can You Guess These Asian's Nationality?
Harry Potter House Quiz: Which Hogwarts House Do You Belong To? Harry Potter House Quiz: Which Hogwarts House Do You Belong To?
Do I Have a Crush on Him? Quiz Do I Have a Crush on Him? Quiz
Best Friend Quiz: Are You Really Best Friends? Best Friend Quiz: Are You Really Best Friends?
Articles Quiz With Answers Articles Quiz With Answers
Back to Top Back to top
Advertisement
×

Wait!
Here's an interesting quiz for you.

We have other quizzes matching your interest.