Automata Theory MCQs

This comprehensive set of Automata Theory MCQs is designed to cover all essential topics required for success in exams related to theoretical computer science and formal languages. Focused on key subjects such as finite automata, regular expressions, context-free grammars, Turing machines, and computational complexity, these MCQs are crafted to help students build a strong foundation in automata theory concepts and formal language theory.

Who should practice Automata Theory MCQs?

Students preparing for courses in computer science, mathematics, or IT that cover automata theory, formal languages, and computation.
Individuals aiming to strengthen their understanding of deterministic and non-deterministic automata, regular languages, and pushdown automata.
Candidates preparing for competitive exams or certifications that assess knowledge of theoretical computer science and automata theory.
Learners interested in mastering topics such as Chomsky hierarchy, decidability, and computational models like Turing machines.
Professionals focused on improving their skills in algorithm design, complexity analysis, and understanding the limits of computation.
Suitable for all aspirants seeking to enhance their knowledge and performance in automata theory for academic or professional success.

1. Which of the following is a type of finite automaton?

A) Pushdown Automaton
B) Deterministic Finite Automaton
C) Linear-bounded Automaton
D) Turing Machine

View Answer

2. In automata theory, which language is accepted by a finite automaton?

A) Context-free language
B) Context-sensitive language
C) Regular language
D) Type-1 language

View Answer

3. A language that can be expressed using a regular expression is called a?

A) Context-free language
B) Regular language
C) Context-sensitive language
D) Type-0 language

View Answer

4. What is the term used for a machine that reads input and produces an output based on its state and input symbol?

A) Turing Machine
B) Finite Automaton
C) Pushdown Automaton
D) Mealy Machine

View Answer

5. Which of the following is true for a non-deterministic finite automaton (NFA)?

A) It cannot have multiple transitions for a single input.
B) It can have multiple transitions for the same input symbol.
C) It only accepts regular languages.
D) It cannot be converted to a DFA.

View Answer

6. What is the language accepted by a Turing machine called?

A) Regular language
B) Context-free language
C) Recursively enumerable language
D) None of the above

View Answer

7. Which of the following automaton types is most powerful?

A) DFA
B) NFA
C) PDA
D) Turing Machine

View Answer

8. Which automaton uses a stack for memory?

A) DFA
B) PDA
C) Turing Machine
D) Mealy Machine

View Answer

9. A DFA can simulate which of the following?

A) NFA
B) PDA
C) Context-free grammar
D) Turing Machine

View Answer

10. What is the class of languages that can be accepted by a Pushdown Automaton?

A) Regular languages
B) Context-free languages
C) Context-sensitive languages
D) Recursively enumerable languages

View Answer

11. Which type of grammar generates regular languages?

A) Type-0 grammar
B) Type-1 grammar
C) Type-2 grammar
D) Type-3 grammar

View Answer

12. Which of the following is not true for a DFA?

A) It can have multiple final states.
B) It has a unique next state for every input symbol.
C) It cannot have ε-transitions.
D) It can accept context-free languages.

View Answer

13. Which of the following can accept a context-free language?

A) DFA
B) NFA
C) PDA
D) Turing Machine

View Answer

14. What is the relationship between DFAs and NFAs?

A) NFA is more powerful than DFA.
B) DFA is more powerful than NFA.
C) DFA and NFA are equivalent in terms of languages accepted.
D) DFA cannot simulate NFA.

View Answer

15. The minimum number of states in a DFA that recognizes the regular expression (a+b)a is?

A) 2
B) 3
C) 4
D) 5

View Answer

16. A finite automaton with an additional tape that can be used for writing as well as reading is called?

A) DFA
B) NFA
C) PDA
D) Turing Machine

View Answer

17. In a PDA, what is the role of the stack?

A) It stores the input symbols.
B) It tracks states.
C) It manages context-free grammar.
D) It determines transitions.

View Answer

18. What is the time complexity of simulating an NFA by a DFA?

