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: 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 \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 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} . Suppose the control unit is originally in 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} . 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 $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 $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)