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]

⭐ Make GKSeries Your Preferred Source on Google

Add GKSeries as Preferred Source
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]
apsc complete general studies course