A) Exponential
B) Linear
C) Polynomial
D) Constant

View Answer

19. Which of the following can a Turing Machine not do?

A) Accept recursively enumerable languages
B) Solve the halting problem
C) Simulate any automaton
D) Perform computations on infinite tapes

View Answer

20. What is the name of the problem that determines whether a Turing machine will halt on a given input?

A) Word problem
B) Halting problem
C) Membership problem
D) Decision problem

View Answer

21. In a DFA, the number of transitions possible from each state is determined by?

A) The input alphabet
B) The number of final states
C) The number of states
D) The stack size

View Answer

22. Which of the following statements is correct about context-free languages?

A) They are accepted by finite automata.
B) They require a Turing machine for acceptance.
C) They are accepted by pushdown automata.
D) They are equivalent to regular languages.

View Answer

23. Which one of the following is not a context-free language?

A) {a^n b^n | n ≥ 0}
B) {a^n b^n c^n | n ≥ 0}
C) {a^m b^n | m ≠ n}
D) {a^p b^p | p is prime}

View Answer

24. Which type of automaton is used to parse context-free grammars?

A) Turing Machine
B) DFA
C) PDA
D) Linear-bounded Automaton

View Answer

25. Which of the following automaton can recognize context-sensitive languages?

A) DFA
B) NFA
C) Turing Machine
D) Linear-bounded Automaton

View Answer

26. What does an ε-transition represent in an NFA?

A) A transition with no input symbol
B) A transition that reads one symbol
C) A transition that reads multiple symbols
D) A transition that changes the stack

View Answer

27. Which of the following is the correct representation of a Turing Machine?

A) Q, Σ, δ, q₀, F
B) Q, Σ, Γ, δ, q₀, B, F
C) Q, δ, q₀, F
D) Σ, Γ, δ, q₀

View Answer

28. Which language is not accepted by any finite automaton?

A) {a, b}*
B) {a^n b^n | n ≥ 0}
C) {ε}
D) {a^n b^n c^n | n ≥ 0}

View Answer

29. What is the difference between Mealy and Moore machines?

A) Moore machine’s output depends only on the current state, while Mealy’s depends on both the state and input.
B) Mealy machine’s output depends only on the current state, while Moore’s depends on both the state and input.
C) Both depend on the input only.
D) Both are the same in terms of output behavior.

View Answer

30. Which of the following is the set of all strings that can be generated by a regular expression?

A) Context-free grammar
B) Context-sensitive language
C) Regular language
D) Type-0 language

View Answer

31. Which of the following languages is not regular?

A) {a^n | n ≥ 0}
B) {a^n b^n | n ≥ 0}
C) {a, b}*
D) {ε}

View Answer

32. Which of the following automaton has a finite tape with no read/write head movement?

A) Finite Automaton
B) Pushdown Automaton
C) Turing Machine
D) Mealy Machine

View Answer

33. What kind of machine is used to model real-world computations and can simulate any other computational model?

A) DFA
B) NFA
C) PDA
D) Turing Machine

View Answer

34. Which of the following is a property of regular languages?

A) They can be described by a context-free grammar.
B) They can be recognized by finite automata.
C) They require a stack to be parsed.
D) They cannot be recognized by deterministic machines.

View Answer

35. What is the distinguishing feature of a Deterministic Finite Automaton (DFA)?

A) It can accept context-free languages.
B) It has multiple possible next states for each input.
C) It has exactly one transition for each symbol in the input alphabet from each state.
D) It can have ε-transitions.

View Answer

36. In a non-deterministic finite automaton, which of the following is allowed?

A) Multiple transitions for the same input symbol from a single state
B) Exactly one transition for each input symbol
C) No transition on any input symbol
D) ε-transitions and deterministic transitions

View Answer

37. What is the closure property of regular languages under union?

A) Regular languages are not closed under union.
B) Regular languages are closed under union.
C) Union of two regular languages may not be regular.
D) Closure under union applies only to context-free languages.

