206
101.1k

170+ Theory of Computation Solved MCQs

These multiple-choice questions (MCQs) are designed to enhance your knowledge and understanding in the following areas: Computer Science Engineering (CSE) , Master of Computer Applications (MCA) .

Chapters

Take a Test
Chapter: Unit 2
51.

Which of the following denotes Chomskianhiearchy?

A. REG ⊂ CFL ⊂ CSL ⊂ type0
B. CFL ⊂ REG ⊂ type0 ⊂ CSL
C. CSL ⊂ type0 ⊂ REG ⊂ CFL
D. CSL ⊂ CFL ⊂ REG ⊂ type0
Answer» A. REG ⊂ CFL ⊂ CSL ⊂ type0
discuss
52.

The concept of FSA is much used in this part of the compiler

A. Lexical analysis
B. Parser
C. Code generation
D. Code optimization
Answer» A. Lexical analysis
discuss
53.

The following grammar G = (N, T, P, S)**spaceN = {S, A, B, C, D, E}**spaceT = {a, b, c}**spaceP : S → aAB**spaceAB → CD**spaceCD → CE**spaceC → aC**spaceC → b**spacebE → bc is

A. is type 3
B. is type 2 but not type 3
C. is type 1 but not type 2
D. is type 0 but not type 1
Answer» C. is type 1 but not type 2
discuss
54.

The following CFG is in S → aBB**spaceB → bAA**spaceA → a**spaceB → b

A. Chomsky normal form but not strong Chomsky normal form
B. Weak Chomsky normal form but not Chomsky normal form
C. Strong Chomsky normal form
D. Greibach normal form
Answer» D. Greibach normal form
discuss
55.

Which of the following statements is wrong?

A. The regular sets are closed under intersection
B. The class of regular sets is closed under substitution
C. The class of regular sets is closed under homomorphism
D. Context Sensitive Grammar(CSG) can be recognized by Finite State Machine
Answer» D. Context Sensitive Grammar(CSG) can be recognized by Finite State Machine
discuss
56.

Context free grammar is not closed under

A. Product operation
B. Union
C. Complementation
D. kleene star
Answer» C. Complementation
discuss
57.

Let the class of language accepted by finite state machine be L1 and the class of languages represented by regular expressions be L2 then

A. L1
B. L1>=L2
C. L1 U L2 = .*
D. L1=L2
Answer» D. L1=L2
discuss
58.

Which of the following statement is wrong?

A. Any regular language has an equivalent context-free grammar.
B. Some non-regular languages can’t be generated by any context-free grammar
C. Intersection of context free language and a regular language is always context-free
D. All languages can be generated by context- free grammar
Answer» D. All languages can be generated by context- free grammar
discuss
59.

Grammar that produce more than one Parse tree for same sentence is:

A. Ambiguous
B. Unambiguous
C. Complementation
D. Concatenation
Answer» A. Ambiguous
discuss
60.

The language accepted by a Push down Automata:

A. Type 0
B. Type 1
C. Type 2
D. Type 3
Answer» C. Type 2
discuss
61.

The PDA is called non-deterministic PDA when there are more than one out going edges from……… state:

A. START or READ
B. POP or REJECT
C. READ or POP
D. PUSH or POP
Answer» C. READ or POP
discuss
62.

Let L be a language defined over an alphabet ∑,then the language of strings , defined over ∑, not belonging to L denoted by LC or L. is called :

A. Non regular language of L
B. Complement of the language L
C. None of the given
D. All of above
Answer» B. Complement of the language L
discuss
63.

All NonNull words of the CFL can be generated by the corresponding CFG which is in CNF i.e the grammar in CNF will generate the same language except the:

A. String
B. Regular language
C. Null string
D. None of the above
Answer» C. Null string
discuss
64.

Let L={w (0 + 1)* w has even number of 1s}, i.e. L is the set of all bit strings with even number of 1s. Which one of the regular expression below represents L?

A. (0*10*1)*
B. 0*(10*10*)*
C. 0*(10*1*)*0*
D. 0*1(10*1)*10*
Answer» B. 0*(10*10*)*
discuss
65.

Consider the following Finite State Automaton The language accepted by this automaton is given by the regular expression

A. b*ab*ab*ab
B. (a+b)*
C. b*a(a+b)*
D. b*ab*ab
Answer» C. b*a(a+b)*
discuss
66.

Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?

A. L2-L1 is recursively enumerable
B. L1-L3 is recursively enumerable
C. L2 intersection L1 is recursively enumerable
D. L2 union L1 is recursively enumerable
Answer» B. L1-L3 is recursively enumerable
discuss
67.

Let L denotes the language generated by the grammar S – OSO/00. Which of the following is true?

