CSCE 222 Lecture 30

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

Finite State Automata

$M=(S,I,f,s_{0},F)$

• 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₀ is the start state
• F is a subset of accepting states (what we want to end on)

Language

$L(M)=\{x\in I^{*}~|~f(s_{0},x)\in F\}$

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 $T=(S,I,f,s_{0})$

• S a finite set of states
• I an input alphabet containing the blank sybmol (B)
• f is a partial function: $f:S\times I\rightarrow S\times I\times \{R,L\}$ (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 $x$. Suppose the control unit is originally in state $s$. If $f(s,x)$ is defined as $f(s,x)=(s',x',d)$, then the control unit will:

1. enter the state $s'$
2. erase $x$ from the tape, replacing it with $x'$, and
3. move right or left on the tape if $d$ is R or L, respectively.

If $f(s,x)$ is undefined, then the machine stops (halt).

Example

Adding Unary numbers on a Turing Machine: represent a number $n$ by $1\underbrace {1\ldots 1} _{n}$, 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 $(s,t,s',t',d)$ to specify $f$.

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)