Consider a graph G = (V, E) where I V I is divisible by 3. The problem of finding a Hamiltonian cycle in a graph is denoted by SHAM3 and the problem of determining if a Hamiltonian cycle exits in such graph is denoted by DHAM3. The option, which holds true, is

Neither SHAM3 nor DHAM3 is NP-hard

Both SHAM3 and DHAM3 are NP-hard

Neither SHAM3 nor DHAM3 is NP-hard

Two persons X and Y have been asked to show that a certain problem p is NP-complete. X shows a polynomial time reduction from the 3-SAT problem to p and Y shows a polynomial time reduction from p to 3-SAT. From these reduction it can be inferred that

P is NP-hard but not NP-complete

Recursive languages are

Are also called type 0 languages

A random access machine (RAM) and truing machine are different in

both accessing and storage are correct

Which of the following problem is undecidable?

Membership problem for regular sets

Membership problem for type 0 languages

Pumping lemma is generally used for proving that

Whether two given regular expressions are equivalent or not

Any given transition graph has an equivalent:

DFSM (Deterministic Finite State Machine)

Which one of the following languages over the alphabet {0,1} is describedby the regular expression: (0+1)*0(0+1)*0(0+1)*?

The set of all strings that begin and end with either 0 or 1.

The set of all strings containing the substring 00.

The set of all strings containing at most two 0’s.

The set of all strings containing at least two 0’s.

The set of all strings that begin and end with either 0 or 1.

Which one of the following is true regarding FOTRAN?

It is a context sensitive language

Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph G =(V,E)with V divisible by 3 and DHAM3 be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?

SHAM3 is NP-hard, but DHAM3 is not

Both DHAM3 and SHAM3 are NP-hard

SHAM3 is NP-hard, but DHAM3 is not

DHAM3 is NP-hard, but SHAM3 is not

Neither DHAM3 nor SHAM3 is NP-hard

TM is more powerful than FSM because

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

The tape movement is confined to one direction

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

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?

X is undecidable but partially decidable

X is undecidable and not even partially decidable

Which of the following statements is wrong ?

For every DFA there is a regular expression denoting its language

The language accepted by finite automata are the languages denoted by regular expressions

For a regular expression r, there does not exist NFA with L(r) any transit that accept

The major difference between a moore and mealy machine is that

output of the former depends on the present state and present input

output of the former depends only on the present state

output of the former depends on the present state and present input

output of former depends only on the present input

The main difference between a DFSA and an NDFSA is

in NDFSA, ε transitions may be present

in DFSA, ε transition may be present

in NDFSA, from any given state, there can't be any alphabet leading to two diferent states

in DFSA, from any given state, there can't be any alphabet leading to two diferent states

The regular expression (a | b)* denotes the set of all strings

equal to regular expression (a* b*)*

with one or more instances of a or b

with zero or more instances of a or b

equal to regular expression (a* b*)*

151 + Mcqs in Theory of Computation in Computer Science Page 3 McqOptions

101.	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» C. None of the given

Discussion

102.	Consider a graph G = (V, E) where I V I is divisible by 3. The problem of finding a Hamiltonian cycle in a graph is denoted by SHAM3 and the problem of determining if a Hamiltonian cycle exits in such graph is denoted by DHAM3. The option, which holds true, is
A.	Only DHAM3 is NP-hard
B.	Only SHAM3 is NP-hard
C.	Both SHAM3 and DHAM3 are NP-hard
D.	Neither SHAM3 nor DHAM3 is NP-hard
Answer» D. Neither SHAM3 nor DHAM3 is NP-hard

Discussion

103.	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» D. PUSH or POP

Discussion

104.	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» C. L1 ∩ R

Discussion

105.	Two persons X and Y have been asked to show that a certain problem p is NP-complete. X shows a polynomial time reduction from the 3-SAT problem to p and Y shows a polynomial time reduction from p to 3-SAT. From these reduction it can be inferred that
A.	P is NP-complete
B.	P is NP-hard but not NP-complete
C.	P is in NP but not NP-complete
D.	P is neither NP-hard nor in NP
Answer» B. P is NP-hard but not NP-complete

Discussion

106.	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» B. Parser

Discussion

