Theory of Automata Paper -2

1. Σ = {a,b} Productions





This grammar defines the language expressed by___________

a. (a+b)aa(a+b)aa

b. (a+b)aba+b)

c. (a+b)aa(a+b)

d. (a+b)a(a+b)a

Correct Answer: c

2. “CFG” stands for _________

a. Context Finite Grammar

b. Context Free Grammar

c. Context Free Graph

d. Context Finite Graph

Correct Answer: b

3. ___________ states are called the halt states.





Correct Answer: a

4. _____________ is obviously infinite language.





Correct Answer: b

5. A binary string is divisible by 4 if and only if it ends with:

a. 1100

b. 11

c. 100

d. 1000

Correct Answer: c

6. A deterministic turing machine is:

a. unambiguous turing machine

b. Ambiguous turing machine

c. non-deterministic

d. None

Correct Answer: a

7. A PDA machine configuration (p, w, y) can be correctly represented as:

a. (current state, unprocessed input, stack content)

b. (unprocessed input, stack content, current state)

c. (current state, stack content, unprocessed input)

d. None

Correct Answer: a

8. A regular language over an alphabet ∑ is one that cannot be obtained from the basic languages using the operation

a. Kleene*

b. All of the mentioned

c. Union

d. Concatenation

Correct Answer: b

9. A->aAa|bAb|a|b|e

Which among the following is the correct option for the given production?

a. Left most derivation

b. Right most derivation

c. Recursive inference

d. None

Correct Answer: a

10. Complement of a DFA can be obtained by

a. making starting state as final state.

b. no trival method.

c. make final as a starting state.

d. making final states non-final and non-final to final.

Correct Answer: d

11. For a DFA accepting binary numbers whose decimal equivalent is divisible by 4, what are all the possible remainders?

a. 0,2

b. 0,2,4

c. 0,1,2,3

d. 0

Correct Answer: c

12. Given grammar G:

S-> A| B| C

A-> aAa| B

B-> bB|bb



Eliminate e and unit productions and state the number of variables left?

a. 3

b. 2

c. 5

d. 4

Correct Answer: c

13. If L is a regular language then, ——— is also a regular language.

a. Ls

b. Lm

c. Lx

d. L’

Correct Answer: d

14. If L1 and L2 are regular languages is/are also regular language(s).

a. L1 + L2

b. L1

c. L1L2

d. All of above

Correct Answer: d

15. If L1 and L2 are regular sets then intersection of these two will be

a. Regular

b. Non Regular

c. Recursive

d. Non Recursive

Correct Answer: a

16. If L1 and L2 are two regular languages, then L1 U L2 is not a regular.


b. True



Correct Answer: a

17. If L1 is regular L2 is unknown but L1-L2 is regular ,then L2 must be

a. Regular

b. Empty set

c. Decidable

d. CFG

Correct Answer: a

18. In NFA, this very state is like dead-end non final state:





Correct Answer: c

19. Kleene’s theorem states

Select correct option:

a. All representations of a context free language are equivalent.


c. All representations of a regular language are equivalent.

d. Finite Automata are less powerful than Pushdown Automata.

Correct Answer: d

20. Language of finite automata is.

a. Type 1

b. Type 2

c. Type 3

d. Type 0

Correct Answer: c

21. Languages of a automata is

a. If it is accepted by automata

b. If it halts

c. If automata touch final state in its life time

d. All language are language of automata

Correct Answer: a

22. Let ∑= {a, b, …. z} and A = {Hello, World}, B= {Input, Output}, then (A*∩B) U (B*∩A) can be represented as:

a. {Hello, World, ε}

b. {Hello, World, Input, Output, ε}

c. {}

d. {Input, Output, ε}

Correct Answer: c

23. Let FA3 be an FA corresponding to FA1+FA2, then the initial state of FA3 must correspond to the initial state of

Select correct option:

a. FA1 and FA2

b. FA1 or FA2

c. FA2 only

d. FA1 only

Correct Answer: b

24. Let G=(V, T, P, S) be a CFG such that _____________. Then there exists an equivalent grammar G’ having no e productions.

a. e ∈ L(G)

b. w ∉ L(G)

c. w ∈ L(G)

d. e ∉ L(G)

Correct Answer: d

25. Let h(0)=ab; h(1)=e

Let L={abab,baba}

h-1(L)= the language of two zeroes and any number of one’s.

The given example belongs to which of the following?

a. Inverse Homomorphism

b. Homomorphism

c. none


