# Quiz: Theory Of Computation! Computer Science Trivia

Approved & Edited by ProProfs Editorial Team
At ProProfs Quizzes, our dedicated in-house team of experts takes pride in their work. With a sharp eye for detail, they meticulously review each quiz. This ensures that every quiz, taken by over 100 million users, meets our standards of accuracy, clarity, and engagement.
| Written by Prof. Rakesh
P
Prof. Rakesh
Community Contributor
Quizzes Created: 4 | Total Attempts: 1,600
Questions: 25 | Attempts: 164  Settings  .

• 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

D. 2^n
Explanation
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 on the current input

• D.

None of these

B. The output of the former depend on the present state
Explanation
A Moore machine is a type of finite state machine where the outputs are determined solely by the current state. In other words, the output depends on the present state of the machine. On the other hand, a Mealy machine is a type of finite state machine where the outputs are determined by both the current state and the current input. Therefore, the major difference between a Moore and a Mealy machine is that the output of a Moore machine depends only on the present state, while the output of a Mealy machine depends on both the present state and the current input.

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

C. 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

• A.

Any grammer

• B.

Only CFG

• C.

Any unambiguous grammar

• D.

Only regular grammar

D. 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.

A given grammar is regular

• B.

A given grammar is not regular

• C.

Whether two given regular expressions are equivalent

• D.

None of these

B. 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

• 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

B. 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

• 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

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

• 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

B. 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

• 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

C. 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

• A.

Mealy Machine

• B.

Moore Machine

• C.

Kleene Machine

• D.

None of these

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?

• A.

(ab)*a and a(ba)*

• B.

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

• C.

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

• D.

None of these

D. 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

• A.

Union

• B.

Complementation

• C.

Intersection

• D.

None the of these

D. 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

• 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

C. 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

• A.

Regular expression

• B.

DFSM

• C.

NDFSM

• D.

All of these

D. 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

• A.

All of these

• B.

(a + b)*

• C.

(a + b)(a + b)*

• D.

(a + b)*(a + b)

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

• 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

D. 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

• A.

S → ab /aSb

• B.

S → aaSbb /ab

• C.

S → ab /aSb /€

• D.

None of these

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

• 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.

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

C. 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

• A.

Regular

• B.

Context free

• C.

Not context free

• D.

None of these

C. 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

• 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

B. 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.

• A.

Need not be regular

• B.

Need not be context free

• C.

Is complement of regular

• D.

Is always CF

D. 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

• A.

Context free

• B.

Regular

• C.

Context sensitive

• D.

LR(k)

C. 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?

• 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

C. 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

• A.

1

• B.

2

• C.

3

• D.

4 Back to top