Theory Of Computation! Computer Science Trivia
(41).jpg "Theory Of Computation! Computer Science Trivia - Quiz")
.
- 1.
Let A = {0,1}, The Possible strings of the length of 'n' that can be formed by elements of the set A is
- A.
N!
- B.
N^2
- C.
N^n
- D.
2^n
Correct Answer
D. 2^nExplanation
The set A has two elements, 0 and 1. To form a string of length n, we have 2 choices for each position in the string, either 0 or 1. Therefore, the total number of possible strings is 2 raised to the power of n, which is represented as 2^n.Rate this question:
-
- 2.
The major difference between a Moore and a Mealy machine is that
- A.
The output of the former depend on the present state and the current input
- B.
The output of the former depend on the present state
- C.
The output of the former depend solely on the current state
- D.
None of these
Correct Answer
C. The output of the former depend solely on the current stateExplanation
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
- A.
May be different
- B.
Must be different
- C.
Must be the same
- D.
None of these
Correct Answer
C. Must be the sameExplanation
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
- A.
Any grammer
- B.
Only CFG
- C.
Any unambiguous grammar
- D.
Only regular grammar
Correct Answer
D. Only regular grammarExplanation
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.
A given grammar is regular
- B.
A given grammar is not regular
- C.
Whether two given regular expressions are equivalent
- D.
None of these
Correct Answer
B. A given grammar is not regularExplanation
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
- A.
1(01)*0 and (10)*10
- B.
X(xx)* and (xx)*x
- C.
(ab)*a and a*b*b
- D.
X*y and x*x'y
Correct Answer
B. X(xx)* and (xx)*xExplanation
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
- A.
It can't remember arbitrary large amount of information
- B.
It sometimes recognizes grammars that are not regular
- C.
It sometimes fails to recognize grammars that are regular
- D.
All of these
Correct Answer
A. It can't remember arbitrary large amount of informationExplanation
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
- A.
Of finite tape length, rewinding capability and unidirectional tap movement
- B.
Of finite tape length, without rewinding capability and unidirectional tape movement
- C.
Of finite tape length, without rewinding capability and bidirectional tape movement
- D.
Of finite tape length, rewinding capability and bidirectional tape movement
Correct Answer
B. Of finite tape length, without rewinding capability and unidirectional tape movementExplanation
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
- A.
The tape movement is confined to one direction
- B.
It has no finite state control
- C.
It has the capability to remember arbitrary long sequences of input symbols
- D.
None of these
Correct Answer
C. It has the capability to remember arbitrary long sequences of input symbolsExplanation
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
- A.
Mealy Machine
- B.
Moore Machine
- C.
Kleene Machine
- D.
None of these
Correct Answer
A. Mealy MachineExplanation
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?
- A.
(ab)*a and a(ba)*
- B.
(a+b)* and (a* + b)*
- C.
(a* +b)* and (a+b)*
- D.
None of these
Correct Answer
D. None of theseExplanation
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
- A.
Union
- B.
Complementation
- C.
Intersection
- D.
None the of these
Correct Answer
D. None the of theseExplanation
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
- A.
Any string of odd number of a's
- B.
Any string of odd number a's and even number b's
- C.
Any string of even number of a's and even number of b's
- D.
Any string of even number of a's and odd number of b's
Correct Answer
C. Any string of even number of a's and even number of b'sExplanation
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
- A.
Regular expression
- B.
DFSM
- C.
NDFSM
- D.
All of these
Correct Answer
D. All of theseExplanation
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
- A.
All of these
- B.
(a + b)*
- C.
(a + b)(a + b)*
- D.
(a + b)*(a + b)
Correct Answer
A. All of theseExplanation
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
- A.
Has at least one b
- B.
Should end in an 'a'
- C.
Has no consecutive a's or b's
- D.
Has at least two a's
Correct Answer
D. Has at least two a'sExplanation
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
- A.
S → ab /aSb
- B.
S → aaSbb /ab
- C.
S → ab /aSb /€
- D.
None of these
Correct Answer
A. S → ab /aSbExplanation
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
- A.
All languages can be generated by CFG
- B.
Any regular language has an equivalent CFG.
- C.
Some non-regular languages can be generated by any CFG
- D.
Some regular languages can't be generated by any CFG.
Correct Answer
B. 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
- A.
Union
- B.
Kleene Star
- C.
Complementation
- D.
Product
Correct Answer
C. ComplementationExplanation
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
- A.
Regular
- B.
Context free
- C.
Not context free
- D.
None of these
Correct Answer
C. Not context freeExplanation
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
- A.
Context free
- B.
Not context free
- C.
Not context free whose complement is not CF
- D.
Context free but whose complement is not CF
Correct Answer
B. Not context freeExplanation
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.
- A.
Need not be regular
- B.
Need not be context free
- C.
Is complement of regular
- D.
Is always CF
Correct Answer
D. Is always CFExplanation
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
- A.
Context free
- B.
Regular
- C.
Context sensitive
- D.
LR(k)
Correct Answer
C. Context sensitiveExplanation
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?
- A.
Regular Grammar to Context free Grammar
- B.
Non deterministic FSA to Deterministic FSA
- C.
Non deterministic PDA to Deterministic PDA
- D.
Non deterministic TM to Deterministic TM
Correct Answer
C. Non deterministic PDA to Deterministic PDAExplanation
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
- A.
1
- B.
2
- C.
3
- D.
4
Correct Answer
B. 2Explanation
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 +
Our quizzes are rigorously reviewed, monitored and continuously updated by our expert board to maintain accuracy, relevance, and timeliness.
-
Current Version
-
Feb 04, 2024Quiz Edited by
ProProfs Editorial Team -
Apr 23, 2020Quiz Created by
Prof. Rakesh
- Binary Code Quizzes
- Computer Concept Quizzes
- Computer Essential Quizzes
- Computer Forensics Quizzes
- Computer Hardware Quizzes
- Computer Networking Quizzes
- Computer Parts Quizzes
- Computer Programming Quizzes
- Computer Security Quizzes
- Computer Shortcut Key Quizzes
- Computer Skills Quizzes
- Computer Virus Quizzes
- Cyber Security Quizzes
- Data Quizzes
- Data Security Quizzes
- Hacking Quizzes
- HCI Quizzes
- IT SecurITy Quizzes
- Malware Quizzes
- Microprocessor Quizzes
- Network Quizzes
- Phishing Quizzes
- Programming Language Quizzes
- Server Quizzes
Back to top