**Automata Theory MCQ (Multiple Choice Questions)**

**1. A language L from a grammar G = { VN, Σ, P, S} is?**

a. Set of symbols over VN**b. Set of symbols over Σ**c. Set of symbols over P

d. Set of symbols over S

**2. What is the transitional function of a DFA?****a. Q X Σ→Q**b. Q X Σ→2Q

c. Q X Σ→2n

d. Q X Σ→Qn

**3. What is the transitional function of an NFA?**

a. Q X Σ→Q**b. Q X Σ→2Q**c. Q X Σ→2n

d. Q X Σ→Qn

**4. Maximum number of states of a DFA converted from an NFA with nstates is?**

a. n

b. n^{2}**c. 2n**d. None of the mentioned

**5. What are the fundamental limitations of finite state machines?**a. It cannot remember arbitrarily large amounts of information

**b. In cannot remember state transitions**

c. In cannot remember Grammar for a language

d. It cannot remember Language generated from a grammar

**6. The String WWR is not recognized by any FSM because _____________**

a. An FSM cannot remember arbitrary amounts amount of information

b. An FSM cannot fix the midpoint

c. An FSM cannot match W with WR

d. An FSM cannot remember the first and last inputs

**7. A finite automata recognizes ____________**

a. Any Language

b. Context Sensitive Language

c. Context Free Language**d. Regular Language**

**8. Assume the R is a relation on a set A, aRb is partially ordered such that a and b are _____________**a. reflexive

b. transitive

c. symmetric

**d. reflexive and transitive**

9. The non-Kleene Star operation accepts the following String of finite length over set A = {0,1} | where string s contains an even number of 0 and 1

a. 01,0011,010101

9. The non-Kleene Star operation accepts the following String of finite length over set A = {0,1} | where string s contains an even number of 0 and 1

**b. 0011,11001100**

c. ε,0011,11001100

d. ε,0011,11001100

**10. A regular language over an alphabet ∑ cannot be obtained from the primary languages using the operation**a. Union

b. Concatenation

c. Kleene*

**d. All of the mentioned**

**11. Statement 1: A Finite automata can be represented graphically; Statement 2: The nodes can be their states; Statement 3: The edges or arcs can be used for transitions**

Hint: Nodes and Edges are for trees and forests, too.

Which of the following makes the correct combination?

a. Statement 1 is false, but Statements 2 and 3 are correct

b. Statements 1 and 2 are correct, while three is wrong

c. None of the mentioned statements are correct

**d. All of the mentioned**

**12. The minimum number of states required to recognize an octal number divisible by 3 are/is**a. 1

**b. 3**

c. 5

d. 7

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

a. Input alphabet

b. Transition function

c. Initial State

d. Output Alphabet

**14. If an Infinite language is passed to Machine M, the subsidiary which gives a finite solution to the infinite input tape is ______________**

a. Compiler

b. Interpreter

c. Loader and Linkers

d. None of the mentioned

**15. The number of elements in the Set for the Language L={xϵ(∑r) *|length if x is at most 2} and ∑={0,1} is _________**

a. 7

b. 6

c. 8

d. 5

**16. For the following state change in FA, which of the following codes is an incorrect option?**

a. δ (m, 1) = n

**b. δ (0, n) = m**

c. δ (m,0) = ε

d.

**17. Given: ∑= {a, b}L= {xϵ∑*|x is a string combination}∑4 represents which among the following?**a. {aa, ab, ba, bb}

**b. {aaaa, abab, ε, abaa, aabb}**

c. {aaa, aab, aba, bbb}

d. All of the mentioned

**18. Moore Machine is an application of:**a. Finite automata without input

**b. Finite automata with output**

c. Non Finite automata with output

d. None of the mentioned

**19. In Moore’s machine, the output is produced over the change of:**

a. transitions

**b. states**

c. all of the mentioned

d. none of the mentioned

**20. For a give Moore Machine, Given Input=’101010’, thus the output would be of length:**

a. |Input|+1

b. |Input|

a. |Input|+1

c. |Input-1|

d. Cannot be predicted

**21. Which of the following delays signal transmission along the wire by one step (clock pulse)?**

a. NAND box (NOT AND)

b. AND box

c. OR box

**d. DELAY box**

**22. For the given input, which of the following provides the Boolean OR for the given input-output?**

a. NAND box (NOT AND)

b. DELAY box

c. AND box

**d. OR box**

**23. For a given input, which of the following provides the complement of Boolean AND output?**

a. DELAY box

b. OR box

**c. NAND box (NOT AND)**

d. AND box

**24. If L1 and L2 are regular languages, then which of the following is/are also everyday Language (s)?**

a. L1 + L2

b. L1L2

c. L1

**d. All of the above**

**25. If L1 and L2 are regular languages, then these can be expressed by the corresponding FAs.**

**a. True**

b. False

**26. A Regular Expression for the Language of words containing an even number of a’s is?**

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

b. a+bbaabaa

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

**d. (b+aba)**

**27. The language regular expression can express session is called a common language.**

**a. True**

b. False

**28. Which of the following languages are examples of non-regular languages?**

a. PALINDROME and EVEN-EVEN

