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?

a. TRUE

b. 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

b. DFA>NFA

c. DFA<NFA

d. Can’t be said

Correct Answer: __a__

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

a. ACCEPT

b. DISTINCT

c. START

d. REJECT

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__