107.	State table of an FSM is given below. There are two states A And B, one input and one output. Let the initial state be A = 0 and B = 0. To take the machine to the state A = 0 and B = 1 with output = 1 the minimum length of input string required will be
A.	2
B.	7
C.	4
D.	3
Answer» E.

Discussion

108.	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» B. Always recognized by PDA

Discussion

109.	A random access machine (RAM) and truing machine are different in
A.	power
B.	accessing
C.	storage
D.	both accessing and storage are correct
Answer» E.

Discussion

110.	A language is represented by a regular expression (a)*(a + ba). Which of the following strings does not belong to the regular set represented by the above expression?
A.	aaa
B.	aba
C.	abab
D.	aa
Answer» D. aa

Discussion

111.	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» E.

Discussion

112.	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» C. Whether two given regular expressions are equivalent or not

Discussion

113.	If G is a simple connected 3-regular planar graph where every region is bounded by exactly 3 edges, then the edges of G is
A.	3
B.	4
C.	6
D.	5
Answer» D. 5

Discussion

114.	Any given transition graph has an equivalent:
A.	regular
B.	DFSM (Deterministic Finite State Machine)
C.	NDFSM
D.	All of them
Answer» E.

Discussion

115.	FSM can recognize
A.	Any grammar
B.	Only CG
C.	Both (a) and ( b )
D.	Only regular grammar
Answer» E.

Discussion

116.	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» B. CFL ⊂ REG ⊂ type0 ⊂ CSL

Discussion

117.	Which one of the following languages over the alphabet {0,1} is describedby the regular expression: (0+1)0(0+1)0(0+1)*?
A.	The set of all strings containing the substring 00.
B.	The set of all strings containing at most two 0’s.
C.	The set of all strings containing at least two 0’s.
D.	The set of all strings that begin and end with either 0 or 1.
Answer» D. The set of all strings that begin and end with either 0 or 1.

Discussion

118.	Which of the following regular expression identity is true?
A.	r() = r
B.	(rs)* = (r + s)*
C.	(r + s)* = r* + s*
D.	rs = r* + s*
Answer» C. (r + s)* = r* + s*

Discussion

119.	Languages are proved to be regular or non regular using pumping lemma.
A.	True
B.	False
C.	Not always true
D.	can’t say anything
Answer» B. False

Discussion

120.	If Turing machine accepts all the words of the languages L and rejects or loops for other words, which are not in L, then L is said to be
A.	recursive enumerable
B.	recursive
C.	context free language (cfl)
D.	none of them
Answer» B. recursive

Discussion

121.	If a Turing machine halts for each and every world of a language L and rejects other, then L is said to be
A.	recursive enumerable
B.	recursive
C.	context free language
D.	none of these
Answer» D. none of these

Discussion

122.	Consider the state table of a finite state machine that has input x and a single output z. The shortest input sequence to reach the final state C if the initial state is unknown is
A.	10
B.	01
C.	101
D.	110
Answer» B. 01

Discussion

123.	Let P be a regular language and Q be context-free language such that Q ∈ P. (For example, let P be the language represented by the regular expression pq and Q be {pnqnn∈ N}). Then which of the following is ALWAYS regular?
A.	P ∩ Q
B.	P – Q
C.	∑* – P
D.	∑* – Q
Answer» D. ∑* – Q

Discussion

124.	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» C. It is a regular language

Discussion

125.	A minimum state deterministic finite automation accepting the language L={W W ε {0,1}*, number of 0s and 1s in are divisible by 3 and 5, respectively} has
A.	15 states
B.	11 states
C.	10 states
D.	9 states
Answer» B. 11 states

Discussion

126.	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» D. None of the above

Discussion

127.	Consider the following language L = {anbncndnn ≥ 1} L is
A.	CFL but not regular
B.	CSL but not CFL
C.	Regular
D.	Type 0 language but not type 1
Answer» C. Regular

Discussion

128.	Context free grammar is not closed under
A.	Product operation
B.	Union
C.	Complementation
D.	kleene star
Answer» D. kleene star

Discussion

129.	Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph G =(V,E)with V divisible by 3 and DHAM3 be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?
A.	Both DHAM3 and SHAM3 are NP-hard
B.	SHAM3 is NP-hard, but DHAM3 is not
C.	DHAM3 is NP-hard, but SHAM3 is not
D.	Neither DHAM3 nor SHAM3 is NP-hard
Answer» B. SHAM3 is NP-hard, but DHAM3 is not

