EduConceptHub

Start MCQs

Theory of Automata

Theory of Automata

Introduction

Study mathematical models of computation, formal languages and the limits of algorithmic machines.

Topic-Wise Overview

Regular Languages

Formal languages, regular expressions and finite automata

Nondeterminism

NFAs, transition graphs, transducers and Kleene’s theorem

Nonregular Languages

Pumping lemma and limitations of finite automata

Context-Free Languages

Grammars, derivation trees, parsing and pushdown automata

Computability

Chomsky hierarchy, Turing machines and universal computation

Study Guidance

Explore the complete collection of 200 Theory of Automata MCQs in four sets of 50. Each question includes four options, the correct answer and an explanation. Topics cover finite automata, regular expressions, pumping lemmas, context-free grammars, pushdown automata, Turing machines, decidability, computability and the Chomsky hierarchy.

Explore Other Subjects

Browse Computer Science subjects

Theory of Automata MCQs — Set 1 (Questions 1–50)

Read each question, choose an option, then reveal its explanation.

Question 1. What is an alphabet in formal language theory?

  1. A finite nonempty set of symbols
  2. An infinite sequence of words
  3. A state transition function
  4. Only English letters
Show correct answer and explanation

Correct answer: A. A finite nonempty set of symbols

An alphabet is a finite set of symbols used to form strings.

Question 2. What is a string over an alphabet?

  1. An unordered set of states
  2. A finite sequence of alphabet symbols
  3. An infinite sequence only
  4. A type of transition graph
Show correct answer and explanation

Correct answer: B. A finite sequence of alphabet symbols

Strings are ordered finite sequences of symbols.

Question 3. What does the empty string epsilon have?

  1. Length one
  2. Length two
  3. Length zero
  4. Undefined length
Show correct answer and explanation

Correct answer: C. Length zero

The empty string contains no symbols.

Question 4. What is the length of the string abba?

  1. 3
  2. 2
  3. 5
  4. 4
Show correct answer and explanation

Correct answer: D. 4

The string contains four symbols.

Question 5. What does Sigma-star denote?

  1. All finite strings over Sigma including epsilon
  2. Only strings of length one
  3. Only infinite strings
  4. Only strings without epsilon
Show correct answer and explanation

Correct answer: A. All finite strings over Sigma including epsilon

Kleene star on an alphabet includes every finite string.

Question 6. What does Sigma-plus denote?

  1. Only epsilon
  2. All nonempty finite strings over Sigma
  3. All strings including epsilon necessarily
  4. Only palindromes
Show correct answer and explanation

Correct answer: B. All nonempty finite strings over Sigma

Sigma-plus is Sigma-star excluding epsilon.

Question 7. What is a formal language over Sigma?

  1. A single transition function necessarily
  2. Only an alphabet
  3. A subset of Sigma-star
  4. A machine tape
Show correct answer and explanation

Correct answer: C. A subset of Sigma-star

A language is a set of finite strings.

Question 8. If Sigma has two symbols how many strings have length three?

  1. 6
  2. 3
  3. 9
  4. 8
Show correct answer and explanation

Correct answer: D. 8

Each of three positions has two choices giving 2 cubed.

Question 9. What is the reversal of string abcd?

  1. dcba
  2. abcd
  3. badc
  4. cdab
Show correct answer and explanation

Correct answer: A. dcba

Reversal lists the symbols in reverse order.

Question 10. What is concatenation of ab and ba?

  1. abab
  2. abba
  3. aabb
  4. bbaa
Show correct answer and explanation

Correct answer: B. abba

Concatenation appends the second string to the first.

Question 11. A deterministic finite automaton is commonly specified by how many components?

  1. Three
  2. Four
  3. Five
  4. Six
Show correct answer and explanation

Correct answer: C. Five

A DFA is a five-tuple of states alphabet transition start and accepting states.

Question 12. What does Q represent in a DFA five-tuple?

  1. Input alphabet
  2. Accepting state alone
  3. Transition symbol
  4. Finite set of states
Show correct answer and explanation

Correct answer: D. Finite set of states

Q is the set of machine states.

Question 13. What does Sigma represent in a DFA?

  1. Input alphabet
  2. Set of accepting states
  3. Start state
  4. Transition graph edges only
Show correct answer and explanation

Correct answer: A. Input alphabet

Sigma lists possible input symbols.

Question 14. What is the function type of the transition function of a DFA?

  1. Q to Sigma-star
  2. Q times Sigma to Q
  3. Sigma to natural numbers
  4. Q times Q to Sigma-star
Show correct answer and explanation

Correct answer: B. Q times Sigma to Q

A DFA selects exactly one next state per state-symbol pair.

Question 15. How many start states does a standard DFA have?

  1. Exactly two
  2. Any positive number
  3. Exactly one
  4. None
Show correct answer and explanation

Correct answer: C. Exactly one

A DFA has a single designated initial state.

Question 16. What does F represent in a DFA?

  1. Only unreachable states
  2. Input symbols
  3. Tape alphabet
  4. Set of accepting states
Show correct answer and explanation

Correct answer: D. Set of accepting states

The DFA accepts a string if its final state is in F.

Question 17. A DFA accepts a string when?

  1. Its run ends in an accepting state
  2. It visits any accepting state at some intermediate moment only
  3. It reads only one character
  4. It has an epsilon transition
Show correct answer and explanation

Correct answer: A. Its run ends in an accepting state

After the entire string is read the final state determines acceptance.

Question 18. Can a DFA have zero accepting states?

  1. No
  2. Yes
  3. Only with an empty alphabet
  4. Only with infinite states
Show correct answer and explanation

Correct answer: B. Yes

An empty accepting-state set recognizes the empty language.

Question 19. Can a DFA recognize the empty language?

  1. No
  2. Only using a stack
  3. Yes
  4. Only using infinite memory
Show correct answer and explanation

Correct answer: C. Yes

A DFA with no reachable accepting states accepts no strings.

Question 20. Can a DFA recognize every string over its alphabet?

  1. No
  2. Only if it uses epsilon moves
  3. Only using a Turing machine
  4. Yes
Show correct answer and explanation

Correct answer: D. Yes

A one-state accepting DFA with self-loops accepts Sigma-star.

Question 21. What is a dead or trap state in a DFA?

  1. A state from which no accepting state can be reached
  2. Always the start state
  3. Always an accepting state
  4. A state with no defined transitions in a complete DFA
Show correct answer and explanation

Correct answer: A. A state from which no accepting state can be reached

A trap state cannot lead to acceptance.

Question 22. What is an unreachable state?

  1. A state without outgoing transitions necessarily
  2. A state that cannot be reached from the start by any input string
  3. An accepting state
  4. A state with two incoming edges
Show correct answer and explanation

Correct answer: B. A state that cannot be reached from the start by any input string

Unreachable states play no role in processing starting from the initial state.

Question 23. What is a distinguishing string for two DFA states?

  1. A string accepted from both states
  2. A string with no symbols
  3. An input accepted from one state but not the other
  4. A string outside the alphabet
Show correct answer and explanation

Correct answer: C. An input accepted from one state but not the other

Distinguishing suffixes separate inequivalent states.

Question 24. What does DFA minimization seek?

  1. A DFA with the longest accepted string
  2. A machine with no accepting states
  3. A DFA with two start states
  4. An equivalent DFA with the fewest states
Show correct answer and explanation

Correct answer: D. An equivalent DFA with the fewest states

