GkSeries.com

Theory of Computation Quiz | Theory of Computation Objective Type Questions and Answers

Download PDF

Free download in PDF Theory of Computation Objective Type 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
(21) If two finite state machines are equivalent they should have the same number of
[A] States
[B] Edges
[C] States and edges
[D] None of these
Answer: None of these
(22) Given L1=L(a*baa*) and L2=L(ab*). The regular expression corresponding to language L3 = L1/L2 (right quotient) is given by
[A] a*b
[B] a*baa*
[C] a*ba*
[D] None of the above
Answer: None of the above

DOWNLOAD CURRENT AFFAIRS PDF FROM APP

(23) Finite state machine___________recognize palindromes.
[A] Can
[B] Cannot
[C] May
[D] May not
Answer: Cannot
(24) 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: 2 only
(25) Which of the following is most powerful?
[A] DFA
[B] NDFA
[C] 2PDA
[D] DPDA
Answer: 2PDA
(26) Given a Non-deterministic Finite Automation (NFA) with states p and r as initial and final states respectively and transition table as given below : The minimum number of states required in Deterministic Finite Automation (DFA) equivalent to NFA is
[A] 5
[B] 4
[C] 3
[D] 2
Answer: 3
(27) Context free languages are not closed under
[A] Union
[B] Concatenation
[C] Closure
[D] Iteration
Answer: Iteration
(28) An FSM can be used to add two given integers.This remark is
[A] True
[B] False
[C] May be true
[D] None of the above
Answer: False
(29) The following CFG S®aB|bA, A®a|as|bAA, B®b|bs|aBB generates strings of terminals that have
[A] Odd number of a’s and odd number of b’s
[B] Even number of a’s and even number of b’s
[C] Equal number of a’s and b’s
[D] Not equal number of a’s and b’s
Answer: Equal number of a’s and b’s
(30) The language accepted by finite automata is
[A] Context free
[B] Regular
[C] Non regular
[D] None of these
Answer: Regular
31 Which of the following permanent database that has an entry for each terminal symbol ?
[A] Literal table
[B] Identifier table
[C] Terminal table
[D] Source table
Answer: Terminal table
32 A PDM behaves like a TM when the number of auxiliary memory it has is
[A] Zero
[B] One or more
[C] Two or more
[D] None of these
Answer: Two or more
33 Two finite states are equivalent if they
[A] Have same number of states
[B] Have same number of edges
[C] Have same number of states and edges
[D] Recognize same set of tokens
Answer: Have same number of states and edges
34 Finite automata are used for pattern matching in text editors for
[A] Compiler lexical analysis
[B] Programming in localized application
[C] Both A and B
[D] None of the above
Answer: Compiler lexical analysis
35 A formal grammar is a___________for rewriting strings.
[A] Set of rules
[B] Set of functions
[C] Both A and B
[D] None of the above
Answer: Set of rules
36 Which is not the correct statement(s) ?

(i) Every context sensitive language is recursive.

(ii) There is a recursive language that is not context sensitive.

[A] is true, (ii) is false.
[B] is true and (ii) is true.
[C] is false, (ii) is false.
[D] is false and (ii) is true.
Answer: is true and (ii) is true.
37 Given the language L = {ab, aa, baa}, which of the following strings are in L*?

1) abaabaaabaa

2) aaaabaaaa

3) baaaaabaaaab

4) baaaaabaa

[A] 1, 2 and 3
[B] 2, 3 and 4
[C] 1, 2 and 4
[D] 1, 3 and 4
Answer: 1, 2 and 4
38 Which one of the following statement is false ?
[A] Context-free languages are closed under union
[B] Context-free languages are closed under concatenation
[C] Context-free languages are closed under intersection
[D] Context-free languages are closed under Kleene closure
Answer: Context-free languages are closed under Kleene closure
39 How many states can a process be in ?
[A] 2
[B] 3
[C] 4
[D] 5
Answer: 5
40 The basic limitation of a FSM is that
[A] It cannot remember arbitrary large amount of information
[B] It sometimes recognizes grammar that are not regular
[C] It sometimes fails to recognize grammars that are regular
[D] All of the above
Answer: It cannot remember arbitrary large amount of information

Please share this page

Click Here to Read more questions

Teacher Eligibility Test