Automata Theory - Multiple Choice Questions and Answers | Automata Theory Questions and Answers | MCQs on Automata Theory | Automata Theory Quiz | Automata Theory Online Test | 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

View Answer Comment

12 Regular expression a+b denotes the set

A {a}

B {Epsilon, a, b}

C {a, b}

D none of the above

View Answer Comment

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

View Answer Comment

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]

View Answer Comment

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

View Answer Comment

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

View Answer Comment

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 = {aⁿbⁿa^m | m, n = 1, 2, 3 …………}
L2 = {aⁿb^ma^m | m, n = 1, 2, 3 ……………}
L3 = {aⁿbⁿaⁿ | 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)

View Answer Comment

18 CSG can be recognized by a

A FSM

B DPDM

C NDPDM

D linearly bounded memory machine

View Answer Comment

19 Which of the following is not primitive recursive but computable?

A Bounded function

B Ackermann function

C Carnot function

D Riemann function

View Answer Comment

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

View Answer Comment

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!