Minimization merges behaviorally equivalent states.

Question 25. Which two DFA states can be merged during minimization?

  1. States with identical acceptance behavior for every future input
  2. Any states with different acceptance behavior
  3. Every pair of accepting and rejecting states
  4. Only states with the same name
Show correct answer and explanation

Correct answer: A. States with identical acceptance behavior for every future input

Indistinguishable states have equivalent right languages.

Question 26. What is an NFA?

  1. An infinite-state machine
  2. A nondeterministic finite automaton
  3. A machine with a mandatory stack
  4. A grammar without productions
Show correct answer and explanation

Correct answer: B. A nondeterministic finite automaton

An NFA permits multiple possible transitions.

Question 27. For an NFA without epsilon transitions its transition function maps to?

  1. Exactly one state always
  2. Only accepting states
  3. Subsets of Q
  4. Whole languages necessarily
Show correct answer and explanation

Correct answer: C. Subsets of Q

An NFA transition may return zero or more destination states.

Question 28. When does an NFA accept a string?

  1. Only if every run accepts
  2. Only if it has exactly one run
  3. Only if all states accept
  4. When at least one possible run ends in an accepting state
Show correct answer and explanation

Correct answer: D. When at least one possible run ends in an accepting state

Existential choice characterizes NFA acceptance.

Question 29. Can an NFA recognize a language beyond DFA expressive power?

  1. No
  2. Yes all context-free languages
  3. Yes all decidable languages
  4. Yes all recursively enumerable languages
Show correct answer and explanation

Correct answer: A. No

NFAs and DFAs recognize exactly the regular languages.

Question 30. What does epsilon transition mean in an epsilon-NFA?

  1. A transition consuming two input symbols
  2. A transition consuming no input symbol
  3. An automatic reset after each character
  4. Only an accepting state
Show correct answer and explanation

Correct answer: B. A transition consuming no input symbol

Epsilon moves change state without reading a symbol.

Question 31. What is epsilon-closure of an NFA state?

  1. States reached only after reading all input
  2. All rejecting states
  3. States reachable through zero or more epsilon transitions
  4. Only the start state in every case
Show correct answer and explanation

Correct answer: C. States reachable through zero or more epsilon transitions

The closure includes the original state and epsilon-reachable states.

Question 32. What is the subset construction used for?

  1. Converting a DFA to a Turing machine
  2. Making a CFG unambiguous always
  3. Removing all alphabets
  4. Converting an NFA to an equivalent DFA
Show correct answer and explanation

Correct answer: D. Converting an NFA to an equivalent DFA

Each DFA state represents a set of NFA states.

Question 33. For an NFA with n states subset construction yields at most?

  1. 2 to the n DFA states
  2. n minus one states
  3. n squared accepting states exactly
  4. n factorial states exactly
Show correct answer and explanation

Correct answer: A. 2 to the n DFA states

There are 2^n possible subsets of n states.

Question 34. Can equivalent NFAs and DFAs differ greatly in state count?

  1. No they always have equal state counts
  2. Yes
  3. Only when the alphabet is empty
  4. Only for infinite automata
Show correct answer and explanation

Correct answer: B. Yes

DFA conversion can create exponentially many states.

Question 35. An NFA may have multiple accepting states?

  1. No
  2. Only for a binary alphabet
  3. Yes
  4. Only if all states accept
Show correct answer and explanation

Correct answer: C. Yes

The accepting set can include any number of states.

Question 36. What is the union of languages L and M?

  1. Only strings belonging to both
  2. Only concatenations of strings
  3. Only strings outside both
  4. Strings belonging to L or M or both
Show correct answer and explanation

Correct answer: D. Strings belonging to L or M or both

Union combines the members of either language.

Question 37. What is the intersection of L and M?

  1. Strings belonging to both languages
  2. Strings in either language
  3. Only reversals
  4. Only empty strings
Show correct answer and explanation

Correct answer: A. Strings belonging to both languages

Intersection retains common members.

Question 38. What does language concatenation LM contain?

  1. Only strings of equal length
  2. All xy with x in L and y in M
  3. All strings outside L
  4. Only symbols common to both alphabets
Show correct answer and explanation

Correct answer: B. All xy with x in L and y in M

Concatenation joins words from the two languages.

Question 39. What is Kleene star L-star?

  1. Exactly one word from L
  2. Only infinite concatenations
  3. All finite concatenations of zero or more words from L
  4. Only words of length one
Show correct answer and explanation

Correct answer: C. All finite concatenations of zero or more words from L

The zero-fold concatenation contributes epsilon.

Question 40. Does L-star always contain epsilon?

  1. No
  2. Only if L contains a one-symbol word
  3. Only if L is finite
  4. Yes
Show correct answer and explanation

Correct answer: D. Yes

Taking zero copies always yields epsilon.

Question 41. Is the complement of a regular language regular?

  1. Yes
  2. No
  3. Only for finite languages
  4. Only with an infinite alphabet
Show correct answer and explanation

Correct answer: A. Yes

A complete DFA can swap accepting and rejecting states.

Question 42. Is the union of two regular languages regular?

  1. No
  2. Yes
  3. Only if disjoint
  4. Only if they have the same number of states
Show correct answer and explanation

Correct answer: B. Yes

Regular languages are closed under union.

Question 43. Is the intersection of two regular languages regular?

  1. No
  2. Only when one language is empty
  3. Yes
  4. Only for unary alphabets
Show correct answer and explanation

Correct answer: C. Yes

A product DFA recognizes intersections.

Question 44. Is the concatenation of regular languages regular?

  1. No
  2. Only if both finite
  3. Only if they share a start state
  4. Yes
Show correct answer and explanation

Correct answer: D. Yes

NFAs or regular expressions establish closure.

Question 45. Is the reversal of a regular language regular?

  1. Yes
  2. No
  3. Only for palindromic languages
  4. Only if the language is finite
Show correct answer and explanation

Correct answer: A. Yes

Reversing an automaton’s transitions with suitable starts and finals yields an NFA.

Question 46. What is a regular expression used to describe?

  1. Every non-context-free language
  2. A regular language
  3. Only a Turing machine tape
  4. Only an infinite-state device
Show correct answer and explanation

Correct answer: B. A regular language

Regular expressions denote regular sets of strings.

Question 47. What language does expression a-star describe?

  1. One or more b symbols
  2. Exactly one a
  3. Zero or more a symbols
  4. Any binary string
Show correct answer and explanation

Correct answer: C. Zero or more a symbols

The star includes epsilon and all repetitions of a.

Question 48. What language does expression a-plus denote?

  1. Only the empty string
  2. Exactly zero a
  3. Only strings ending in b
  4. One or more occurrences of a
Show correct answer and explanation

Correct answer: D. One or more occurrences of a

Plus denotes positive repetition.

Question 49. What does the expression a vertical-bar b represent?

  1. Choice between a and b
  2. Concatenation ab only
  3. Exactly two occurrences of a
  4. The empty language only
Show correct answer and explanation

Correct answer: A. Choice between a and b

Alternation denotes union.

Question 50. Which theorem relates regular expressions and finite automata?

  1. Pythagoras theorem
  2. Kleene’s theorem
  3. Rice’s theorem exclusively
  4. Church-Rosser theorem
Show correct answer and explanation

Correct answer: B. Kleene’s theorem

Kleene’s theorem establishes equivalent descriptions of regular languages.

