Finite Automata

CS051: Models of Computation Lecture 02 Finite Automata (a.k.a Finite State Machines or FSMs)

Eugene Charniak

CS051

Lecture 02: Finite Automata (a.k.a Finite State Machines or FSMs)

1

Finite Automata (a.k.a Finite State Machines or FSMs)

Question: What is a computer? • real computers too complex for any theory • need manageable mathematical abstraction • idealized models: accurate in some ways, not others important ideas • formal definition of finite state machines • deterministic vs. non-deterministic finite state machines • regular languages • operations on regular languages • regular expressions • pumping lemma

CS051

Lecture 02: Finite Automata (a.k.a Finite State Machines or FSMs)

2

Example: An Automatic Door

front pad

rear pad

door

• open when person approaches • hold open until person clears • don’t open when someone standing behind the door

CS051

Lecture 02: Finite Automata (a.k.a Finite State Machines or FSMs)

3

Example: An Automatic Door

REAR BOTH NEITHER

FRONT

closed

FRONT REAR BOTH open

NEITHER

States: • open • closed Sensor: • FRONT: someone on front pad • REAR: someone on rear pad • BOTH: someone on both pads • NEITHER no one on either pad.

CS051

Lecture 02: Finite Automata (a.k.a Finite State Machines or FSMs)

4

Example: An Automatic Door

REAR BOTH NEITHER

FRONT

closed

FRONT REAR BOTH open

NEITHER

CS051

NEITHER

FRONT

REAR

BOTH

closed

closed

open

closed

closed

open

closed

open

open

open

Lecture 02: Finite Automata (a.k.a Finite State Machines or FSMs)

5

Informal Definition

0

1

1

q 1

0

q 2

q3 0,1

The machine M1 : • states: q1 , q2 , and q3 . • start state: q1 (clearly labeled arrow from nowhere). • accept state: q2 (double circle or marked with shading). • state transitions: arrows.

CS051

Lecture 02: Finite Automata (a.k.a Finite State Machines or FSMs)

6

Informal Definition

0

1

1

q 1

0

q 2

q3 0,1

On an input string • begins in start state q1 • after reading each symbol, M1 takes transition with matching label. After reading last symbol, M1 produces output: • accept if M1 is an accepting state. • reject otherwise.

CS051

Lecture 02: Finite Automata (a.k.a Finite State Machines or FSMs)

7

Informal Definition

0 q 1

1

1

0

q 2

q3 0,1

What happens on input strings • 1101 • 0010 • 01100

CS051

Lecture 02: Finite Automata (a.k.a Finite State Machines or FSMs)

8

Informal Definition

0

1

1

q 1

0

q 2

q3 0,1

M1 accepts • all input strings that end with a 1 • all input strings that have at least one 1 and end with an even number of 0’s • no other strings

CS051

Lecture 02: Finite Automata (a.k.a Finite State Machines or FSMs)

9

Formal Definitions

A deterministic finite state machine (DFSM) is a 5-tuple (Q, Σ, δ, q0 , F ), where • Q is a finite set called the states, • Σ is a finite set called the alphabet, • δ : Q × Σ → Q is the transition function, • q0 ∈ Q is the start state, and • F ⊆ Q is the set of accept states.

CS051

Lecture 02: Finite Automata (a.k.a Finite State Machines or FSMs)

10

Back to M1

0

1

1

0

q 2

q1

q3 0,1

M1 = (Q, Σ, δ, q1 , F ) where • Q = {q1 , q2 , q3 }, • Σ = {0, 1},

• δ is

0

1

q1

q1

q2

q2

q3

q2

q3

q2

q2

• q1 is the start state, and • F = {q2 }.

CS051

Lecture 02: Finite Automata (a.k.a Finite State Machines or FSMs)

11

Languages

Definition The language of machine M is the set of strings A that M accepts. L(M ) = A

Note that • M may accept many strings, but • M accepts only one language Question: What language does M accept if it accepts no strings? Definition: A language is regular if some deterministic finite state machine accepts it.

CS051

Lecture 02: Finite Automata (a.k.a Finite State Machines or FSMs)

12

Formal Model of Computation

Let • M = (Q, Σ, δ, q0 , F ) be a DFSM, and • w = w1 w2 · · · wn be a string over Σ. M accepts w if a sequence of states r0 , . . . , rn exists in Q such that • r0 = q 0 • δ(ri , wi+1 ) = ri+1 , 0 ≤ i < n • rn ∈ F

CS051

Lecture 02: Finite Automata (a.k.a Finite State Machines or FSMs)

13

Classroom Exercises

Create FSMs that do the following: • accepts a string of a’s and b’s if and only if it contains a substring of 0 or more a’s followed by a substring of 0 or more b’s. (Recommended technique: just plow ahead) • accepts a string of 0’s and 1’s if and only if the second to last number is a 1. (Recommended technique: think about what the FSM needs to “remember” and create a state for each memory situation.)

CS051

Lecture 02: Finite Automata (a.k.a Finite State Machines or FSMs)

14