Discussion

130.	He difference between a read-only Turing machine and a two-way finite state machine is
A.	head movement
B.	finite control
C.	storage capacity
D.	power
Answer» D. power

Discussion

131.	Let S be an NP-complete problem, Q and R be two other problems not known to be in NP. Q is polynomial-time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true?
A.	R is NP-complete
B.	R is NP-hard
C.	Q is NP-complete
D.	Q is NP-hard
Answer» B. R is NP-hard

Discussion

132.	Which of the following strings is not generated by the following grammar? S → SaSbSε
A.	aabb
B.	abab
C.	aababb
D.	aaabb
Answer» E.

Discussion

133.	How many states are present in the minimum state finite automaton that recognizes the language represented by the regular expression (0+1)(0+1)…..N times?
A.	n+1
B.	n+2
C.	n
D.	2n
Answer» C. n

Discussion

134.	A universal Turing machine is a
A.	reprogrammable truing machine
B.	two-tape turing machine
C.	single tape turing machine
D.	none of them
Answer» B. two-tape turing machine

Discussion

135.	If PCP is decidable then MPCP is
A.	Decidable
B.	Undecidable
C.	Can’t Say
D.	None of the
Answer» D. None of the

Discussion

136.	The logic of pumping lemma is a good example of
A.	Pigeon-hole principle
B.	Divide-and-conquer technique
C.	Recursion
D.	Iteration
Answer» B. Divide-and-conquer technique

Discussion

137.	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» C. It has the capability to remember arbitrary long sequences of input symbols

Discussion

138.	If G is a connected planar graph of v vertices e edges and r regions then
A.	v-e+r=2
B.	e-v+r=2
C.	v+e-r=2
D.	None of above.
Answer» B. e-v+r=2

Discussion

139.	The minimum state automaton equivalent to the above FSA has the following number of states
A.	1
B.	2
C.	3
D.	4
Answer» C. 3

Discussion

140.	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» B. X is undecidable but partially decidable

Discussion

141.	The languages -------------- are the examples of non regular languages.
A.	PALINDROME and PRIME
B.	PALINDROME and EVEN-EVEN
C.	EVEN-EVEN and PRIME
D.	FACTORIAL and SQURE
Answer» B. PALINDROME and EVEN-EVEN

Discussion

142.	Consider the NFA M shown below. Let the language accepted by M be L. Let L1 be the language accepted by the NFA M1, obtained by changing the accepting state of M to a non-accepting state and by changing the non-accepting state of M to accepting states. Which of the following statements is true?
A.	L1 = {0,1}* − L
B.	L1 = {0,1}*
C.	L1 is a subset of L
D.	L1 = L
Answer» B. L1 = {0,1}*

Discussion

143.	The Family of recursive language is not closed under which of the followingoperations:
A.	Union
B.	Intersection
C.	Complementation
D.	None of the above.
Answer» E.

Discussion

144.	Given an arbitrary non-deterministic finite automaton NFA with N states, the maximum number of states in an equivalent minimized DFA is at least:
A.	N2
B.	2N
C.	2N
D.	N!
Answer» D. N!

Discussion

145.	The following grammarG = (N, T, P, S)N = {S, A, B, C, D, E}T = {a, b, c}P : S → aABAB → CDCD → CEC → aCC → bbE → 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» D. is type 0 but not type 1

Discussion

146.	Which of the following statements is wrong ?
A.	For every DFA there is a regular expression denoting its language
B.	The language accepted by finite automata are the languages denoted by regular expressions
C.	None of these
D.	For a regular expression r, there does not exist NFA with L(r) any transit that accept
Answer» E.

Discussion

147.	Regular expression a / b denotes the set
A.	{ ∈ , a, b }
B.	{a}
C.	{ ab }
D.	{a, b}
Answer» E.

Discussion

148.	The major difference between a moore and mealy machine is that
A.	output of the former depends only on the present state
B.	output of the former depends on the present state and present input
C.	all of these
D.	output of former depends only on the present input
Answer» B. output of the former depends on the present state and present input

Discussion

149.	The main difference between a DFSA and an NDFSA is
A.	in NDFSA, ε transitions may be present
B.	in DFSA, ε transition may be present
C.	in NDFSA, from any given state, there can't be any alphabet leading to two diferent states
D.	in DFSA, from any given state, there can't be any alphabet leading to two diferent states
Answer» E.

