Chapter 9 Flashcards
Which of the following is true about a finite-state machine (FSM)?
A) It has infinite memory and states.
B) It processes input strings to transition between states.
C) It can only recognize context-sensitive languages.
D) It halts for undecidable problems.
B) It processes input strings to transition between states.
What is the purpose of a state graph in an FSM?
A) To show the sequence of transitions.
B) To list all possible inputs.
C) To define the output at each state.
D) To identify halting problems.
A) To show the sequence of transitions.
Which of the following represents the same information as a state graph?
A) Quintuple
B) Turing machine tape
C) State table
D) Context-free grammar
C) State table
What is the primary difference between a finite-state machine and a Turing machine?
A) Turing machines have infinite tape; FSMs do not.
B) FSMs have more computational power than Turing machines.
C) Turing machines cannot recognize regular sets.
D) FSMs can recognize undecidable problems.
A) Turing machines have infinite tape; FSMs do not.
What does the quintuple of a Turing machine include?
A) A list of states, transitions, and tape symbols.
B) States, input alphabet, output alphabet, transition functions, and final state.
C) The initial state, final state, input alphabet, output alphabet, and tape.
D) The current state, input symbol, next state, output symbol, and direction of movement.
D) The current state, input symbol, next state, output symbol, and direction of movement.
A Turing machine recognizes a set if:
A) It halts on every input string.
B) It halts only for strings in the set.
C) It never halts for strings in the set.
D) It computes an infinite loop for the set.
B) It halts only for strings in the set.
What is the role of the tape in a Turing machine?
A) To store the input and provide infinite memory.
B) To define transitions between states.
C) To verify the grammar of context-free languages.
D) To enforce type-0 rules on languages.
A) To store the input and provide infinite memory.
The Halting Problem is undecidable because:
A) Turing machines cannot handle infinite loops.
B) There is no general algorithm to determine if a Turing machine will halt for all inputs.
C) Finite-state machines have limited memory.
D) Regular languages do not allow halting transitions.
B) There is no general algorithm to determine if a Turing machine will halt for all inputs.
Which of the following statements about the Halting Problem is true?
A) It is a P problem.
B) It is a problem specific to finite automata.
C) It proves the limits of computational problem-solving.
D) It can be solved using context-free grammars.
C) It proves the limits of computational problem-solving.
A problem is in class P if:
A) It can be solved in polynomial time by a deterministic Turing machine.
B) It can only be solved in exponential time.
C) It is verifiable in polynomial time by a deterministic Turing machine.
D) It is not verifiable in any time.
A) It can be solved in polynomial time by a deterministic Turing machine.
Which of the following is true about NP-complete problems?
A) Every NP-complete problem is also NP-hard.
B) Every NP-hard problem is NP-complete.
C) NP-complete problems cannot be reduced to each other.
D) They are solvable in polynomial time.
A) Every NP-complete problem is also NP-hard.
What is an example of an NP-complete problem?
A) Sorting a list
B) Traveling Salesperson Problem
C) Matrix multiplication
D) Adding two numbers
B) Traveling Salesperson Problem
Which type of formal language corresponds to regular expressions?
A) Type 0
B) Context-sensitive
C) Context-free
D) Regular
D) Regular
Context-free languages are recognized by:
A) Turing machines
B) Finite-state machines
C) Pushdown automata
D) Context-sensitive grammars
C) Pushdown automata
Which of the following is true about Type 0 grammars?
A) They generate only regular languages.
B) They generate all computable languages.
C) They can be parsed using finite automata.
D) They are less powerful than context-sensitive grammars.
B) They generate all computable languages.
