Theory of Automata Paper -1

1. 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 alphabets

Correct Answer: b

2. A language for which no DFA exist is a _________

a. Non-Regular Language

b. Regular Language

c. Maybe Regular

d. Cannot be said

Correct Answer: a

3. When are 2 finite states equivalent?

a. Same number of states as well as transitions

b. Same number of transitions

c. same number of states

d. Both are final states

Correct Answer: a

4. We can represent one language in more one FSMs, true or false?



c. Maybe true

d. Can’t be said

Correct Answer: a

5. Which of the following is not an example of finite state machine system?

a. Control Mechanism of an elevator

b. Combinational Locks

c. Traffic Lights

d. Digital Watches

Correct Answer: d

6. Can a DFA recognize a palindrome number ?

a. No

b. Yes

c. Yes, but with input alphabet as  ∑*

d. Can’t be determined

Correct Answer: a

7. How many languages are over the alphabet R?

a. countably infinite

b. countably finite

c. uncountable finite

d. uncountable finite

Correct Answer: d

8. There are _______ tuples in finite state machine.

a. 4

b. 6

c. unlimited

d. 5

Correct Answer: d

9. The sum of minimum & maximum number of final states for a DFA n state is equal to:

a. n-1

b. n+2

c. n+1

d. n

Correct Answer: c

10. δˆ tells us the best:

a. Kleene operation is performed on the set

b. how the DFA S behaves on a word u

c. the state is the dumping state

d. the final state has been reached

Correct Answer: b

11. Language of finite automata is .

a. Type 2

b. Type 0

c. Type 1

d. Type 3

Correct Answer: d

12. The maximum  transition which can be performed over a state in a DFA? ∑= {a, b, c}

a. 3

b. 4

c. 2

d. 1

Correct Answer: a

13. Finite automata requires minimum _______ number of stacks.

a. 0

b. 1

c. 2

d. None of the mentioned

Correct Answer: a

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

a. The choice of path is non-deterministic

b. The result is undetermined

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

d. All of the mentioned

Correct Answer: a

15. What is the relation between DFA and NFA on the basis of computational power?

a. Equal



d. Can’t be said

Correct Answer: a

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





Correct Answer: d

17. When two or more strings combine to form a new string is called:

a. Reverse string

b. Length of string

c. Regular expression

d. Concatenation

Correct Answer: d

18. Empty transition is possible in NFA.

a. True

b. False

c. Maybe true

d. Can’t be determined

Correct Answer: a

19. If by reversing a string it remains same then its called:

a. Concatenation

b. Reverse of strings

c. Regular expression

d. Palindrome

Correct Answer: d

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

a. L={ab}*

b. Factorial

c. Palindrome

d. Reverse

Correct Answer: b

21. The number of tuples in an extended Non Deterministic Finite Automaton:

a. 5

b. 6

c. 7

d. 4

Correct Answer: a

22. A ___________ is a substitution such that h(a) contains a string for each a.

a. Inverse Homomorphisam

b. Homomorphisam

c. Closure

d. Interchange

Correct Answer: b

23. Subset Construction method refers to:

a. Eliminating Null referemces

b. NFA minimization

c. Conversion of NFA to DFA

d. DFA minimization

Correct Answer: c

24. L is a regular Language if and only If the set of __________ classes of IL is finite.

a. Myhill

b. Nerode

c. Equivalence

d. Reflexive

Correct Answer: c

25. Concatenation Operation refers to which of the following set operations:

a. Intersaction

b. Dot

c. Union

d. Kleeene

Correct Answer: b

26. Regular sets are closed under union,concatenation and kleene closure.

a. Depends on non-regular set

b. True

c. False

d. Depends on regular set

Correct Answer: b

27. Complement of a DFA can be obtained by

a. no trival method

b. make final as a starting state

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

d. making starting state as final state.

Correct Answer: c

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

a. Recursive

b. Non-Regular

c. Non-Recursive

d. Regular

Correct Answer: d

29. The entity which generate Language is termed as:

a. Data

b. Grammer

c. Automata

d. Tokens

Correct Answer: b

30. The scanner outputs:

a. Intermediate code

b. Machine code

c. Stream of tokens

d. Image file

Correct Answer: c

31. Reverse of a DFA can be formed by

a. making final as starting state and starting state as final state

b. making final state as non-final

c. using PDA

d. None of the mentioned

Correct Answer: a

32. Which of the technique can be used to prove thata language is non regular?

a. Pumping Lemma

b. Ardens theorem

c. Ogden’s Lemma

d. None of the mentioned

Correct Answer: a

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

a. Decidable

b. Regular

c. Empty set

d. CFG

Correct Answer: b

34. The finite automata accept the following languages:

a. Context Sensitive Languages

b. Non Regular Langugages

c. Regular Languages

d. Context Free Languages

Correct Answer: c

35. The phase of compilation which involves type checking is:

a. Parsing

b. Semantic Analyzer

c. Scanning

d. Syntax directed translation

Correct Answer: d

36. Complement of (a + b)* will be

a. phi

b. null

c. a

d. b

Correct Answer: a

37. A language is regular if and only if

a. accepted by DFA

b. accepted by PDA

c. accepted by LBA

d. accepted by Turing machine

Correct Answer: a

38. Homomorphism of a regular set is _______

a. Universal set

b. Non regular set

c. Regular set

d. Null set

Correct Answer: c

39. If L is DFA-regular, L’ is

a. DFA-regular

b. Non-finite

c. Non regular

d. None

Correct Answer: a

40. Arden’s theorem is true for:

a. Null transitions

b. More than one initial states

c. One initial state

d. Non-null transitions

Correct Answer: d

41. Which kind of proof is used to prove the regularit of a language?

a. Proof by contradiction

b. Direct proof

c. Proof by induction

d. All

Correct Answer: a

42. Which of the following is not a notion of Context free grammars?

a. Recursive Inference

b. Derivations

c. Sentential form

d. All

Correct Answer: d

43. The language of balanced paranthesis is

a. None of the mentioned

b. may be regular

c. non regular

d. regular

Correct Answer: c

44. Which of the given are correct?

a. Moore machine has 6-touples

b. Mealy machine has 5-touples

c. Both Mealy and Moore has 6-touples

d. None of the mentioned

Correct Answer: a

45. A push down automaton employs ________ data structure.

a. Queue

b. Linked List

c. Stack

d. Hash Table

Correct Answer: c

46. In mealy machine, the O/P depends upon?

a. State

b. Previous State

c. Only Input

d. State and Input

Correct Answer: d

47. Which of the following can be used to prove a language is not context free?

a. Ardens theorem

b. Power Construction method

c. Pumping Lemma

d. Regular Closure

Correct Answer: d

48. Which of the following is an utility of state elimination phenomenon?

a. DFA to Regular Expression

b. DFA to NFA

c. NFA to DFA

d. All

Correct Answer: a

49. In which order are the children of any node ordered?

a. From the left

b. From the left

c. Arbitrarily

d. None

Correct Answer: a

50. Regular expression are

a. Type 1 language

b. Type 2 language

c. Type 3 language

d. Type 0 language

Correct Answer: d