Discussion

150.	The regular expression (a \| b)* denotes the set of all strings
A.	with one or more instances of a or b
B.	with zero or more instances of a or b
C.	both ( and (
D.	equal to regular expression (a* b)
Answer» D. equal to regular expression (a* b)

Discussion

Explore topic-wise MCQs in Computer Science.

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 :

Consider a graph G = (V, E) where I V I is divisible by 3. The problem of finding a Hamiltonian cycle in a graph is denoted by SHAM3 and the problem of determining if a Hamiltonian cycle exits in such graph is denoted by DHAM3. The option, which holds true, is

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

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?

Two persons X and Y have been asked to show that a certain problem p is NP-complete. X shows a polynomial time reduction from the 3-SAT problem to p and Y shows a polynomial time reduction from p to 3-SAT. From these reduction it can be inferred that

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

State table of an FSM is given below. There are two states A And B, one input and one output. Let the initial state be A = 0 and B = 0. To take the machine to the state A = 0 and B = 1 with output = 1 the minimum length of input string required will be

Recursive languages are

A random access machine (RAM) and truing machine are different in

A language is represented by a regular expression (a)*(a + ba). Which of the following strings does not belong to the regular set represented by the above expression?

Which of the following problem is undecidable?

Pumping lemma is generally used for proving that

If G is a simple connected 3-regular planar graph where every region is bounded by exactly 3 edges, then the edges of G is

Any given transition graph has an equivalent:

FSM can recognize

Which of the following denotes Chomskianhiearchy?

Which one of the following languages over the alphabet {0,1} is describedby the regular expression: (0+1)*0(0+1)*0(0+1)*?

Which of the following regular expression identity is true?

Languages are proved to be regular or non regular using pumping lemma.

If Turing machine accepts all the words of the languages L and rejects or loops for other words, which are not in L, then L is said to be

If a Turing machine halts for each and every world of a language L and rejects other, then L is said to be

Consider the state table of a finite state machine that has input x and a single output z. The shortest input sequence to reach the final state C if the initial state is unknown is

Let P be a regular language and Q be context-free language such that Q ∈ P. (For example, let P be the language represented by the regular expression p*q* and Q be {pnqnn∈ N}). Then which of the following is ALWAYS regular?

Which one of the following is true regarding FOTRAN?

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

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:

Consider the following language L = {anbncndnn ≥ 1} L is

Context free grammar is not closed under

Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph G =(V,E)with V divisible by 3 and DHAM3 be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?

He difference between a read-only Turing machine and a two-way finite state machine is

Let S be an NP-complete problem, Q and R be two other problems not known to be in NP. Q is polynomial-time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true?

Which of the following strings is not generated by the following grammar? S → SaSbSε

How many states are present in the minimum state finite automaton that recognizes the language represented by the regular expression (0+1)(0+1)…..N times?

A universal Turing machine is a

If PCP is decidable then MPCP is

The logic of pumping lemma is a good example of

TM is more powerful than FSM because

If G is a connected planar graph of v vertices e edges and r regions then

The minimum state automaton equivalent to the above FSA has the following number of states

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?

The languages -------------- are the examples of non regular languages.

Consider the NFA M shown below. Let the language accepted by M be L. Let L1 be the language accepted by the NFA M1, obtained by changing the accepting state of M to a non-accepting state and by changing the non-accepting state of M to accepting states. Which of the following statements is true?

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

Given an arbitrary non-deterministic finite automaton NFA with N states, the maximum number of states in an equivalent minimized DFA is at least:

The following grammarG = (N, T, P, S)N = {S, A, B, C, D, E}T = {a, b, c}P : S → aABAB → CDCD → CEC → aCC → bbE → bc is

Which of the following statements is wrong ?

Regular expression a / b denotes the set

The major difference between a moore and mealy machine is that

The main difference between a DFSA and an NDFSA is

The regular expression (a | b)* denotes the set of all strings

Which one of the following languages over the alphabet {0,1} is describedby the regular expression: (0+1)0(0+1)0(0+1)*?

Let P be a regular language and Q be context-free language such that Q ∈ P. (For example, let P be the language represented by the regular expression pq and Q be {pnqnn∈ N}). Then which of the following is ALWAYS regular?