Theory of Automata MCQs — Set 2 (Questions 51–100)

Choose the answer and reveal an explanation.

Question 51. Is every finite language regular?

  1. No
  2. Only if it contains epsilon
  3. Yes
  4. Only if it is binary
Show correct answer and explanation

Correct answer: C. Yes

Finite unions of fixed-word expressions are regular.

Question 52. Is every infinite language nonregular?

  1. Yes
  2. Only if it contains epsilon
  3. Only if it is countable
  4. No
Show correct answer and explanation

Correct answer: D. No

Examples like a-star are infinite and regular.

Question 53. Is the language of binary strings ending in 01 regular?

  1. Yes
  2. No
  3. Only if length is even
  4. Only if alphabet is unary
Show correct answer and explanation

Correct answer: A. Yes

A DFA needs only track a finite suffix.

Question 54. Is the language of even-length strings over a finite alphabet regular?

  1. No
  2. Yes
  3. Only when the alphabet has one symbol
  4. Only if strings are palindromes
Show correct answer and explanation

Correct answer: B. Yes

A two-state DFA can track length parity.

Question 55. Is the language of binary strings containing 11 as a substring regular?

  1. No
  2. Only for bounded lengths
  3. Yes
  4. Only if every string begins with 1
Show correct answer and explanation

Correct answer: C. Yes

An automaton can remember whether consecutive ones have occurred.

Question 56. A language is regular if and only if it is recognized by?

  1. Only a two-stack Turing machine
  2. Any unrestricted grammar only
  3. A pushdown automaton but never a DFA
  4. A finite automaton
Show correct answer and explanation

Correct answer: D. A finite automaton

Finite automata characterize regular languages.

Question 57. The pumping lemma for regular languages gives?

  1. A necessary property of all regular languages
  2. A sufficient test that every language satisfying it is regular
  3. A way to minimize any CFG
  4. A proof of all languages being regular
Show correct answer and explanation

Correct answer: A. A necessary property of all regular languages

The pumping condition is necessary, not a complete characterization.

Question 58. What is a pumping length?

  1. The exact number of accepting states
  2. A threshold beyond which accepted words admit a specific decomposition
  3. The number of symbols in every word
  4. The total alphabet size
Show correct answer and explanation

Correct answer: B. A threshold beyond which accepted words admit a specific decomposition

The regular pumping lemma guarantees decompositions for sufficiently long words.

Question 59. In the regular pumping lemma, the pumped middle segment y must satisfy?

  1. Its length is zero
  2. It contains every alphabet symbol
  3. Its length is positive
  4. It is the entire string always
Show correct answer and explanation

Correct answer: C. Its length is positive

The lemma requires the middle segment not be empty.

Question 60. For regular pumping decomposition xyz, what bound is imposed on xy?

  1. Length of xy equals zero
  2. Length of xy exceeds p
  3. Length of xy must equal all of z
  4. Length of xy is at most p
Show correct answer and explanation

Correct answer: D. Length of xy is at most p

The prefix containing x and y stays within pumping length p.

Question 61. The classic language a^n b^n for n at least zero is?

  1. Context-free but not regular
  2. Regular
  3. Not context-free
  4. Finite
Show correct answer and explanation

Correct answer: A. Context-free but not regular

A PDA counts unmatched a symbols with its stack.

Question 62. Why can a DFA not generally recognize a^n b^n?

  1. It has no input alphabet
  2. It cannot store an unbounded counter using finitely many states
  3. It always needs two start states
  4. It cannot read b
Show correct answer and explanation

Correct answer: B. It cannot store an unbounded counter using finitely many states

Equal unbounded counts require memory beyond finite states.

Question 63. Is the language of all palindromes over a two-symbol alphabet regular?

  1. Yes
  2. Only because epsilon is included
  3. No
  4. Only for arbitrary lengths restricted to one
Show correct answer and explanation

Correct answer: C. No

Recognizing arbitrary mirror symmetry needs unbounded memory.

Question 64. Is the language of strings over a unary alphabet with even length regular?

  1. No
  2. Only with a stack
  3. Only with a Turing machine
  4. Yes
Show correct answer and explanation

Correct answer: D. Yes

A two-state parity automaton suffices.

Question 65. Can the pumping lemma be used to prove a language nonregular?

  1. Yes
  2. No
  3. Only for finite languages
  4. Only after constructing a minimal DFA
Show correct answer and explanation

Correct answer: A. Yes

A contradiction to necessary pumping behavior proves nonregularity.

Question 66. What does a context-free grammar contain?

  1. Only states and a transition function
  2. Variables terminals productions and a start symbol
  3. Only two stacks
  4. Only integers and a program counter
Show correct answer and explanation

Correct answer: B. Variables terminals productions and a start symbol

A CFG generates strings using variable-replacement rules.

Question 67. A CFG production ordinarily has which left side?

  1. Any arbitrary string including terminals
  2. Exactly two terminals
  3. One nonterminal symbol
  4. A Turing machine tape
Show correct answer and explanation

Correct answer: C. One nonterminal symbol

Context-free productions replace a single nonterminal.

Question 68. What is the start symbol of a grammar?

  1. Any terminal character
  2. The empty word only
  3. The final automaton state
  4. A designated nonterminal from which derivations begin
Show correct answer and explanation

Correct answer: D. A designated nonterminal from which derivations begin

Derivations start at the selected grammar variable.

Question 69. A terminal symbol in a grammar is?

  1. A symbol appearing in generated strings rather than being expanded as a nonterminal
  2. A variable always replaced
  3. A machine state
  4. A production number
Show correct answer and explanation

Correct answer: A. A symbol appearing in generated strings rather than being expanded as a nonterminal

Terminals form the output alphabet.

Question 70. A derivation step in a CFG?

  1. Swaps two accepting states
  2. Replaces a nonterminal using a production
  3. Changes an input alphabet
  4. Only changes a stack bottom marker
Show correct answer and explanation

Correct answer: B. Replaces a nonterminal using a production

A rule expands one selected nonterminal.

Question 71. What is a sentential form?

  1. Only a fully terminal word
  2. Only a graph vertex
  3. A string of terminals and nonterminals derivable from the start
  4. A state transition table
Show correct answer and explanation

Correct answer: C. A string of terminals and nonterminals derivable from the start

Intermediate derivation strings may contain variables.

Question 72. What is a leftmost derivation?

  1. A derivation replacing the rightmost terminal
  2. A path in the DFA only
  3. A derivation with no terminals
  4. A derivation replacing the leftmost nonterminal at each step
Show correct answer and explanation

Correct answer: D. A derivation replacing the leftmost nonterminal at each step

The chosen replacement order is always the leftmost variable.

Question 73. What does a parse tree represent?

  1. Hierarchical application of grammar productions
  2. Only an NFA state graph
  3. A shortest path
  4. A hash table
Show correct answer and explanation

Correct answer: A. Hierarchical application of grammar productions

The tree encodes syntactic structure.

Question 74. What does grammar ambiguity mean?

  1. The language is empty
  2. Some generated word has two distinct parse trees
  3. All productions are left-linear
  4. Every string has one derivation
Show correct answer and explanation

Correct answer: B. Some generated word has two distinct parse trees

Ambiguity concerns multiple parse structures for one word.

Question 75. Does every context-free language have an unambiguous grammar?

  1. Yes
  2. Only finite languages do
  3. No
  4. Only regular languages do not
Show correct answer and explanation