A. L = O
B. L is regular but not O
C. L is context free but not regular
D. L is not context free
Answer» B. L is regular but not O
discuss
68.

Let S and T be language over ={a,b} represented by the regular expressions (a+b*)* and (a+b)*, respectively. Which of the following is true?

A. ScT (S is a subset of T)
B. TcS (T is a subset of S)
C. S=T
D. SnT=Ø
Answer» C. S=T
discuss
69.

Which of the following pairs have DIFFERENT expressive power?

A. Deterministic finite automata (DFA) and Non-Deterministic finite automata(NFA)
B. Deterministic push down automata (DPDA) and Non-deterministic pushdown automata
C. Deterministic single-tape Turing machine and Non-deterministic single-tape Turing Machine
D. Single-tape Turing machine and multi-tape Turing machine
Answer» B. Deterministic push down automata (DPDA) and Non-deterministic pushdown automata
discuss
70.

Match all items in Group 1 with correct options from those given in Group 2. List I List II**spaceP. Regular Expression 1. Syntax analysis**spaceQ. Push down automata 2. Code Generation**spaceR. Dataflow analysis 3. Lexical analysis**spaceS. Register allocation 4. Code optimization

A. P-4, Q-1, R-2, S-3
B. P-3, Q-1, R-4, S-2
C. P-3, Q-4, R-1, S-2
D. P-2, Q-1, R-4, S-3
Answer» B. P-3, Q-1, R-4, S-2
discuss
71.

A minimum state deterministic finite automation accepting the language L = {W W € {0,1}* , number of 0's and 1's in W are divisible by 3 and 5 respectively has

A. 15 states
B. 11 states
C. 10 states
D. 9 states
Answer» A. 15 states
discuss
Chapter: Unit 3
72.

Any Language generated by an unrestricted grammar is:

A. Recursive
B. Recursively Enumerable
C. Not Recursive
D. None of the above
Answer» A. Recursive
discuss
73.

The Family of recursive language is not closed under which of the following operations:

A. Union
B. Intersection
C. Complementation
D. None of the above.
Answer» D. None of the above.
discuss
74.

PCP is:

A. Decidable
B. Undecidable
C. Sometimes Decidable
D. None of the
Answer» B. Undecidable
discuss
75.

If PCP is decidable then MPCP is

A. Decidable
B. Undecidable
C. Can’t Say
D. None of the
Answer» C. Can’t Say
discuss
76.

Consider a language L for which there exists a Turing machine ™, T, that accepts every word in L and either rejects or loops for every word that is not in L. The language L is

A. NP hard
B. NP complete
C. Recursive
D. Recursively enumerable
Answer» D. Recursively enumerable
discuss
77.

Consider the following statements
I. Recursive languages are closed under complementation
II. Recursively enumerable languages are closed under union
III. Recursively enumerable languages are closed under complementation
Which of the above statement are TRUE?

A. I only
B. I and II
C. I and III
D. II and III
Answer» B. I and II
discuss
78.

Recursively enumerable languages are not closed under

A. Union
B. homomorphism
C. complementation
D. concatenation
Answer» C. complementation
discuss
79.

Which of the following problem is undecidable?

A. Membership problem for CFL
B. Membership problem for regular sets
C. Membership problem for CSL
D. Membership problem for type 0 languages
Answer» D. Membership problem for type 0 languages
discuss
80.

Recursive languages are

A. A proper superset of CFL
B. Always recognized by PDA
C. Are also called type 0 languages
D. Always recognized by FSA
Answer» A. A proper superset of CFL
discuss
81.

Consider the following problem x. Given a Turing machine M over the input alphabet Σ, any state q of M. And a word w Є Σ*, does the computation of M on w visit the state q? Which of the following statements about x is correct?

A. X is decidable
B. X is undecidable but partially decidable
C. X is undecidable and not even partially decidable
D. X is not a decision problem
Answer» A. X is decidable
discuss
82.

If a language is denoted by a regular expression L = ( x )* (x y x ), then which of the following is not a legal string within L ?

A. yx
B. xyx
C. x
D. xyxyx
Answer» D. xyxyx
discuss
83.

Given A = {0,1} and L = A*. If R = (0n1n, n > 0), then language L ∪ R and R are respectively

A. Regular, regular
B. Not regular, regular
C. Regular, not regular
D. Context free, not regular
Answer» D. Context free, not regular
discuss
84.

If L1 and L2 are context free language and R a regular set, then which one of the languages below is not necessarily a context free language?

A. L1 L2
B. L1 ∩ L2
C. L1 ∩ R
D. L1 ∪ L2
Answer» B. L1 ∩ L2
discuss
85.

The logic of pumping lemma is a good example of

A. Pigeon-hole principle
B. Divide-and-conquer technique
C. Recursion
D. Iteration
Answer» A. Pigeon-hole principle
discuss
86.

For two regular languages L1 = (a + b)* a and L2 = b (a + b ) *, the intersection of L1 and L2 is given by

A. (a + b ) * ab
B. ab (a + b ) *
C. a ( a + b ) * b
D. b (a + b ) * a
Answer» D. b (a + b ) * a
discuss
87.

Pumping lemma is generally used for proving that

A. Given grammar is regular
B. Given grammar is not regular
C. Whether two given regular expressions are equivalent or not
D. None of these
Answer» B. Given grammar is not regular
discuss
88.

What is the highest type number which can be applied to the following grammar? S —>Aa, A —> Ba, B —>abc

A. Type 0
B. Type 1
C. Type 2
D. Type 3
Answer» C. Type 2
discuss
89.

Following syntax-directed translation scheme is used with a shift reduction (bottom up) parser that perform the action in braces immediately after a reduction by the corresponding production
A —>aB {print “(1)” A —> c {print “1”),
B —>Ab {print *2”}.
When parser is aaacbbb, then string printed

A. 0202021
B. 1202020
C. 1020202
D. None of these
Answer» A. 0202021
discuss
90.

FSM can recognize

A. Any grammar
B. Only CG
C. Both (a) and ( b )
D. Only regular grammar
Answer» D. Only regular grammar
discuss
91.

Basic limitation of FSM is that it

A. Cannot remember arbitrary large amount of information
B. Sometimes fails to recognize grammars that are regular
C. Sometimes recognizes grammars are not regular
D. None of these
Answer» A. Cannot remember arbitrary large amount of information
discuss
92.

Which of the following are decidable?
1) Whether the intersection of two regular language is infinite.
2) Whether a given context free language is regular.
3) Whether two push down automata accept the same language.
4) Whether a given grammar is context free.