View Answer

38. Which of the following is true for context-sensitive languages?

A) They are accepted by finite automata.
B) They are accepted by Turing machines with linear space constraints.
C) They require a PDA to be accepted.
D) They are equivalent to regular languages.

View Answer

39. What is a distinguishing characteristic of a Turing machine over a finite automaton?

A) It has finite memory.
B) It has infinite tape and can read and write on it.
C) It only accepts regular languages.
D) It uses a stack for memory.

View Answer

40. What is the term for a language that can be accepted by a Turing machine but not necessarily halt on all inputs?

A) Regular language
B) Context-free language
C) Context-sensitive language
D) Recursively enumerable language

View Answer

41. Which of the following describes a right-linear grammar?

A) It generates regular languages.
B) It generates context-free languages.
C) It generates context-sensitive languages.
D) It generates recursively enumerable languages.

View Answer

42. Which of the following is true about the pumping lemma for regular languages?

A) It provides a method to prove that a language is regular.
B) It provides a method to prove that a language is not regular.
C) It applies only to context-free languages.
D) It applies to all types of languages.

View Answer

43. What is the purpose of the stack in a Pushdown Automaton (PDA)?

A) To store input symbols
B) To track states
C) To store grammar rules
D) To handle non-regular languages

View Answer

44. What is a key feature of the Mealy machine compared to the Moore machine?

A) Output is generated only on transitions.
B) Output depends on the current state only.
C) Output depends on both input and the state.
D) Output is constant for every input.

View Answer

45. Which of the following is true for deterministic context-free languages (DCFL)?

A) They are a superset of context-free languages.
B) They can be accepted by deterministic pushdown automata.
C) They cannot be accepted by any type of automaton.
D) They require a Turing machine for acceptance.

View Answer

46. Which type of machine can accept recursively enumerable languages?

A) DFA
B) NFA
C) PDA
D) Turing Machine

View Answer

47. Which of the following is an undecidable problem for a Turing machine?

A) Whether a given string belongs to a regular language
B) Whether a given string belongs to a context-free language
C) The halting problem
D) Whether a Turing machine accepts a regular language

View Answer

48. What does the term “decidable language” mean in the context of automata theory?

A) A language that can be accepted by a DFA
B) A language that can be recognized by a Turing machine that halts on all inputs
C) A language that can be generated by a context-free grammar
D) A language that cannot be recognized by any automaton

View Answer

49. Which of the following regular expressions represents the set of all strings over {a, b} containing at least one ‘a’?

A) (a+b)*
B) bab*
C) ba(b+a)
D) a(a+b)*

View Answer

50. Which of the following is not a characteristic of context-free languages?

A) They can be accepted by pushdown automata.
B) They can be generated by a context-free grammar.
C) They can be described by regular expressions.
D) They are a strict superset of regular languages.

View Answer

51. Which of the following does not hold for regular languages?

A) They are closed under union.
B) They are closed under intersection.
C) They are closed under complementation.
D) They require a stack for recognition.

View Answer

52. Which of the following is true for linear-bounded automata (LBA)?

A) They accept context-free languages.
B) They accept context-sensitive languages.
C) They have infinite tape.
D) They are equivalent to Turing machines.

View Answer

53. What does the pumping lemma for context-free languages state?

A) Every string in a context-free language can be divided into parts and “pumped.”
B) No string in a context-free language can be “pumped.”
C) Every context-free language is regular.
D) Regular languages and context-free languages have the same pumping properties.

View Answer

54. Which of the following languages is context-free but not regular?

A) {a^n b^n | n ≥ 0}
B) {a^n b^n c^n | n ≥ 0}
C) {a, b}*
D) {ε}

View Answer

55. What is the computational power of a non-deterministic Turing machine compared to a deterministic Turing machine?

A) Non-deterministic Turing machines are more powerful.
B) Deterministic Turing machines are more powerful.
C) Both have the same computational power.
D) Neither can simulate each other.

