Theory of Computation Lecture 9

Study Notes

Finite-state machines (FSMs) are models that represent various technologies in computing, including components found in computers.
They consist of a finite set of states, an initial state, a designated input alphabet, and a transition function that maps state-input pairs to new states.
Common applications include spell checking, grammar checking, text indexing/searching, and speech recognition.

FSMs can be represented using state tables, showing states, inputs, and associated outputs.
State diagrams are graphical representations using circles for states and arrows for transitions, labeled with input-output pairs.

The FSM processes an input string symbol by symbol, transitioning through states based on the transition function.
Each transition generates an output, leading to an output string that corresponds to the input string through a defined output function.

Unit-Delay Machine:
- Delays the output string by one time unit through three states (s0, s1, s2).
- State s1 remembers if the previous input was 1; s2 remembers if it was 0.
- Outputs 0 for initial transition and reflects the delayed input thereafter.
Error Detection Machine:
- Detects three consecutive 1s to indicate a transmission error, reflecting output accordingly.
- Utilizes three states to track sequences of 1s:
  - State s0: previous input was not 1.
  - State s1: previous input was 1, but not two consecutive 1s.
  - State s2: two previous inputs were 1s.
- An input of 0 resets the machine to state s0.

FSMs have limited memory capabilities due to a finite number of states.
They cannot perform tasks requiring unbounded memory, hindering their effectiveness for certain applications.