b. EVEN-EVEN and PRIME

**c. PALINDROME and PRIME**

d. FACTORIAL and SQURE

**29. Can languages be proven regular or unstable when using a pumping lemma?**

**a. True**

b. False

**30. Which of the following is the infinite Language?**

a. EQUAL-EQUAL

b. EVEN-EVEN

c. FACTORIAL

**d. PALINDROME**

**31. Select the nearest to the Myhill Nerode theorem.**

a. L partitions Σinto distinct classes.

b. If L is regular, L generates a finite number of classes.

c. If L generates a finite number of classes, then L is regular.

**d. All of the above**

**32. If we want to describe the complement of a language, then it is essential to describe the ——————- of that Language over which the Language is defined**.

a. Regular Expression

b. String

c. Word

**d. Alphabet**

**33. “CFG” stands for _________**

a. Context-Free Graph

**b. Context Free Grammar**

c. Context Finite Graph

d. Context Finite Grammar

**34. Which of the following states are called the halt states?**

a. ACCEPT AND START

b. ACCEPT and READ

**c. ACCEPT and REJECT**

d. ACCEPT AND WRITE

**35. The part of a PDA where the input string is placed before it is run is called?**

a. State

b. Transition

**c. Input Tape**

d. Output Tape

**36. In non-deterministic PDA, there is more than one outgoing edge from which of the following states?**

**a. READ or POP**

b. START or READ

c. POP or REJECT

d. PUSH or POP

**37. Which of these machines can accept lambda?**a. Moore

b. Mealy

c. NFA

d. None

**38. Which of these is the correct formula to calculate the memory required for a machine?**

a. 2n

b. 2 n+1

c. 2 n+1 -1

d. None

**39. If X and Y are strings of language L and XZϵL & YZ₲L, then it’s a———- language.**

a. Distinguishable

b. Un-Distinguishable

c. Both A&B

d. None

**40. Which of these is the right formula for De-Morgan’s law?**

a. (L1c U L2c)c = L1∩L2

a. (L1c U L2c)c = L1∩L2

b. (L1∩L2c)U(L1c∩L2) c

c. (L1∩L2c)c U (L1c∩L2)

d. None

**41. Machines in which the outputs are attached with transitions are known as.**

a. TG

b. FA

c. NFA

**d. OUTPUT machines**

**42. A language that has no regular expression is known as?.**

a. TG

b. FA

c. Both A&B

**d. None**

**43. ————- is an intermediate structure between FA and TG.**

a. GTG

**b. NFA**

c. Both A & B

d. None

**44. A machine in which the outputs are attached with states is known as.**

a**. Moore machine**

b. Mealy Machine

c. Both A&B

d. None**45. If a machine takes 010 as input and produces 101 as out, what will it be known as?**a. Increment

b. Moore

c. Mealy

d. Compliment

**46. ————– Have there been no final states for some?**

a. FA

b. TG

c. GTG

d. All

**47. If a string has no letters, it is not known as.**

a. ʎ

b. Empty String

c. Null String

d. None

**48. What is the written expression for the reverse of a string?**

a. rev(s)

b. reverse(s)

c. reverse IsI

d.None

**49. If a language contains all strings of length three, which expression will represent it?**

a. (a+b)(a+b)2

b. (a+b)*

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

d. None

**50. this expression (a+b)*will not define which of the following strings.**a. bbba

b. aaa

c. bbb

d. None

**51. ———– Can have multiple start states?**

a. GTG

b. TG

c. FA

**d. Both a & b**

**52. What is it known as if we have multiple transitions against a single input letter**?

a. NFA

b. DFA

c. Both a & b

d. None**53. Concatenation of a finite number of letters from the alphabet is called a.**a. Alphabets

b. Language

c. Grammar

**d. None**

**54. If a production is applied in the leftmost nonterminal in the working String, then it is.**

a. Left Recursion

b. Polish Notation

c. CFG

d. Left derivation**55. If a CFG has the form nonterminal , one terminal, or two , it is known as nonterminal.**a. CFG

b. CFL

**c. CNF**

d. None

**56. If a CFG has the form nonterminal one terminal.****a. Unit Production**

b. ʎ-production

c. Null able

d. Null**57. A production of the form. Nonterminal ʎ**

a. Unit Production**b. ʎ-production**

c. Null able

d. Null production

**58. Which is the right combination for Polish Notation?**a. Operator-Operand-Operand

b. Operand-Operator-Operand

c. Operand-Operand-Operator

d. None

**59. It will be known if we can draw more than one tree for Grammar.**

a. Ambiguous

a. Ambiguous

b. Context free

c. Both A & B

d. None

**60. The Maze game is an example of this.**a. TG

b. FA

**c. NFA**

d. None

**61. Terminals, nonterminal, and production are the terminology of**a. CFL

b. Chomsky

c. PDA

d. None

**62. If L is regular, then L generates a finite no of classes of the rule.**

a. Myhill Nerode Theorem

a. Myhill Nerode Theorem

b. Pumping Lemma

c. Both A&B

d. None

**63. If two machines create the same output, they will be known as.**a. Decrement

b. Moore

c. Mealy

**d. Equivalent**