View Answer

56. Which of the following is true for the intersection of two context-free languages?

A) It is always context-free.
B) It is regular.
C) It may not be context-free.
D) It is context-sensitive.

View Answer

57. Which of the following languages cannot be accepted by a deterministic pushdown automaton?

A) {a^n b^n | n ≥ 0}
B) {a^n b^n c^n | n ≥ 0}
C) {a^m b^m | m ≠ n}
D) {ε}

View Answer

58. Which of the following automata models is used in lexical analysis?

A) DFA
B) NFA
C) PDA
D) Turing Machine

View Answer

59. Which of the following is used to simulate a non-deterministic pushdown automaton?

A) DFA
B) Turing Machine
C) Mealy Machine
D) NFA

View Answer

60. Which of the following regular expressions represents strings with an even number of a’s?

A) (aa)*
B) (a+b)*
C) (b+a)*
D) (aa+b)*

View Answer

61. Which of the following is true for a context-free grammar (CFG)?

A) It can generate regular languages.
B) It can generate context-sensitive languages.
C) It can generate context-free languages.
D) It can generate recursively enumerable languages.

View Answer

62. Which machine model is capable of recognizing context-sensitive languages?

A) DFA
B) NFA
C) Linear-bounded Automaton (LBA)
D) PDA

View Answer

63. Which of the following languages is regular?

A) {a^n b^n | n ≥ 0}
B) {a, b}*
C) {a^n b^n c^n | n ≥ 0}
D) {a^m b^n | m ≠ n}

View Answer

64. The language accepted by a PDA can be described by?

A) Regular grammar
B) Context-free grammar
C) Context-sensitive grammar
D) Type-0 grammar

View Answer

65. Which of the following languages can be recognized by a DFA?

A) Context-sensitive languages
B) Context-free languages
C) Regular languages
D) Recursively enumerable languages

View Answer

66. What is the time complexity of converting an NFA to a DFA in the worst case?

A) O(n)
B) O(n^2)
C) O(2^n)
D) O(log n)

View Answer

67. Which of the following is true for a Turing machine?

A) It cannot solve the halting problem.
B) It accepts only regular languages.
C) It has finite memory.
D) It is less powerful than a DFA.

View Answer

68. Which language is accepted by a deterministic pushdown automaton (DPDA)?

A) Context-free language
B) Regular language
C) Deterministic context-free language
D) Context-sensitive language

View Answer

69. What is the main difference between a PDA and a DFA?

A) PDA uses a stack, while DFA does not.
B) DFA can process context-free languages, PDA cannot.
C) PDA requires infinite memory, DFA requires finite memory.
D) PDA processes regular languages, DFA does not.

View Answer

70. Which of the following is the set of all languages that can be recognized by a linear-bounded automaton?

A) Regular languages
B) Context-free languages
C) Context-sensitive languages
D) Recursively enumerable languages

View Answer

71. In automata theory, what does ε represent?

A) The empty stack
B) The empty string
C) A regular expression
D) A transition with an input

View Answer

72. What is the language class recognized by a Turing machine that halts on all inputs?

A) Recursively enumerable languages
B) Regular languages
C) Recursive languages
D) Context-sensitive languages

View Answer

73. What is the language class recognized by an NFA with ε-transitions?

A) Regular languages
B) Context-free languages
C) Context-sensitive languages
D) Type-0 languages

View Answer

74. Which of the following operations is not closed in context-free languages?

A) Union
B) Intersection
C) Concatenation
D) Kleene star

View Answer

75. Which of the following describes a left-linear grammar?

A) It generates context-sensitive languages.
B) It generates regular languages.
C) It generates context-free languages.
D) It generates recursively enumerable languages.

View Answer

76. The language {a^n b^n c^n | n ≥ 0} is an example of which type of language?

A) Regular
B) Context-free
C) Context-sensitive
D) Recursively enumerable

View Answer