Correct answer: C. No

Some context-free languages are inherently ambiguous.

Question 76. Which machine class recognizes context-free languages by final state or empty stack conventions?

  1. Only deterministic finite automata
  2. Only Mealy machines
  3. Only linear bounded automata
  4. Nondeterministic pushdown automata
Show correct answer and explanation

Correct answer: D. Nondeterministic pushdown automata

NPDAs characterize context-free languages.

Question 77. What extra storage does a PDA possess beyond finite control?

  1. A stack
  2. An unlimited random-access array
  3. Two read-write tapes
  4. A priority queue
Show correct answer and explanation

Correct answer: A. A stack

The stack provides unbounded last-in-first-out memory.

Question 78. Which operation is typical for a PDA stack?

  1. Sort the stack in constant time
  2. Push or pop a symbol
  3. Read any depth directly
  4. Randomly access all stack cells
Show correct answer and explanation

Correct answer: B. Push or pop a symbol

PDA access is restricted to the top.

Question 79. Are deterministic PDAs as powerful as nondeterministic PDAs for language recognition?

  1. Yes for every context-free language
  2. Only when both have zero states
  3. No
  4. Only for finite languages
Show correct answer and explanation

Correct answer: C. No

Deterministic context-free languages form a proper subset of CFLs.

Question 80. Can every regular language be recognized by a PDA?

  1. No
  2. Only if it contains epsilon
  3. Only if it is infinite
  4. Yes
Show correct answer and explanation

Correct answer: D. Yes

A PDA can simulate a finite automaton without using its stack.

Question 81. What is a balanced-parentheses language an example of?

  1. A deterministic context-free language
  2. A finite language
  3. A non-recursively-enumerable language
  4. An empty language
Show correct answer and explanation

Correct answer: A. A deterministic context-free language

A stack can track unmatched opening parentheses.

Question 82. A grammar for balanced parentheses may use?

  1. S yields only a
  2. S yields (S)S or epsilon
  3. S yields ab only
  4. S yields SS without any base case
Show correct answer and explanation

Correct answer: B. S yields (S)S or epsilon

Recursive productions generate nested and concatenated balanced pairs.

Question 83. What is Chomsky normal form for a CFG generally based on?

  1. Rules with arbitrary five nonterminals
  2. Only rules A to epsilon for every A
  3. Rules A to BC or A to a with an optional start epsilon rule
  4. Only left-linear productions
Show correct answer and explanation

Correct answer: C. Rules A to BC or A to a with an optional start epsilon rule

CNF restricts rules to binary variables or one terminal with a start exception.

Question 84. What is Greibach normal form’s typical production shape?

  1. A to BC only
  2. A to epsilon for every variable
  3. A to two terminals only
  4. A to a followed by zero or more variables
Show correct answer and explanation

Correct answer: D. A to a followed by zero or more variables

GNF begins each non-epsilon production with a terminal.

Question 85. What is a nullable nonterminal?

  1. A variable able to derive the empty string
  2. A terminal omitted from Sigma
  3. Only an unreachable state
  4. A variable with no rules
Show correct answer and explanation

Correct answer: A. A variable able to derive the empty string

Nullable variables can derive epsilon.

Question 86. What is a unit production in a CFG?

  1. A to ab
  2. A to B with both symbols nonterminals
  3. A to epsilon
  4. A to aBC
Show correct answer and explanation

Correct answer: B. A to B with both symbols nonterminals

Unit rules replace one variable with another.

Question 87. What is a useless grammar symbol?

  1. Every start variable
  2. Every terminal
  3. One that cannot contribute to a terminal string derivable from the start
  4. Only an epsilon symbol
Show correct answer and explanation

Correct answer: C. One that cannot contribute to a terminal string derivable from the start

Non-generating or unreachable symbols can be removed.

Question 88. Is the union of two context-free languages context-free?

  1. No
  2. Only when disjoint
  3. Only when finite
  4. Yes
Show correct answer and explanation

Correct answer: D. Yes

A fresh start variable can choose either grammar.

Question 89. Is concatenation of context-free languages context-free?

  1. Yes
  2. No
  3. Only if both regular
  4. Only with the same alphabet size
Show correct answer and explanation

Correct answer: A. Yes

A grammar can derive a word from each language in sequence.

Question 90. Is the Kleene star of a context-free language context-free?

  1. No
  2. Yes
  3. Only for finite languages
  4. Only if epsilon is absent
Show correct answer and explanation

Correct answer: B. Yes

A new recursive start variable concatenates zero or more words.

Question 91. Are context-free languages closed under arbitrary intersection?

  1. Yes
  2. Only for binary alphabets
  3. No
  4. Only for finite grammars
Show correct answer and explanation

Correct answer: C. No

Intersections of CFLs need not be context-free.

Question 92. Are context-free languages closed under complement?

  1. Yes
  2. Only for deterministic pushdown automata all CFLs
  3. Only under reversal
  4. No
Show correct answer and explanation

Correct answer: D. No

General CFLs are not closed under complement.

Question 93. Is the intersection of a CFL with a regular language context-free?

  1. Yes
  2. No
  3. Only if the regular language is finite
  4. Only when alphabets differ
Show correct answer and explanation

Correct answer: A. Yes

A PDA can be combined with a finite automaton.

Question 94. Is every regular language context-free?

  1. No
  2. Yes
  3. Only infinite regular languages
  4. Only those containing epsilon
Show correct answer and explanation

Correct answer: B. Yes

Every regular language has a context-free grammar.

Question 95. Is every context-free language regular?

  1. Yes
  2. Only those with nonterminals
  3. No
  4. Only if they contain epsilon
Show correct answer and explanation

Correct answer: C. No

Equal-count languages provide counterexamples.

Question 96. What does a pumping lemma for CFLs require for sufficiently long words?

  1. Exactly three parts with one mandatory DFA loop
  2. No length constraint
  3. Only one accepting state
  4. A decomposition into five parts with two pumpable portions
Show correct answer and explanation

Correct answer: D. A decomposition into five parts with two pumpable portions

The CFL lemma pumps v and x in uvwxy.

Question 97. In the CFL pumping lemma, what holds for the two pumped pieces v and x?

  1. Their combined length is positive
  2. Both must be empty
  3. Both must be terminals a only
  4. They always have equal lengths
Show correct answer and explanation

Correct answer: A. Their combined length is positive

At least one pumpable portion is nonempty.

Question 98. What classic language is not context-free?

  1. a^n b^n
  2. a^n b^n c^n for n at least zero
  3. Balanced parentheses
  4. All binary strings
Show correct answer and explanation

Correct answer: B. a^n b^n c^n for n at least zero

One stack cannot enforce three synchronized unbounded counts in this form.

Question 99. Can a pushdown automaton recognize a^n b^n?

  1. No
  2. Only using two stacks
  3. Yes
  4. Only if n is bounded
Show correct answer and explanation

Correct answer: C. Yes

One stack records the number of a symbols before checking b symbols.

Question 100. What is an inherently ambiguous context-free language?

  1. A language with an ambiguous grammar but a different unambiguous grammar
  2. Every regular language
  3. A language with no derivations
  4. One for which every CFG generating it is ambiguous
Show correct answer and explanation

Correct answer: D. One for which every CFG generating it is ambiguous

Inherent ambiguity is a property of the language, not just one grammar.

Theory of Automata MCQs — Set 3 (Questions 101–150)

