Reading

Examples 2.1.1, 2.1.2, and 2.1.3 of Theory of Computing, A Gentle Introduction.

Homework

Printout the homework and answer the questions on that paper.

Finite Automata - Our first machine model

Our first model of a machine will be based on the assumption that a fixed, finite amount of memory is available. Now, in any computer the memory is finite, but the point is that we effectively treat memory as infinite when we program, and are quite surprised if anything ever crashes due to insufficient memory. So, yes, a billion-bit memory is finite, but we don't usually worry about it. In our model, however, memory is finite and we're forced to think of it that way ... usually we'll have 1 bit, 2 bits ... maybe 9 or 10 bits of memory in our machine, but we're not usually talking millions or billions.

Introducing the diagram definition for Finite Automata

A finite automaton is a very simple kind of computer. It reads its input as a string of characters from some alphabet, and as it goes the only "memory" it has of what it's read is the state it's in. The machine consists of a finite number of states, and it simply changes from state-to-state as it reads input. One state is labelled as the "start" or "initial" state which, not surprisingly, is the state you start off in. Some states are labelled as accepting, and when the input is exhausted, the machine "accepts" the input string if it happens to have ended up in an accepting state. The set of strings accepted by a finite automaton M is, of course, a language --- the "language accepted by M", as we say, or "L(M)" for short.

We draw diagrams to represent these machines. The diagrams are directed graphs whose vertices are the states, and whose edges are transitions, which are rules to tell you which states to move to as you read characters. If an edge (i.e. transition) from state p to state q is labelled with character a, it means that when the machine is in state p and it reads character a it goes into state q. Some examples should make this quite clear:

Draw a machine accepting the language {ab,ba}	Given the machine below, give an English description of the language it accepts
Note: This is not the simplest machine accepting this language!	Answer: The machine accepts strings consisting of any number of copies of abc concatenated together.

The Rules

Here are some rules for finite automata. They are few and simple, and they basically add up to "you have to specify everything completely and unambiguously".

1. You need to have an input alphabet Σ in mind.
2. Every state in the machine has to have an outgoing transition arrow for each character in Σ, i.e. the machine can never "crash" because there's nowhere to go.
3. No state can have more than one outgoing transition for the same character in Σ, i.e. there can be no ambiguity about where to go next.
4. While a machine can have as many accepting states as it wants (including zero), a machine has to have one and only one start state.

ACTIVITY

We introduced JFLAP as a tool for playing with finite automata. For problems 4-9 below, I encourage you to use JFLAP to create and test your machines.

1. Give a brief English description of the language accepted by
   
2. Give a brief English description of the language accepted by
   
3. Give a brief English description of the language accepted by
   
4. Draw a machine that accepts exactly the strings over alphabet {a,b,c} that start with a and end with c.
5. Draw a machine that accepts exactly the strings over alphabet {a,b,c} of length 1,4,7,10,13,16,19,...
6. Draw a machine that accepts exactly the strings bba, baa and bbc over alphabet {a,b,c}.
7. Draw a machine that accepts everything over alphabet {a,b,c} except the strings bba, baa and bbc.
8. Draw a machine that accepts all strings over the alphabet {a,b,c} that start with b and have odd length.
9. Draw a machine that accepts exactly the strings over alphabet {a,b,c} that start with a and end with c, and which have even length.