Question:
Which of the following statements is TRUE about FSMs (Finite State Machines)?
Which of the following statements is TRUE about FSMs (Finite State Machines)?
Show Hint
FSMs have finite memory and accept exactly one language class. Which class is that?
Updated On: Jul 2, 2026
- FSMs can recognize all context-free languages
- FSMs can solve the halting problem
- Every regular language can be recognized by an FSM
- FSMs have an infinite memory
Show Solution
Verified By Collegedunia
The Correct Option is C
Solution and Explanation
Step 1: A finite state machine has a fixed, finite number of states and no auxiliary storage, so it has finite memory only. That rules out option (D).
Step 2: FSMs accept exactly the class of regular languages. Many context-free languages, such as \( \{ a^n b^n \mid n \ge 0 \} \), need counting and cannot be recognized, so option (A) is false.
Step 3: The halting problem is undecidable even for full Turing machines, so an FSM cannot solve it. Option (B) is false.
Step 4: By definition, regular languages are precisely those an FSM can recognize. So option (C) is the true statement.
Step 2: FSMs accept exactly the class of regular languages. Many context-free languages, such as \( \{ a^n b^n \mid n \ge 0 \} \), need counting and cannot be recognized, so option (A) is false.
Step 3: The halting problem is undecidable even for full Turing machines, so an FSM cannot solve it. Option (B) is false.
Step 4: By definition, regular languages are precisely those an FSM can recognize. So option (C) is the true statement.
Was this answer helpful?
0
0
Top CPET Computer Science Questions
- Which of the following is a key reason for choosing DRAM over SRAM for main memory?
- Which of the following components in an FPGA is responsible for implementing combinational and sequential logic?
- What is the main purpose of declaring a base class as virtual in multiple inheritance?
- What happens if a class contains at least one pure virtual function?
- What happens if a derived class defines a function with the same name as a base class function, but with a different parameter list?
View More Questions
Top CPET Automata Theory Questions
Top CPET Questions
- Which of the following is a key reason for choosing DRAM over SRAM for main memory?
- Which of the following components in an FPGA is responsible for implementing combinational and sequential logic?
- What is the main purpose of declaring a base class as virtual in multiple inheritance?
- What happens if a class contains at least one pure virtual function?
- What happens if a derived class defines a function with the same name as a base class function, but with a different parameter list?
View More Questions