# 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

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

a. Non-Regular Language

b. Regular Language

c. Maybe Regular

d. Cannot be said

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

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

a. TRUE

b. FALSE

c. Maybe true

d. Can’t be said

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

6. Can a DFA recognize a palindrome number ?

a. No

b. Yes

c. Yes, but with input alphabet as  ∑*

d. Can’t be determined

7. How many languages are over the alphabet R?

a. countably infinite

b. countably finite

c. uncountable finite

d. uncountable finite

8. There are _______ tuples in finite state machine.

a. 4

b. 6

c. unlimited

d. 5

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

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

11. Language of finite automata is .

a. Type 2

b. Type 0

c. Type 1

d. Type 3

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

13. Finite automata requires minimum _______ number of stacks.

a. 0

b. 1

c. 2

d. None of the mentioned

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

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

a. Equal

b. DFA>NFA

c. DFA<NFA

d. Can’t be said

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

a. ACCEPT

b. DISTINCT

c. START

d. REJECT

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

18. Empty transition is possible in NFA.

a. True

b. False

c. Maybe true

d. Can’t be determined

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

a. Concatenation

b. Reverse of strings

c. Regular expression

d. Palindrome

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

a. L={ab}*

b. Factorial

c. Palindrome

d. Reverse

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

a. 5

b. 6

c. 7

d. 4

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

a. Inverse Homomorphisam

b. Homomorphisam

c. Closure

d. Interchange

23. Subset Construction method refers to:

a. Eliminating Null referemces

b. NFA minimization

c. Conversion of NFA to DFA

d. DFA minimization

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

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

a. Intersaction

b. Dot

c. Union

d. Kleeene

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

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.

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

29. The entity which generate Language is termed as:

a. Data

b. Grammer

c. Automata

d. Tokens

30. The scanner outputs:

a. Intermediate code

b. Machine code

c. Stream of tokens

d. Image file

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

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

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

34. The finite automata accept the following languages:

a. Context Sensitive Languages

b. Non Regular Langugages

c. Regular Languages

d. Context Free Languages

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

a. Parsing

b. Semantic Analyzer

c. Scanning

d. Syntax directed translation

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

a. phi

b. null

c. a

d. b

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

38. Homomorphism of a regular set is _______

a. Universal set

b. Non regular set

c. Regular set

d. Null set

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

a. DFA-regular

b. Non-finite

c. Non regular

d. None

40. Arden’s theorem is true for:

a. Null transitions

b. More than one initial states

c. One initial state

d. Non-null transitions

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

b. Direct proof

c. Proof by induction

d. All

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

a. Recursive Inference

b. Derivations

c. Sentential form

d. All

43. The language of balanced paranthesis is

a. None of the mentioned

b. may be regular

c. non regular

d. regular

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

45. A push down automaton employs ________ data structure.

a. Queue

c. Stack

d. Hash Table

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

a. State

b. Previous State

c. Only Input

d. State and Input

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

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

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

a. From the left

b. From the left

c. Arbitrarily

d. None