Finite Automata: Understanding Input Tape and Symbols

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.

• 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 as it is used.
• When we reach the first blank cell, we stop.
• We always presume that once the first blank is encountered, the rest of the Tape is also blank.
• We read from left to right and never go back to a cell that was read before.

New Symbols for FA

• To streamline the design of the machine, some symbols are used.
• The arrows (directed edges) into or out of these states can be drawn at any angle. The START state is like a state connected to another state in a TG by a ʎ edge.
• We begin the process there, but we read no input letter. We just proceed immediately to the next state.

A New Symbol for FAs

• A start state has no arrows coming into it.

• An ACCEPT state is a shorthand notation for a dead-end final state - once entered, it cannot be left, shown on the next slide:

• A REJECT state is a dead-end state that is not final.

• READ states are introduced.
• These are depicted as diamond-shaped boxes.

• The FA that used to be drawn:

The FA that accepts all words ending in the letter a becomes, in the new symbolism:

• We have also used the electronic diagram notation for wires flowing into each other.                                          

• We have also used the electronic diagram notation for wires flowing into each other.

• Becomes:

end