77. Which of the following statements is true for the union of two context-free languages?

A) It is always context-sensitive.
B) It is always context-free.
C) It is always recursively enumerable.
D) It may not be context-free.

View Answer

78. What does it mean if a language is not recursively enumerable?

A) It cannot be recognized by any automaton.
B) It cannot be recognized by a Turing machine.
C) It can only be recognized by a DFA.
D) It can be recognized by a PDA.

View Answer

79. What is the primary function of a Turing machine’s tape?

A) To store input symbols
B) To simulate finite automata
C) To act as a memory for computation
D) To track the states of a PDA

View Answer

80. Which of the following is undecidable for a Turing machine?

A) Whether the machine halts on a given input
B) Whether the machine accepts all inputs
C) Whether the machine accepts context-free languages
D) Whether the machine has a finite number of states

View Answer

81. What does it mean for a grammar to be ambiguous?

A) It can generate more than one parse tree for the same string.
B) It can generate only one parse tree for each string.
C) It cannot generate a parse tree.
D) It is equivalent to a regular grammar.

View Answer

82. Which of the following machines can recognize the language {a^n b^n c^n | n ≥ 0}?

A) DFA
B) NFA
C) PDA
D) Linear-bounded automaton

View Answer

83. Which of the following is true for context-sensitive languages?

A) They are a subset of recursively enumerable languages.
B) They can be accepted by a pushdown automaton.
C) They can be accepted by finite automata.
D) They are equivalent to regular languages.

View Answer

84. What is the function of a transition table in a finite automaton?

A) To define the set of input symbols
B) To specify state transitions for input symbols
C) To define the language recognized by the automaton
D) To specify final states

View Answer

85. What is a recursive language?

A) A language accepted by a Turing machine that halts on all inputs
B) A language accepted by a DFA
C) A language that can be generated by a regular grammar
D) A language that cannot be recognized by any automaton

View Answer

86. Which of the following operations is closed in the set of regular languages?

A) Intersection
B) Union
C) Complementation
D) All of the above

View Answer

87. What type of machine is required to recognize the language {a^n b^n c^n | n ≥ 0}?

A) DFA
B) NFA
C) PDA
D) Linear-bounded automaton

View Answer

88. What is the difference between a DFA and an NFA?

A) A DFA can have ε-transitions, whereas an NFA cannot.
B) A DFA has exactly one transition for each input symbol from each state, while an NFA can have multiple transitions.
C) A DFA is more powerful than an NFA.
D) A DFA accepts context-free languages, while an NFA accepts regular languages.

View Answer

89. Which of the following grammars generates context-sensitive languages?

A) Type-0 grammar
B) Type-1 grammar
C) Type-2 grammar
D) Type-3 grammar

View Answer

90. Which of the following is not a property of recursively enumerable languages?

A) They are accepted by Turing machines.
B) They are closed under union.
C) They are closed under complementation.
D) They include all decidable languages.

View Answer

91. What is the primary difference between a recursive and a recursively enumerable language?

A) Recursive languages are accepted by DFAs, while recursively enumerable languages are accepted by PDAs.
B) Recursive languages are accepted by Turing machines that halt on all inputs, while recursively enumerable languages may not halt.
C) Recursive languages are a subset of context-free languages, while recursively enumerable languages are not.
D) Recursive languages are closed under intersection, while recursively enumerable languages are not.

View Answer

92. Which of the following is an undecidable problem in automata theory?

A) Whether a DFA accepts a given string
B) Whether a context-free grammar is ambiguous
C) Whether a Turing machine halts on a given input
D) Whether a PDA accepts a given string

View Answer

93. Which of the following languages is not context-free?

A) {a^n b^n | n ≥ 0}
B) {a^n b^n c^n | n ≥ 0}
C) {a^m b^n | m ≠ n}
D) {ε}

View Answer

94. Which of the following regular expressions represents all strings over {a, b} with an odd number of a’s?

