Finite Automata: Understanding Input Tape and Symbols
Classified in Electronics
Written on in
English with a size of 126.48 KB
New Terminology of Finite Automata
- We call the part of the FA where the input string resides while it is being run the Input Tape.
- The Input Tape must be long enough for any possible input. Since any word in a* is a possible input, the Tape must be infinitely long.
- The Tape has a first location for the first letter of the input, then a second location, and so on.
- Therefore, we say that the Tape is infinite in only one direction.
A New Format for FAs
- The locations into which we put the input letters are called cells. (See the table below)
- Name the cells with lowercase Roman numerals.
a | a | b | Δ | Δ |
- The Δ is used to indicate the blank.
- Input string is aab.
- Input tape parsing.
- As the Tape is processed on the machine, we read one letter at a time and eliminate each