Select an answer and reveal the explanation.

Question 101. A Turing machine has which feature absent from a finite automaton?

  1. An unbounded read-write tape
  2. A finite state set
  3. An input alphabet
  4. A start state
Show correct answer and explanation

Correct answer: A. An unbounded read-write tape

Its tape provides unbounded storage in the mathematical model.

Question 102. The control unit of a standard Turing machine has?

  1. Infinitely many mandatory states
  2. Finitely many states
  3. No states
  4. One accepting state only
Show correct answer and explanation

Correct answer: B. Finitely many states

Unbounded memory is in the tape rather than finite control.

Question 103. A standard Turing-machine transition can?

  1. Read only and never write
  2. Move without any state
  3. Write a symbol and move the tape head
  4. Accept every word automatically
Show correct answer and explanation

Correct answer: C. Write a symbol and move the tape head

Transitions update tape and state and move the head.

Question 104. What is a tape alphabet?

  1. Only input symbols excluding the blank
  2. Only accepting states
  3. Only transition directions
  4. Symbols permitted on the Turing-machine tape
Show correct answer and explanation

Correct answer: D. Symbols permitted on the Turing-machine tape

The tape alphabet includes input and working symbols.

Question 105. The blank symbol on a Turing-machine tape represents?

  1. An unfilled tape cell
  2. The unique start state
  3. Every input symbol
  4. The accept state
Show correct answer and explanation

Correct answer: A. An unfilled tape cell

Cells not containing meaningful data initially carry blanks.

Question 106. What does a Turing machine’s configuration describe?

  1. Only its input alphabet
  2. Its state tape contents and head position
  3. Only its accepted language
  4. Only the number of states
Show correct answer and explanation

Correct answer: B. Its state tape contents and head position

A configuration captures a complete instantaneous computation description.

Question 107. When does a Turing machine accept an input?

  1. Whenever it moves right
  2. Only after scanning every possible tape cell
  3. When its computation enters an accepting halt condition
  4. Whenever it writes a blank
Show correct answer and explanation

Correct answer: C. When its computation enters an accepting halt condition

Accepting computation halts in an accepting outcome.

Question 108. What happens when a Turing machine loops forever on an input?

  1. It automatically accepts
  2. It automatically rejects
  3. The input becomes empty
  4. It neither accepts nor rejects through a halt
Show correct answer and explanation

Correct answer: D. It neither accepts nor rejects through a halt

Infinite computation has no halting decision.

Question 109. What is a decider?

  1. A Turing machine that halts on every input and answers membership correctly
  2. Any Turing machine with one final state
  3. Only a finite automaton
  4. A machine that loops on rejected inputs
Show correct answer and explanation

Correct answer: A. A Turing machine that halts on every input and answers membership correctly

A decider terminates on all inputs.

Question 110. What is a recognizer for a language?

  1. A machine that halts on all inputs necessarily
  2. A machine that accepts members and may loop on nonmembers
  3. A machine recognizing only regular languages
  4. A machine without a tape
Show correct answer and explanation

Correct answer: B. A machine that accepts members and may loop on nonmembers

Recognizers need not terminate on words outside the language.

Question 111. A language is decidable when?

  1. It must be finite
  2. It must be regular
  3. Some Turing machine halts on every input and determines membership
  4. Only a PDA accepts it
Show correct answer and explanation

Correct answer: C. Some Turing machine halts on every input and determines membership

Decidability requires a total membership algorithm.

Question 112. A language is Turing-recognizable if?

  1. Only a DFA can recognize it
  2. Every input must be accepted
  3. All inputs must halt
  4. A Turing machine accepts exactly its members
Show correct answer and explanation

Correct answer: D. A Turing machine accepts exactly its members

Nonmembers may reject or loop.

Question 113. Are all decidable languages Turing-recognizable?

  1. Yes
  2. No
  3. Only finite languages
  4. Only context-free languages
Show correct answer and explanation

Correct answer: A. Yes

A decider also serves as a recognizer.

Question 114. Are all Turing-recognizable languages decidable?

  1. Yes
  2. No
  3. Only when the alphabet is binary
  4. Only for deterministic machines
Show correct answer and explanation

Correct answer: B. No

Some recognizable sets have no total decision procedure.

Question 115. Which class is also called recursively enumerable languages?

  1. Only regular languages
  2. Only finite languages
  3. Turing-recognizable languages
  4. Only deterministic context-free languages
Show correct answer and explanation

Correct answer: C. Turing-recognizable languages

The terms refer to languages accepted by Turing machines.

Question 116. Are all finite languages decidable?

  1. No
  2. Only singleton languages
  3. Only if epsilon is excluded
  4. Yes
Show correct answer and explanation

Correct answer: D. Yes

Membership can compare input against a finite list.

Question 117. Are all regular languages decidable?

  1. Yes
  2. No
  3. Only infinite regular languages
  4. Only with epsilon moves
Show correct answer and explanation

Correct answer: A. Yes

A DFA halts after a finite input scan.

Question 118. Are all context-free languages decidable?

  1. No
  2. Yes
  3. Only deterministic context-free languages
  4. Only those without epsilon
Show correct answer and explanation

Correct answer: B. Yes

CFG membership has terminating algorithms such as CYK after conversion.

Question 119. What is a universal Turing machine?

  1. A DFA with unlimited states
  2. A machine accepting every word
  3. A machine that simulates another encoded Turing machine on encoded input
  4. A PDA with only one stack symbol
Show correct answer and explanation

Correct answer: C. A machine that simulates another encoded Turing machine on encoded input

Universality uses encodings of machines and their inputs.

Question 120. What is a machine encoding?

  1. An infinite tape of random values
  2. Only the final answer
  3. A network protocol
  4. A finite string representing a machine description
Show correct answer and explanation

Correct answer: D. A finite string representing a machine description

Machine descriptions can be represented as finite data.

Question 121. The halting problem asks whether?

  1. A given Turing machine halts on a given input
  2. A DFA has any accepting state
  3. A CFG has a start symbol
  4. A language has at least one letter
Show correct answer and explanation

Correct answer: A. A given Turing machine halts on a given input

The general input-pair halting question is undecidable.

Question 122. Is the general Turing-machine halting problem decidable?

  1. Yes
  2. No
  3. Only with two tapes
  4. Only with a larger alphabet
Show correct answer and explanation

Correct answer: B. No

No algorithm correctly decides halting for every machine-input pair.

Question 123. What proof technique establishes the halting problem undecidable?

  1. Only counting symbols
  2. Bubble sorting
  3. Diagonalization and contradiction
  4. Linear regression
Show correct answer and explanation

Correct answer: C. Diagonalization and contradiction

A hypothetical halting decider leads to a self-reference contradiction.

Question 124. Does an undecidable problem have no yes-instances?

  1. Yes
  2. Only if it is infinite
  3. Only if machines are nondeterministic
  4. No
Show correct answer and explanation

Correct answer: D. No

Undecidable means no total algorithm solves all inputs, not that all answers are no.

Question 125. What does a reduction from problem A to B help establish?

  1. A solution for B could be used to solve A
  2. B must be finite
  3. A and B have equal input lengths
  4. Both problems are regular
Show correct answer and explanation

Correct answer: A. A solution for B could be used to solve A

Reductions transfer algorithmic solvability or hardness.

Question 126. To show B undecidable by reduction one can?

  1. Reduce B to a known decidable problem
  2. Reduce a known undecidable problem A to B
  3. Only test ten instances
  4. Construct a DFA for B
