JOIN ADRE 2.0 Telegram Group

Theory of Computation Quiz | Theory of Computation Multiple Choice Questions and Answers

Questions
1 Which of the following conversion is not possible (algorithmically)?
A regular grammar to context-free grammar
B nondeterministic FSA to deterministic FSA
C nondeterministic PDA to deterministic PDA
D nondeterministic TM to deterministic TM

Answer: nondeterministic PDA to deterministic PDA
2 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 intersection
Advertisement
Article and Schedule Quiz Start Test!

DOWNLOAD CURRENT AFFAIRS PDF FROM APP

3 Which of the following regular expression identity is true?
A r(*) = r*
B (r*s*)* = (r + s)*
C (r + s)* = r* + s*
D r*s* = r* + s*

Answer: (r*s*)* = (r + s)*
4 R1 and R2 are regular sets. Which of the following is not true?
A R1 n R2 neet not be regular
B S* – R1 is regular
C R1 ? R2 is regular
D is regular

Answer: R1 n R2 neet not be regular
5 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 proper superset of CFL
6 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: membership problem for type 0 languages
7 Recursively enumerable languages are not closed under
A union
B homomorphism
C complementation
D concatenation

Answer: complementation
8 Which of the following statement is wrong?
A Any regular language can be generated by a context-free grammar
B Some non-regular languages cannot be generated by any CFG
C the intersection of a CFL and regular set is a CFL
D All non-regular languages can be generated by CFGs.

Answer: All non-regular languages can be generated by CFGs.
9 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: I and II
10 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: recursively enumerable
11 Which of the following strings is not generated by the following grammar? S ? SaSbS|e
A aabb
B abab
C aababb
D aaabb

Answer: aaabb
12 Consider the following right-linear grammar G = (N, T, P, S) N = {S}

P : S ? aS|aA T = {a, b}

A ? bA|b

Which of the following regular expression denotes L(G)?
A (a + b)*
B a(ab)*b
C aa*bb*
D a*b*

Answer: aa*bb*
13 Which of the following is not primitive recursive but partially recursive?
A McCarthy’s function
B Riemann function
C Ackermann’s function
D Bounded function

Answer: Ackermann’s function
14 A language is represented by a regular expression (a)*(a + ba). Which of the following string does not belong to the regular set represented by the above expression.
A aaa
B aba
C ababa
D aa

Answer: ababa
15 Which of the following regular expressions denotes a language comprising of all possible strings over S = {a, b} of length n where n is a multiple of 3.
A (a + b + aa + bb + aba + bba)*
B (aaa + bbb)*
C ((a + b)(a + b)(a + b))*
D (aaa + ab + a) + (bbb + bb + a)

Answer: ((a + b)(a + b)(a + b))*
16 A language L is accepted by a FSA iff it is
A CFL
B CSL
C recursive
D regular

Answer: regular
17 Which of the following denotes Chomskian hiearchy?
A REG ? CFL ? CSL ? type0
B CFL ? REG ? type0 ? CSL
C CSL ? type0 ? REG ? CFL
D CSL ? CFL ? REG ? type0

Answer: REG ? CFL ? CSL ? type0
18 Let S = {a, b, c, d, e}. The number of strings in S* of length 4 such that no symbol is used more than once in a string is
A 360
B 120
C 35
D 36

Answer: 120
19 Palindromes can’t be recognized by any FSA because
A FSA cannot remember arbitrarily large amount of information
B FSA cannot deterministically fix the midpoint
C Even if the mid point is known an FSA cannot find whether the second half of the string matches the first half
D all of the above

Answer: all of the above
20 The set of all strings over the alphabet S = {a, b} (including e) is denoted by
A (a + b)*
B (a + b)+
C a+b+
D a*b*

Answer: (a + b)*

ADRE 2.0 FULL LENGTH MOCK TEST

Take Mock Tests

Missiles Mock Test Start Test!
SSC MTS Mock Test Start Test
IBPS CLERK MOCK TEST Start Test
SSC MTS 2022 JULY 26 Shift 1 (ENGLISH) Start Test!
SSC GD Previous Year Paper 2021 Nov 17 Shift - I (Hindi) Start Test!
SSC CGL Tier - 1 PYP 2022 April 21 Shift- 1 (ENGLISH) Start Test!
MPSC PAPER I MOCK TEST 1 (ENGLISH) Start Test!
IB Security Assistant Mock test 1 (english) Start Test!
UP POLICE CONSTABLE MOCK TEST 1 Start Test!
DELHI POLICE CONSTABLE MOCK TEST 1 (HINDI) Start Test!
Advertisement