JOIN ADRE 2.0 Telegram Group

Automata Theory Objective Questions Answers | Page-2

Questions
11 Which of the following is not primitive recursive but partially recursive?
A Ricmann function
B Bounded function
C Carnot function
D Ackermann function

Answer: Option [D]
12 Regular expression a+b denotes the set
A {a}
B {Epsilon, a, b}
C {a, b}
D none of the above

Answer: Option [C]
Advertisement
Article and Schedule Quiz Start Test!

DOWNLOAD CURRENT AFFAIRS PDF FROM APP

13 Finite State Machine can recognize
A only ambiguous CFG
B any grammar
C any unambiguous grammar
D only regular grammar

Answer: Option [D]
14 Which of the following are not regular grammar?
A Strings of 0’s, whose length is a prime number.
B String of 0’s whose length is a perfect square.
C Both [A] and [B].
D Only [A]

Answer: Option [D]
15 Set of regular languages over a given alphabet ∑ is not closed under
A union
B concatenation
C Kleene star
D none of the above

Answer: Option [D]
16 The following CFG

     S → aB | bA

     A → b | aS | bAA

     B → b | bS | aBB

generates strings of terminals that have

A equal number of a’s and b’s
B odd number of a’s and odd number b’s
C even number of a’s and even number of b’s
D odd number a’s and even number of a’s

Answer: Option [A]

We have S → aB → aaBB → aabB → aabb

So (b) is wrong. We have

S → aB → ab

So (c) is wrong.

A careful observation of the productions will reveal a similarity. Change A to B, B to A, a to b and b to a. The new set of productions will be the same as the original set. So (d) is false and (a) is the correct answer.

17 Let L1 = {anbnam | m, n = 1, 2, 3 …………}
       L2 = {anbmam | m, n = 1, 2, 3 ……………}
       L3 = {anbnan | n = 1, 2, 3 ………}

Choose the correct statements.

A L3 = L1 ∩ L2
B L1 and L2 are CFL but L3 is not a CFL
C L1 and L2 are not CFL but L3 is a CFL
D (A) and (B)

Answer: Option [D]
18 CSG can be recognized by a
A FSM
B DPDM
C NDPDM
D linearly bounded memory machine

Answer: Option [D]
19 Which of the following is not primitive recursive but computable?
A Bounded function
B Ackermann function
C Carnot function
D Riemann function

Answer: Option [B]
20 Which of the following pairs of regular expression are not equivalent?
A (a+b)* and (a*+b)*
B (a*+b)* and (a+b)*
C (ab)*a and a(ba)*
D none of the above

Answer: Option [D]

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
Assam Direct Recruitment Test Series