Show correct answer and explanation

Correct answer: B. Reduce a known undecidable problem A to B

If B were decidable the reduction would decide A, contradicting undecidability of A.

Question 127. What is a many-one computable reduction?

  1. An arbitrary correspondence without computability
  2. A state minimization step
  3. A computable mapping preserving membership answers
  4. A grammar production
Show correct answer and explanation

Correct answer: C. A computable mapping preserving membership answers

Computable mappings convert instances while preserving yes and no outcomes.

Question 128. What does Rice’s theorem concern?

  1. Every DFA transition
  2. Only CFG ambiguity
  3. All finite-set membership problems
  4. Nontrivial semantic properties of languages recognized by Turing machines
Show correct answer and explanation

Correct answer: D. Nontrivial semantic properties of languages recognized by Turing machines

Nontrivial properties of recognized language semantics are undecidable.

Question 129. Is the property that a Turing machine accepts the empty language decidable?

  1. No
  2. Yes for all Turing machines
  3. Only when the machine uses one tape
  4. Only if the alphabet is unary
Show correct answer and explanation

Correct answer: A. No

Turing-machine language emptiness is undecidable.

Question 130. Is equivalence of arbitrary Turing machines’ accepted languages decidable?

  1. Yes
  2. No
  3. Only when their state counts match
  4. Only if both halt on every input
Show correct answer and explanation

Correct answer: B. No

General equivalence is an undecidable semantic property.

Question 131. A language and its complement are both Turing-recognizable exactly when the language is?

  1. Finite
  2. Regular
  3. Decidable
  4. Context-free
Show correct answer and explanation

Correct answer: C. Decidable

Dovetailing the two recognizers yields a halting decision procedure.

Question 132. What is dovetailing in computability?

  1. Running one computation forever before the next
  2. Only compressing machine code
  3. Replacing the tape with a queue
  4. Interleaving steps of multiple computations so each receives progress
Show correct answer and explanation

Correct answer: D. Interleaving steps of multiple computations so each receives progress

Dovetailing avoids starvation among simulated computations.

Question 133. If L is decidable is its complement decidable?

  1. Yes
  2. No
  3. Only when L is finite
  4. Only when L is regular
Show correct answer and explanation

Correct answer: A. Yes

A decider can swap accept and reject outcomes.

Question 134. Are recognizable languages closed under union?

  1. No
  2. Yes
  3. Only for finite languages
  4. Only for regular sets
Show correct answer and explanation

Correct answer: B. Yes

Simulate both recognizers fairly and accept when either accepts.

Question 135. Are recognizable languages closed under intersection?

  1. No
  2. Only for one-letter alphabets
  3. Yes
  4. Only if they are decidable
Show correct answer and explanation

Correct answer: C. Yes

Fairly simulate both and accept after both have accepted.

Question 136. Can a nondeterministic Turing machine recognize more languages than a deterministic one?

  1. Yes all uncountable languages
  2. Yes every undecidable language
  3. Only for finite alphabets
  4. No
Show correct answer and explanation

Correct answer: D. No

Dovetailing nondeterministic branches yields equivalent recognizable power.

Question 137. Does adding a second tape increase the class of Turing-decidable languages?

  1. No
  2. Yes
  3. Only for unary languages
  4. Only for finite languages
Show correct answer and explanation

Correct answer: A. No

Multitape machines can be simulated by single-tape machines.

Question 138. A multitape Turing machine can improve?

  1. The set of decidable languages
  2. Efficiency of simulation and algorithms
  3. The cardinality of finite alphabets
  4. Whether a machine can have states
Show correct answer and explanation

Correct answer: B. Efficiency of simulation and algorithms

Extra tapes affect convenience and running time, not computability.

Question 139. Can a standard Turing machine simulate finite automata?

  1. No
  2. Only with two input heads
  3. Yes
  4. Only with no tape
Show correct answer and explanation

Correct answer: C. Yes

It can emulate finite-state computations.

Question 140. Can a standard Turing machine simulate pushdown automata?

  1. No
  2. Only deterministic PDAs
  3. Only empty-stack PDAs
  4. Yes
Show correct answer and explanation

Correct answer: D. Yes

A Turing machine can represent and update a stack.

Question 141. A linear bounded automaton has?

  1. Tape space limited linearly by input length
  2. Exactly one tape cell
  3. No tape at all
  4. Unlimited independently addressable tapes by definition
Show correct answer and explanation

Correct answer: A. Tape space limited linearly by input length

An LBA operates within a tape region bounded by input length.

Question 142. Which language family is associated with linear bounded automata?

  1. Only regular languages
  2. Context-sensitive languages
  3. Only finite languages
  4. Only recursively enumerable languages as an exact characterization
Show correct answer and explanation

Correct answer: B. Context-sensitive languages

Nondeterministic LBAs characterize context-sensitive languages.

Question 143. Type 3 in the Chomsky hierarchy denotes?

  1. Context-free grammars
  2. Context-sensitive grammars
  3. Regular grammars
  4. Unrestricted grammars
Show correct answer and explanation

Correct answer: C. Regular grammars

Type 3 is the regular grammar class.

Question 144. Type 2 in the Chomsky hierarchy denotes?

  1. Regular grammars only
  2. Unrestricted grammars only
  3. Context-sensitive grammars only
  4. Context-free grammars
Show correct answer and explanation

Correct answer: D. Context-free grammars

Type 2 permits single-nonterminal production left sides.

Question 145. Type 1 in the Chomsky hierarchy denotes?

  1. Context-sensitive grammars
  2. Regular grammars
  3. Context-free grammars only
  4. Finite automata only
Show correct answer and explanation

Correct answer: A. Context-sensitive grammars

Type 1 grammars generate context-sensitive languages.

Question 146. Type 0 grammars generate?

  1. Only regular languages
  2. Recursively enumerable languages
  3. Only finite languages
  4. Only deterministic context-free languages
Show correct answer and explanation

Correct answer: B. Recursively enumerable languages

Unrestricted grammars match Turing-recognizable languages.

Question 147. Which hierarchy inclusion is correct?

  1. Context-free is contained in regular
  2. Context-sensitive is contained in finite
  3. Regular is contained in context-free
  4. Recursively enumerable is contained in regular
Show correct answer and explanation

Correct answer: C. Regular is contained in context-free

Regular languages form a proper subclass of CFLs.

Question 148. Which hierarchy inclusion correctly places context-free languages in the Chomsky hierarchy?

  1. Context-sensitive is contained in regular
  2. Type 0 is contained in type 3
  3. Every CFL is finite
  4. Context-free is contained in context-sensitive
Show correct answer and explanation

Correct answer: D. Context-free is contained in context-sensitive

The Chomsky hierarchy places CFLs within context-sensitive languages.

Question 149. Which family includes the language a^n b^n c^n for n at least one?

  1. Context-sensitive
  2. Regular
  3. Context-free
  4. Finite only
Show correct answer and explanation

Correct answer: A. Context-sensitive

Three synchronized counts are context-sensitive but not context-free.

Question 150. Which is the most expressive among the four Chomsky grammar types?

  1. Type 3 regular
  2. Type 0 unrestricted
  3. Type 2 context-free
  4. Type 1 context-sensitive
Show correct answer and explanation

Correct answer: B. Type 0 unrestricted

Type 0 covers the broadest class of generated languages.

