# CSCE 222 Lecture 30

« previous | *Monday, April 18, 2011* | next »

## Finite State Automata

*S*is set of all states*I*is the input alphabet*f*is a transition function to get from one state to another based on input*s*_{0}is the start state*F*is a subset of accepting states (what we want to end on)

### Language

The set of all inputs such that the end result is an accepting state.

Two finite stata automata are called equivalent iff they share the same language

### Non-Deterministic FSA

A variation on Finite State Automata in which the transition function is replaced by a **transition relation** such that there might be several possible next states based on the current state and input. (next state is chosen at random)

A language that is accepted by a non-deterministic FSA can be recognized by a deterministic FSA.

#### Kleene's Theorem

A language is regular (Type 3) iff it can be recognized by a finite state automata.

## Turing Machines

A four-tuple

*S*a finite set of states*I*an input alphabet containing the blank sybmol (B)*f*is a partial function: (defined on a subset of*S*×*I*and outputs a new state and direction.*s_0*start state

Control unit contains the states and can write to an infinite tape in both directions.

At each step, the control unit reads the current tape symbol . Suppose the control unit is originally in state . If is defined as , then the control unit will:

- enter the state
- erase from the tape, replacing it with , and
- move right or left on the tape if is
*R*or*L*, respectively.

If is undefined, then the machine stops (halt).

### Example

**Adding Unary numbers on a Turing Machine:** represent a number by , where the first 1 is the "start of number" symbol. Numbers will be separated by an asterisk (*). For example, (2,3) would be represented as 111*1111. The output of this pair should be 111111

We will use to specify .

Instructions:

- (s_0, 1, s, B, R)
- (s_1, *, s_3, B, R)
- (s_1, 1, s_3, B, R)
- (s_2, 1, s_2, 1, R)
- (s_2, *, s_3, 1, R)