A) (aa)*
B) (a+ba)a
C) (ab*)*
D) (ab)*

View Answer

95. Which of the following is true for deterministic context-free languages (DCFL)?

A) They can be accepted by nondeterministic pushdown automata.
B) They can be accepted by deterministic pushdown automata.
C) They require a Turing machine for acceptance.
D) They are a superset of regular languages.

View Answer

96. Which of the following operations is not closed in the set of context-free languages?

A) Union
B) Concatenation
C) Intersection
D) Kleene star

View Answer

97. What is the main use of ε-transitions in a non-deterministic finite automaton (NFA)?

A) To allow the automaton to move between states without consuming input symbols
B) To allow multiple transitions for the same input symbol
C) To process context-sensitive languages
D) To remove ambiguities from the grammar

View Answer

98. Which of the following is not a regular expression?

A) (a+b)*
B) a^n b^n
C) ab
D) (ab)+

View Answer

99. Which of the following languages cannot be recognized by a deterministic finite automaton (DFA)?

A) {a^n b^n | n ≥ 0}
B) {a, b}*
C) {ab}
D) {ε}

View Answer

100. What does the term “decidable problem” mean in the context of Turing machines?

A) A problem that can be solved by a DFA
B) A problem that can be solved by a Turing machine that halts on all inputs
C) A problem that can be generated by a regular grammar
D) A problem that cannot be solved by any automaton

View Answer

101. Which of the following is a valid property of regular languages?

A) They are closed under union.
B) They are not closed under intersection.
C) They are not closed under concatenation.
D) They require a pushdown automaton to be recognized.

View Answer

102. Which of the following languages can be recognized by a finite automaton?

A) {a^n b^n c^n | n ≥ 0}
B) {a^m b^n | m = 2n}
C) {a, b}*
D) {a^n b^n | n ≥ 0}

View Answer

103. Which of the following is true for nondeterministic Turing machines (NDTM)?

A) They can solve more problems than deterministic Turing machines (DTM).
B) They are equivalent in computational power to DTMs.
C) They cannot recognize context-free languages.
D) They are less powerful than DFAs.

View Answer

104. What is the pumping lemma used for in regular languages?

A) To prove that a language is regular.
B) To prove that a language is not regular.
C) To prove that a language is context-free.
D) To prove that a language is context-sensitive.

View Answer

105. Which of the following can be recognized by a deterministic finite automaton (DFA)?

A) {a^n b^n | n ≥ 0}
B) {ab}
C) {a^n b^n c^n | n ≥ 0}
D) {a^m b^n | m ≠ n}

View Answer

106. What is the language of a Turing machine that halts on all inputs?

A) Regular languages
B) Context-free languages
C) Recursive languages
D) Context-sensitive languages

View Answer

107. Which of the following operations is not closed in the class of recursively enumerable languages?

A) Union
B) Intersection
C) Complementation
D) Concatenation

View Answer

108. What does a Turing machine with an infinite tape represent?

A) An automaton with finite memory
B) An automaton with infinite memory
C) A DFA with ε-transitions
D) A PDA with multiple stacks

View Answer

109. Which of the following is undecidable for context-free grammars?

A) Whether a string belongs to the language
B) Whether the grammar is ambiguous
C) Whether the language is regular
D) Whether the grammar generates an infinite language

View Answer

110. Which of the following is true for the intersection of two regular languages?

A) It is always regular.
B) It is always context-free.
C) It is always context-sensitive.
D) It is not necessarily regular.

View Answer

111. Which of the following best describes the Church-Turing thesis?

A) It claims that any problem solvable by an algorithm can be solved by a Turing machine.
B) It claims that regular languages are equivalent to context-free languages.
C) It claims that recursive languages are equivalent to recursively enumerable languages.
D) It claims that Turing machines are less powerful than finite automata.

View Answer

112. What is the main purpose of a stack in a pushdown automaton (PDA)?