Theory of Automata MCQs — Set 4 (Questions 151–200)

Choose an answer and reveal the explanation.

Question 151. What is the CYK algorithm used for?

  1. DFA minimization
  2. Computing shortest paths
  3. Membership testing for context-free languages in suitable normal form
  4. Encrypting grammar rules
Show correct answer and explanation

Correct answer: C. Membership testing for context-free languages in suitable normal form

CYK uses dynamic programming on a CFG in Chomsky normal form.

Question 152. For a fixed grammar in CNF, classical CYK parsing of a length n string takes?

  1. O(log n) time
  2. O(1) time
  3. O(2 to the n) time necessarily
  4. O(n cubed) time
Show correct answer and explanation

Correct answer: D. O(n cubed) time

The algorithm considers substrings and split positions.

Question 153. What does FIRST of a grammar symbol describe?

  1. Terminals that may begin derived strings
  2. Only final states
  3. Only strings ending with a symbol
  4. Only production numbers
Show correct answer and explanation

Correct answer: A. Terminals that may begin derived strings

FIRST sets support predictive parsing.

Question 154. What does FOLLOW of a nonterminal describe?

  1. Only its leftmost derived symbol
  2. Terminals that can occur immediately after it in a sentential form
  3. The input alphabet size
  4. The number of rules
Show correct answer and explanation

Correct answer: B. Terminals that can occur immediately after it in a sentential form

FOLLOW sets guide parser decisions.

Question 155. An LL(1) parser uses?

  1. Two stacks and a Turing tape
  2. A rightmost derivation in reverse
  3. One input lookahead symbol with left-to-right leftmost derivation parsing
  4. No grammar information
Show correct answer and explanation

Correct answer: C. One input lookahead symbol with left-to-right leftmost derivation parsing

LL(1) identifies a predictive parsing method.

Question 156. Left recursion causes difficulty for?

  1. All possible Turing machines
  2. Every bottom-up parser necessarily
  3. All regular languages
  4. Naive recursive-descent predictive parsing
Show correct answer and explanation

Correct answer: D. Naive recursive-descent predictive parsing

Direct left recursion can make top-down calls loop without consuming input.

Question 157. Left factoring helps?

  1. Defer a grammar choice when productions share a prefix
  2. Increase grammar ambiguity deliberately
  3. Remove every terminal
  4. Turn any CFL into a regular language
Show correct answer and explanation

Correct answer: A. Defer a grammar choice when productions share a prefix

Factoring common prefixes supports predictive selection.

Question 158. A parse tree’s leaves read left to right form?

  1. Only nonterminals
  2. The generated terminal string, ignoring epsilon leaves
  3. The set of states
  4. Only the start symbol
Show correct answer and explanation

Correct answer: B. The generated terminal string, ignoring epsilon leaves

Parse-tree yield is the terminal word.

Question 159. Ambiguity in a CFG means?

  1. The language is non-context-free
  2. Every production is nullable
  3. Some string has two distinct parse trees
  4. No terminals occur
Show correct answer and explanation

Correct answer: C. Some string has two distinct parse trees

Different parse trees represent multiple derivation structures.

Question 160. Can an ambiguous CFG generate a regular language?

  1. No
  2. Only with no productions
  3. Only with an infinite alphabet
  4. Yes
Show correct answer and explanation

Correct answer: D. Yes

A regular language may be described by an ambiguous grammar.

Question 161. Is CFG emptiness decidable?

  1. Yes
  2. No
  3. Only for a single nonterminal
  4. Only when epsilon is excluded
Show correct answer and explanation

Correct answer: A. Yes

Productive nonterminal analysis detects whether any terminal word is generated.

Question 162. Is CFG membership decidable?

  1. No
  2. Yes
  3. Only for deterministic CFGs
  4. Only if the string is empty
Show correct answer and explanation

Correct answer: B. Yes

Parsing algorithms decide whether a given string belongs to a CFG language.

Question 163. Is CFG equivalence decidable in general?

  1. Yes
  2. Only by DFA minimization
  3. No
  4. Only using CYK in polynomial time
Show correct answer and explanation

Correct answer: C. No

Equivalence of arbitrary CFL grammars is undecidable.

Question 164. Is CFG universality decidable in general?

  1. Yes
  2. Only when the alphabet has two symbols
  3. Only with a linear bounded automaton
  4. No
Show correct answer and explanation

Correct answer: D. No

Whether an arbitrary CFG generates all strings is undecidable.

Question 165. Is DFA equivalence decidable?

  1. Yes
  2. No
  3. Only if both have equal numbers of states
  4. Only for unary alphabets
Show correct answer and explanation

Correct answer: A. Yes

A product automaton can search for a distinguishing word.

Question 166. Is DFA emptiness decidable?

  1. No
  2. Yes
  3. Only if all states accept
  4. Only if epsilon moves are present
Show correct answer and explanation

Correct answer: B. Yes

Reachability determines whether any final state can be reached.

Question 167. Is NFA membership decidable?

  1. No
  2. Only if NFA has one accepting state
  3. Yes
  4. Only if it is deterministic
Show correct answer and explanation

Correct answer: C. Yes

A finite set of reachable states can be simulated.

Question 168. Is regular-language inclusion decidable for DFA descriptions?

  1. No
  2. Only if both languages are finite
  3. Only when alphabets differ
  4. Yes
Show correct answer and explanation

Correct answer: D. Yes

Check emptiness of the intersection with the complement.

Question 169. Is finiteness of a DFA language decidable?

  1. Yes
  2. No
  3. Only for one-state DFAs
  4. Only for accepting all words
Show correct answer and explanation

Correct answer: A. Yes

A useful cycle on a path to acceptance implies infinite language.

Question 170. When does a DFA language become infinite?

  1. When every state is rejecting
  2. When a reachable cycle can lead to an accepting state
  3. Only when there are infinitely many states
  4. When the alphabet has two symbols
Show correct answer and explanation

Correct answer: B. When a reachable cycle can lead to an accepting state

Pumping a useful reachable cycle gives arbitrarily long accepted strings.

Question 171. The Myhill-Nerode relation groups strings by?

  1. Equal lengths only
  2. Alphabetical order only
  3. Indistinguishability by future suffixes for language membership
  4. Number of vowels only
Show correct answer and explanation

Correct answer: C. Indistinguishability by future suffixes for language membership

Equivalent prefixes have identical behavior under all continuations.

Question 172. Myhill-Nerode theorem characterizes regular languages by?

  1. A unique pushdown automaton
  2. Unbounded stack depth
  3. Every language being finite
  4. Finitely many right-congruence equivalence classes
Show correct answer and explanation

Correct answer: D. Finitely many right-congruence equivalence classes

Finite index of the relation is equivalent to regularity.

Question 173. The minimal complete DFA has as many states as?

  1. Distinct Myhill-Nerode equivalence classes
  2. Total words in the language
  3. Maximum word length
  4. Number of accepting paths only
Show correct answer and explanation

Correct answer: A. Distinct Myhill-Nerode equivalence classes

Each inequivalent residual language requires a separate state.

Question 174. How can two DFA states be shown distinguishable?

  1. Show both have outgoing transitions
  2. Find a suffix accepted from exactly one of them
  3. Give both the same name
  4. Use any empty input always
Show correct answer and explanation

Correct answer: B. Find a suffix accepted from exactly one of them

A discriminating suffix separates their future behavior.

