CSCE 222 Lecture 30

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

Finite State Automata

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(s, x)} is defined as Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(s,x) = (s', x', d)} , then the control unit will:

enter the state Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s'}
erase Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} from the tape, replacing it with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x'} , and
move right or left on the tape if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} is R or L, respectively.

If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(s,x)} is undefined, then the machine stops (halt).

Example

Adding Unary numbers on a Turing Machine: represent a number Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} by Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (s, t, s', t', d)} to specify Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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)