Deterministic Automata

Fix . is called a deterministic automata if

1. is a finite set of states
2. is a start state
3. accept states
4. transition function

Interpretation

1. Get a word as input
2. Start at state
3. Read the word letter by letter: If you’re in state and read , move to
4. After reading all of , you’re in some state : If then ACCEPTS . If then REJECTS .

Definition

is defined recursively:

Definition

Homomorphism is just the only reasonable definition

Proposition

If is a homomorphism from to , then .

Corollary

We can always WLOG that .