Question 175. Can two different regular expressions define the same language?

  1. No
  2. Only if textually identical
  3. Yes
  4. Only when the alphabet is empty
Show correct answer and explanation

Correct answer: C. Yes

Regular expressions need not be syntactically unique.

Question 176. What is a Mealy machine?

  1. A PDA with two stacks
  2. A grammar in CNF
  3. A Turing decider only
  4. A finite-state transducer with outputs associated with transitions
Show correct answer and explanation

Correct answer: D. A finite-state transducer with outputs associated with transitions

Mealy output depends on the transition and current input.

Question 177. What is a Moore machine?

  1. A finite-state transducer with output associated with states
  2. A nondeterministic Turing machine
  3. A regular grammar only
  4. A stack-based parser
Show correct answer and explanation

Correct answer: A. A finite-state transducer with output associated with states

Moore outputs are attached to machine states.

Question 178. What distinguishes language recognizers from transducers?

  1. Transducers always require two tapes
  2. Transducers produce outputs while recognizers decide or recognize membership
  3. Recognizers always produce a number
  4. There is no distinction
Show correct answer and explanation

Correct answer: B. Transducers produce outputs while recognizers decide or recognize membership

Transducers map input histories or strings to outputs.

Question 179. Which input is needed to compute a Mealy transition output?

  1. Only a future accepting state
  2. Only stack height
  3. Current state and input symbol
  4. Only tape length
Show correct answer and explanation

Correct answer: C. Current state and input symbol

Mealy output labels are determined by current transition conditions.

Question 180. Moore output is determined by?

  1. Only next input symbol
  2. Length of remaining input only
  3. A stack top necessarily
  4. Current machine state
Show correct answer and explanation

Correct answer: D. Current machine state

Outputs are associated with states.

Question 181. Regular grammars commonly use which production form?

  1. Right-linear or left-linear rules under a consistent convention
  2. Any two nonterminals on the left
  3. Only unrestricted erasing rules
  4. Rules requiring a stack
Show correct answer and explanation

Correct answer: A. Right-linear or left-linear rules under a consistent convention

Linear grammar productions describe regular languages.

Question 182. A right-linear rule can look like?

  1. AB to BA
  2. A to aB
  3. A to BC
  4. aA to Ab
Show correct answer and explanation

Correct answer: B. A to aB

A terminal followed by at most one nonterminal is a standard right-linear shape.

Question 183. Is every regular grammar also context-free?

  1. No
  2. Only if it has no epsilon rules
  3. Yes
  4. Only when symbols are binary
Show correct answer and explanation

Correct answer: C. Yes

Regular productions are a restricted form of CFG rules.

Question 184. Which language is recognized by a one-state accepting DFA looping on all alphabet symbols?

  1. The empty language
  2. Only epsilon
  3. Exactly one-symbol strings
  4. Sigma-star
Show correct answer and explanation

Correct answer: D. Sigma-star

Every finite input leaves the machine in an accepting state.

Question 185. Which language is recognized by a one-state rejecting DFA looping on all alphabet symbols?

  1. The empty language
  2. Sigma-star
  3. Only epsilon
  4. All one-symbol strings
Show correct answer and explanation

Correct answer: A. The empty language

No input leads to acceptance.

Question 186. What is the difference between the empty language and the language containing epsilon?

  1. They are identical
  2. The latter has one string; the former has none
  3. Both have infinitely many strings
  4. The empty language contains a blank symbol
Show correct answer and explanation

Correct answer: B. The latter has one string; the former has none

The singleton epsilon language contains one zero-length string.

Question 187. What is the concatenation of the empty language with any language L?

  1. L
  2. The language containing epsilon
  3. The empty language
  4. Sigma-star
Show correct answer and explanation

Correct answer: C. The empty language

There is no left-hand word available for concatenation.

Question 188. What is the concatenation of the language containing epsilon with L?

  1. The empty language
  2. Only epsilon
  3. The complement of L
  4. L
Show correct answer and explanation

Correct answer: D. L

The empty word acts as the identity for concatenation.

Question 189. What is the Kleene star of the empty language?

  1. The language containing epsilon
  2. The empty language
  3. All one-symbol strings
  4. Sigma-star for any alphabet
Show correct answer and explanation

Correct answer: A. The language containing epsilon

Zero repetitions contribute epsilon and no positive repetitions are possible.

Question 190. What is the Kleene star of the singleton epsilon language?

  1. The empty language
  2. The singleton epsilon language
  3. Every string
  4. Only one-symbol words
Show correct answer and explanation

Correct answer: B. The singleton epsilon language

Concatenating any number of empty words still yields epsilon.

Question 191. For a regular language L, which operation preserves regularity?

  1. Arbitrary intersection of CFLs
  2. Halting-problem encoding
  3. Homomorphism
  4. Unbounded equal-counter extension always
Show correct answer and explanation

Correct answer: C. Homomorphism

Regular languages are closed under homomorphisms.

Question 192. Which closure property is useful to prove a language nonregular?

  1. Every subset of a regular language is regular
  2. Every infinite language is regular
  3. Regular languages are closed under arbitrary infinite unions
  4. Intersection with a regular language remains regular
Show correct answer and explanation

Correct answer: D. Intersection with a regular language remains regular

A nonregular intersection contradicts assumed regularity.

Question 193. Is a subset of a regular language necessarily regular?

  1. No
  2. Yes
  3. Only for binary alphabets
  4. Only when infinite
Show correct answer and explanation

Correct answer: A. No

Every language is a subset of Sigma-star, which is regular.

Question 194. Are regular languages closed under difference?

  1. No
  2. Yes
  3. Only if they are finite
  4. Only when both have the same state count
Show correct answer and explanation

Correct answer: B. Yes

Difference equals intersection with complement.

Question 195. Are regular languages closed under symmetric difference?

  1. No
  2. Only when disjoint
  3. Yes
  4. Only with a one-symbol alphabet
Show correct answer and explanation

Correct answer: C. Yes

Symmetric difference combines differences using union.

Question 196. What is a deterministic context-free language?

  1. Any CFL without epsilon
  2. Any language recognized by an NFA
  3. All recursively enumerable sets
  4. A language recognized by some deterministic PDA
Show correct answer and explanation

Correct answer: D. A language recognized by some deterministic PDA

Deterministic PDAs define this subclass of CFLs.

Question 197. Are deterministic context-free languages closed under complement?

  1. Yes under the standard DPDA language class
  2. No for every possible model
  3. Only if finite
  4. Only if regular
Show correct answer and explanation

Correct answer: A. Yes under the standard DPDA language class

Deterministic context-free languages have effective complement closure with appropriate acceptance conventions.

Question 198. Are context-free languages closed under reversal?

  1. No
  2. Yes
  3. Only for deterministic languages
  4. Only for finite alphabets of size one
Show correct answer and explanation

Correct answer: B. Yes

Reversing derivations appropriately yields another CFG.

Question 199. Are context-free languages closed under union?

  1. No
  2. Only for regular inputs
  3. Yes
  4. Only if both are finite
Show correct answer and explanation

Correct answer: C. Yes

A new start rule chooses between the grammars.

Question 200. Are context-free languages closed under intersection with regular languages?

  1. No
  2. Only if both languages are finite
  3. Only for one-character strings
  4. Yes
Show correct answer and explanation

Correct answer: D. Yes

A product of PDA and DFA recognizes the intersection.

Privacy Policy
Powered by CookieAdmin