Correct Answer: a

26. Let L be a language defined over an alphabet Σ, then the language of strings, defined over Σ, not belonging to L,

is called Complement of the language L, denoted by Lc or L’.

a. True




Correct Answer: a

27. NFA, in its name has ’non-deterministic’ because of :

a. The choice of path is non-deterministic

b. The state to be transited next is non-deterministic

c. The result is undetermined

d. All of the mentioned

Correct Answer: a

28. Number of final state require to accept Φ in minimal finite automata.

a. 2

b. 3

c. None of the mentioned

d. 1

Correct Answer: c

29. Number of states require to accept string ends with 10.

a. can’t be represented.

b. 3

c. 2

d. 1

Correct Answer: b

30. Predict the number of transitions required to automate the following language using only 3 states:

L= {w | w ends with 00}

a. 4

b. 5

c. 3

d. 2

Correct Answer: c

31. The Grammar can be defined as: G=(V, ∑, p, S) In the given definition, what does S represents?

a. Starting Variable

b. Sensitive Grammar

c. Accepting State

d. None of these

Correct Answer: a

32. The grammatical rules are often called_____________

a. Productions

b. Terminals

c. Non-terminals

d. All of above

Correct Answer: a

33. The language of all words (made up of a’s and b’s) with at least two a’s can not be described by the regular expression.

a. a(a+b)a(a+b)(a+b)ab

b. (a+b)aba(a+b)

c. baba(a+b)


Correct Answer: d

34. The language that can be expressed by any regular expression is called a Non regular language.


b. True



Correct Answer: a

35. The maximum number of transition which can be performed over a state in a DFA?

∑= {a, b, c}

a. 2

b. 4

c. 3

d. 1

Correct Answer: c

36. The productions of the form nonterminal → one nonterminal, is called _________

a. Unit production

b. Null production

c. Null able production

d. None

Correct Answer: a

37. The symbols that can’t be replaced by anything are called —————–

a. Non-terminals

b. Productions

c. Terminals

d. All of above

Correct Answer: a

38. The symbols that must be replaced by other things are called __________

a. Terminals

b. Productions

c. Non-terminals

d. All of above

Correct Answer: a

39. The terminals are designated by ________ letters, while the non-terminals are designated by ________ letters.

a. Capital, bold

b. Capital, small

c. Small, bold

d. Small, capital

Correct Answer: d

40. The transition a Push down automaton makes is additionally dependent upon the:

a. Stack

b. Input tape

c. terminals

d. None

Correct Answer: a

41. There are ________ tuples in finite state machine.

a. 6

b. unlimited

c. 5

d. 4

Correct Answer: c

42. What is the output for the given language?

Language: A set of strings over ∑= {a, b} is taken as input and it prints 1 as an output “for every occurrence of a, b as its substring. (INPUT: abaaab)

a. 0111010

b. 0010000

c. 0010001

d. 0101010

Correct Answer: c

43. Which among the following is not notated as infinite language?

a. L={ab}*

b. Factorial

c. Palindrome

d. Reverse

Correct Answer: b

44. Which of the following can accept even palindrome over {a,b}


b. Push down Automata

c. Turing Machine

d. All

Correct Answer: a

45. Which of the following does not obey pumping lemma for context free languages ?

a. Unrestricted languages

b. Finite Languages

c. Context free languages

d. None

Correct Answer: a

46. Which of the following is a correct statement?

a. Mealy machine has accepting states

b. We can convert Mealy to Moore but not vice versa

c. All oh the mentioned

d. Moore machine has no accepting states

Correct Answer: d

47. Which of the following is a not a part of 5-tuple finite automata?

a. Initial State

b. Output Alphabet

c. Transition function

d. Input alphabet

Correct Answer: b

48. Which of the following is analogous to the following?


a. Regular language and Context Free language

b. Context free language and Context Sensitive language

c. Regular language and Context Sensitive language

d. None

Correct Answer: a

49. Which of the following regular expression allows strings on {a,b}* with length n where n is a multiple of 4.

a. ((a+b)(a+b)(a+b)(a+b))*

b. (bbbb+aaaa)*

c. (a+b+ab+ba+aa+bb+aba+bab+abab+baba)*

d. None

Correct Answer: a

50. Which of the following relates to Chomsky hierarchy?

a. Regular<CFL<CSL<Unrestricted

b. CFL<CSL<Unrestricted<Regular

c. CSL<Unrestricted<CF<Regular

d. None

Correct Answer: a