GkSeries.com

Theory of Computation Quiz | Theory of Computation Short Questions and Answers

Download PDF

Free download in PDF Theory of Computation Short Questions and Answers for competitive exams. These short objective type questions with answers are very important for Board exams as well as competitive exams. These short solved questions or quizzes are provided by Gkseries.
Go To Download Page
41 All strings having equal number of a and b can be recognized by
[A] DFA
[B] NDFA
[C] PDA
[D] All of these
Answer: PDA
42 The language L={ak bk|k>=1} is
[A] Type -3 Grammar
[B] Type -2 Grammar
[C] Type -1 Grammar
[D] Type -0 Grammar
Answer: Type -2 Grammar

DOWNLOAD CURRENT AFFAIRS PDF FROM APP

43 Which of the following problems are decidable?

1) Does a given program ever produce an output?

2) If L is context-free language, then, is ~L also context-free?

3) If L is regular language, then, is ~L also regular?

4) If L is recursive language, then, is ~L also recursive?

[A] 1,2,3,4
[B] 1,2
[C] 2,3,4
[D] 3,4
Answer: Boyson Jensen
44 Following grammar

S-> bS

S -> b

S -> aA

A -> bA

[A] Type -3 grammar
[B] Type -2 grammar
[C] Type -1 grammar
[D] Type -0 grammar
Answer: Type -3 grammar
45 6 Files F1,F2,F3,F4,F5 and F6 have 100,200,50,80,120,150 records repectively. In what order should they be sorted so as to optimize activity? Assume each file is accessed with the same frequency.
[A] F3,F4,F1,F5,F6,F2
[B] F2,F6,F5,F1,F4,F3
[C] F1,F2,F3,F4,F5,F6
[D] Ordering is immaterial as all files are accessed with the same frequency
Answer: F3,F4,F1,F5,F6,F2
46 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 statements are true ?
[A] I only
[B] I and II
[C] I and III
[D] I and III
Answer: I and II
47 The language accepted by the nondeterministic pushdown automaton
[A] L(abb*a)
[B] {a} U L(abb*a)
[C] L(ab*a)
[D] {a} U L(ab*a)
Answer: L(ab*a)
48 A FSM can be used to add how many given integers?
[A] 1
[B] 3
[C] 4
[D] 5
Answer: 3
49 Which of the following is the most general phase structured grammar ?
[A] Regular
[B] Context-sensitive
[C] Context free
[D] None of the above
Answer: Context-sensitive
50 Assume statements S1 and S2 defined as :

S1 : L2-L1 is recursive enumerable where L1 and L2 are recursive and recursive enumerable respectively.

S2 : The set of all Turing machines is countable.

Which of the following is true ?
[A] S1 is correct and S2 is not correct.
[B] Both S1 and S2 are correct.
[C] Both S1 and S2 are not correct.
[D] S1 is not correct and S2 is correct.
Answer: Both S1 and S2 are not correct.
51 FSM can recognize
[A] Any grammar
[B] Only CFG
[C] Any unambiguous grammar
[D] Only regular grammar
Answer: Only regular grammar
52 The regular expression for the following DFA
[A] ab*(b + aa*b)*
[B] a*b(b + aa*b)*
[C] a*b(b* + aa*b)
[D] a*b(b * + aa*b)*
Answer: a*b(b * + aa*b)*
53 Given the following productions of a grammar :
[A] The language corresponding to the given grammar is a set of even number of a s.
[B] The language corresponding to the given grammar is a set of odd number of a s.
[C] The language corresponding to the given grammar is a set of even number of a’s followed by odd number of b s.
[D] The language corresponding to the given grammar is a set of odd number of a’s followed by even number of b s.
Answer: The language corresponding to the given grammar is a set of odd number of a s.
54 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: Languages recognizable by Turing machine
55 Context free language can be recognized by
[A] Finite State Automaton
[B] Linear bounded automaton
[C] Pushdown automaton
[D] Both B and C
Answer: Both B and C
56 If every string of a language can be determined whether it is legal or illegal in finite time the language is called
[A] Decidable
[B] Undecidable
[C] Interpretive
[D] Non deterministic
Answer: Decidable
57 The logic of pumping lemma is a good example of
[A] The pigeon hole principle
[B] Divide and conquer method
[C] Iteration
[D] Recursion
Answer: The pigeon hole principle
58 Push down machine represents
[A] Type 0 Grammar
[B] Type 1 grammar
[C] Type-2 grammar
[D] Type-3 grammar
Answer: Type-2 grammar
59 The behavior of a NFA can be stimulated by DFA
[A] always
[B] sometimes
[C] never
[D] depend on NFA
Answer: always
60 Which of the following is not primitive recursive but partially recursive?
[A] Carnot function
[B] Rieman function
[C] Bounded function
[D] Ackermann function
Answer: Ackermann function

Please share this page

Click Here to Read more questions

Teacher Eligibility Test