A) To keep track of input symbols.
B) To process regular languages.
C) To store auxiliary information required for processing context-free languages.
D) To simulate DFA transitions.

View Answer

113. Which of the following is a limitation of finite automata?

A) They cannot recognize context-free languages.
B) They cannot process regular languages.
C) They require a stack to process regular languages.
D) They can recognize context-sensitive languages.

View Answer

114. What is the Halting Problem in the context of Turing machines?

A) Determining whether a DFA will accept an input string.
B) Determining whether a PDA will accept a context-free language.
C) Determining whether a Turing machine will halt on a given input.
D) Determining whether a Turing machine accepts a regular language.

View Answer

115. Which of the following machines can be used to recognize recursively enumerable languages?

A) DFA
B) NFA
C) Pushdown Automaton
D) Turing Machine

View Answer

116. What does it mean for a Turing machine to be “universal”?

A) It can simulate any other Turing machine.
B) It can recognize only context-free languages.
C) It can solve the Halting Problem.
D) It requires finite memory.

View Answer

117. What type of automaton is used to recognize the language {a^n b^n c^n | n ≥ 0}?

A) DFA
B) PDA
C) Linear-bounded automaton
D) Turing machine

View Answer

118. Which of the following problems is undecidable for a Turing machine?

A) Whether a Turing machine halts on a given input
B) Whether a DFA accepts a string
C) Whether a PDA accepts a context-free language
D) Whether a context-free grammar is ambiguous

View Answer

119. Which of the following is true for recursively enumerable languages?

A) They can be accepted by finite automata.
B) They can be accepted by pushdown automata.
C) They can be accepted by Turing machines.
D) They can be accepted by context-free grammars.

View Answer

120. Which of the following describes a deterministic Turing machine (DTM)?

A) A Turing machine with only one possible transition for each state and input symbol.
B) A Turing machine that can have multiple transitions for the same input symbol.
C) A Turing machine that uses two tapes.
D) A Turing machine that accepts context-free languages.

View Answer

121. Which of the following operations is closed in the set of regular languages?

A) Union
B) Intersection
C) Complementation
D) All of the above

View Answer

122. What is the main purpose of ε-transitions in an NFA?

A) To allow state transitions without consuming input symbols.
B) To process context-free languages.
C) To represent non-regular languages.
D) To provide multiple transitions for the same input.

View Answer

123. Which of the following best describes the Chomsky hierarchy?

A) A classification of languages based on their complexity.
B) A classification of automata based on their power.
C) A classification of grammars based on the type of languages they generate.
D) All of the above.

View Answer

124. What type of machine is required to recognize the language {a^n b^n c^n | n ≥ 0}?

A) DFA
B) NFA
C) PDA
D) Linear-bounded automaton

View Answer

125. Which of the following is not closed in the class of context-free languages?

A) Union
B) Concatenation
C) Intersection
D) Kleene star

View Answer

126. What is the main characteristic of a recursively enumerable language?

A) It can be recognized by a Turing machine that halts on all inputs.
B) It can be recognized by a finite automaton.
C) It can be recognized by a pushdown automaton.
D) It can be recognized by a Turing machine but may not halt on all inputs.

View Answer

127. Which of the following languages is not regular?

A) {a^n b^n | n ≥ 0}
B) {a, b}*
C) {ab}
D) {ε}

View Answer

128. What is the significance of the pumping lemma for context-free languages?

A) It is used to prove that a language is context-free.
B) It is used to prove that a language is not context-free.
C) It is used to prove that a language is regular.
D) It is used to prove that a language is context-sensitive.

View Answer

129. Which of the following is true for deterministic context-free languages?

A) They can be recognized by deterministic pushdown automata.
B) They can be recognized by nondeterministic Turing machines.
C) They are a superset of regular languages.
D) They require a Turing machine for recognition.

View Answer

130. What is the class of languages recognized by linear-bounded automata?

A) Regular languages
B) Context-free languages
C) Context-sensitive languages
D) Recursive languages

View Answer