# Quiz: Theory Of Computation! Computer Science Trivia

25 Questions | Total Attempts: 59  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

• 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

• 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

• 4.
FSM can recognize
• A.

Any grammer

• B.

Only CFG

• C.

Any unambiguous grammar

• D.

Only regular grammar

• 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

• 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

• 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

• 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

• 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

• 10.
The FSM pictured in fig is a
• A.

Mealy Machine

• B.

Moore Machine

• C.

Kleene Machine

• D.

None of these

• 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

• 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

• 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

• 14.
Any given Transition graph has an equivalent
• A.

Regular expression

• B.

DFSM

• C.

NDFSM

• D.

All of these

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

• 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

• 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

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

• 19.
CFG is not closed under
• A.

Union

• B.

Kleene Star

• C.

Complementation

• D.

Product

• 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

• 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

• 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

• 23.
The following grammar is
• A.

Context free

• B.

Regular

• C.

Context sensitive

• D.

LR(k)

• 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

• 25.
The number of internal states of a UTM should be at least
• A.

1

• B.

2

• C.

3

• D.

4

Related Topics Back to top