A. 1 and 2
B. 1 and 4
C. 2 and 3
D. 2 and 4
Answer» B. 1 and 4
discuss
93.

If L and L¯ are recursively enumerable, then L is

A. Regular
B. Context free
C. Context sensitive
D. Recursive
Answer» D. Recursive
discuss
94.

Which of the following problems is undecidable?

A. Membership problem for CFGs
B. Ambiguity problem for CFGs.
C. Finiteness problem for FSAs.
D. Equivalence problem for FSAs.
Answer» B. Ambiguity problem for CFGs.
discuss
95.

Fred created a new automaton model which is a push down automaton but with two stacks and the added ability of having commands which do not read input tape but which can pop from one stack and push into the other.This new automaton can recognize (choose strongest result)

A. Context Free Language
B. Context sensitive language
C. Regular language
D. Languages recognizable by Turing machine
Answer» D. Languages recognizable by Turing machine
discuss
96.

Which of the following statements is/are FALSE?
(1) For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine.
(2) Turing recognizable languages are closed under union and complementation.
(3) Turing decidable languages are closed under intersection and complementation
(4) Turing recognizable languages are closed under union and intersection.

A. 1 and 4 only
B. 1 and 3 only
C. 2 only
D. 3 only
Answer» C. 2 only
discuss
97.

Consider a string s over (0+1)*. The number of 0’s in s is denoted by no(s) and the number of 1’s in s is denoted by n1(s). The language that is not regular is

A. L = {s ε (0+1)* I for every prefix s’ of s, I no(s’)-n1(s’) I ≤ 2}
B. L = {s ε (0+1)* I no(s) mod 7 = n1(s) mod 5 = 0}
C. L = {s ε (0+1)* I no(s) is a 3 digit prime}
D. L = {s ε (0+1)* I no(s)-n1(s) I ≤ 4
Answer» D. L = {s ε (0+1)* I no(s)-n1(s) I ≤ 4
discuss
98.

Which one of the following is true regarding FOTRAN?

A. It is a context free language
B. It is a context sensitive language
C. It is a regular language
D. None of the above
Answer» B. It is a context sensitive language
discuss
99.

Which statement is true?

A. The PDA must have one accept state and one reject state
B. The PDA must have one accept state and two reject state
C. The PDA must have two accept state and two reject state
D. There is no reject state in the PDA.
Answer» D. There is no reject state in the PDA.
discuss
100.

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
Answer» B. It has no finite state control
discuss

Done Studing? Take A Test.

Great job completing your study session! Now it's time to put your knowledge to the test. Challenge yourself, see how much you've learned, and identify areas for improvement. Don’t worry, this is all part of the journey to mastery. Ready for the next step? Take a quiz to solidify what you've just studied.

Take a Test