# CS代考 Deterministic Finite Automata – cscodehelp代写

Deterministic Finite Automata

COMP1600 / COMP6260

Australian National University

Semester 2, 2020

The Story So Far …

Logic.

language and proofs to speak about systems precisely useful to express properties and do proofs

Functional Programs

establish properties of functional programs main tool: (structural) induction

Imperative Programs.

again: focus on properties of programs main tool: Hoare Logic

Q. Is there a general notion of computation? That encompasses both?

1/42

First Shot: Your Laptop

Abstract Characteristics.

can do computation

has memory – a finite amount has (lots of) internal states

2/42

From Laptops to Formal Models

Concrete (your laptop) realistic (it exists!)

complex

hard to analyse

Abstract (mathematical model) exists only as a model simple

easy to analyse

Q. What is a “good” simple model of computation?

should match what really exists (possibly by a long shot) should be conceptually simple

3/42

First Answer: Finite State Automata

Basic Components.

internal states – finitely many

state transitions – triggered by reading input simplifying assumption: just one output: yes/no

Data.

basic input: strings (what you type in, text/xml file) characters: drawn from finite set (alphabet)

4/42

Example: Java Identifiers

From Oracle’s Java Language Specification.

An identifier is a sequence of one or more characters. The first character must be a valid first character (letter, $, ) in an identifier of the Java programming language, hereafter in this chapter called simply “Java”. Each subsequent character in the sequence must be a valid nonfirst character (letter, digit, $, ) in a Java identifier.

Graphical Specification

Identifier $ _

Letter

Letter

Digit

$ _

Q. Can you “see” a machine that recognises Java identifiers?

5/42

Java Identifiers

Example: Main Components

Letter Identifier $

_

Letter

Digit $ _

Data.

drawn form a finite alphabet (unicode, or ASCII)

Control.

“yes” if I can get from the left to the right, “no” otherwise have states after taking a transition (implicit in diagram)

Computational Problem with yes/no answer:

it a given sequence of characters a valid Java identifier?

6/42

Preview.

Next two weeks. Finite Automata

start with simplest model: finite automata relate to regular languages, non-determinism conclusion: finite automata “too simple”

The week after. Pushdown automata

like finite automata, but some more memory

useful for e.g. specifying syntax of programming languages still “too simple” for general computation

Then. Turing machines

The most widely accepted model of computation

infinite memory

idea: buy another hard disk whenever your computation runs out of memory

limits of what can be computed

7/42

Finite State Automata: First Example

The simplest useful abstraction of a “computing machine” consists of: A fixed, finite set of states

A transition relation over the states

Example: a traffic light FSA has 3 states:

-G R

G names state in which light is green. Y names state in which light is yellow. R names state in which light is red.

@

R@

Y

System designs are often in terms of state machines.

8/42

Second Example: Vending Machine

Operation

accept 10c and 20c coins

delivers if it has received at least 40c and selection is made

– 0c – 20c – 40c

select

20 20

select

10 10 10

R@ 10 @R 10 @R

@ @ @

10c 20 -30c 20 -50c

Note.

transitions are labelled

new ingredient: final states (doubly circled)

Computation. Sequences of actions (labels) from initial to final state.

9/42

Language Examples

Main Idea.

input: a string over a fixed character set operation: transitions labelled with characters output: yes if in final state after reading the input

More Generally.

Setup: Fix a finite set of characters (an alphabet)

Problem: A set of strings (called language) that are “valid” or “good” Task: decide computationally which strings are “good”

Example Languages.

1. A finite set.

2. Palindromes consisting of bits (0,1):

{0, 1, 00, 11, 010, 101, 000, 111, 0110, …} Languages in this sense are called formal languages.

{a, aa, ab, aaa, aab, aba, abb}

10/42

Terminology

Alphabet.

A finite set (of symbols). Usually denoted by Σ.

Strings over an alphabet Σ

finite sequence of characters (elements of Σ), can be the empty

sequence. E.g. for Σ = {a, b, c}, ababc is a string over Σ. Languages over alphabet Σ

are just sets of strings over Σ.

Sentences of the language

just another name for the elements (strings) of the language.

Notation:

Σ∗ is the set of all strings over Σ.

Therefore, every language with alphabet Σ is some subset of Σ∗.

11/42

Automata

First Model of Computation. Deterministic Finite Automata solve computational problem: given string s, is s accepted?

Basic Ingredients. (see e.g. traffic light and vending machine example) The alphabet of a DFA is a finite set of input tokens that an

automaton acts on.

a DFA consists of a finite set of states (a primitive notion)

One of the states is the initial state — where the automaton starts At least one of the states is a final state

A transition function (next state function):

State×Token → State

12/42

Recurring Theme

Diagrammatic Notation.

useful for humans

e.g. the transition diagram of the vending machine

Mathematical Notation.

useful for formal manipulation (e.g. proving theorems) useful for computer implementation

Glue between Diagrams and Maths

both notions convey precisely the same information crucial: being able to switch back and forth!

13/42

Formal Definition of DFA

A Deterministic Finite State Automaton (DFA) consists of five parts: A = (Σ,S,s0,F,N)

an input alphabet Σ, the set of tokens

a set of states S

an “initial” state s0 ∈ S (we start here)

a set of “final” states F ⊆ S (we hope to finish in one of these) atransitionfunction N:S×Σ → S

Aside. Having a transition function is what makes the automaton deterministic.

14/42

Finite State Automata as String Acceptors

Idea. A finite state automaton

works on strings over an alphabet Σ

determines which strings in Σ are “good” (accepted) and which strings are “bad” (rejected)

Acceptance Informally. Let A = (Σ,S,s0,F,N) be a DFA. Then A accepts the string w = a1a2 . . . an if there is a sequence of states

a1 a2 an−1 an

s0 −→s1 −→…−→sn−1 −→sn

a where s0 is the starting state, sn ∈ F is an accepting state, and s −→ t if

δ(s,a) = t.

Informally. Run the automaton from the starting state, move states according to the individual letters of the word, and accept if you end up in a final state.

15/42

Example 1

As a diagram.

1

– S0 S2

0

S 1 0

Alphabet – {0,1}

States – {S0,S1,S2}

Initial state – S0

Final states – {S2}

Transition function (as a table) –

In Mathematical Notation.

1 @ 10 6

R@

01

S0 S1 S0 S1 S1 S2 S2 S1 S0

Q1. Which strings are accepted by this automaton? Q2. What changes if we re-name the states?

16/42

Example 1, ctd

Recall. N : S × Σ → S is the transition function. 01

S0 S1 S0 S1 S1 S2 S2 S1 S0

Single Steps of the automaton

N(S0,0) is the state that the automation transitions to from state S0

reading letter 0.

Here: N(S0,0) = S1.

Multiple Steps of the automaton

N(N(S0,0), 1) is the state of the automation when starting in S0 and

reading first 0, then 1. Here: N(N(S0, 0), 1) = S2.

17/42

Example 2

b a,b,c abc – U – V

→U Z V Y

@ b ⊙V V V V

? a,b,cR@ c

@ YZVY

-Za Y ⊙ZZZZ

(the table carries the same information as the diagram) Q. What is the language of this automaton?

18/42

Eventual State Function

Revisit example 1:

1

– S0 S2

0

1 @ 10 6

@R

S 1 0

Input 0101 takes the DFA from S0 to S2, Input 1011 takes the DFA from S1 to S0, etc

A complete list of such possibilities is a function from a given state and a string to an ‘eventual state.’

This is the idea of Eventual State Function.

19/42

Eventual State Function — Definition

Definition. Let A be a DFA with states S, alphabet Σ, and transition function N.

The eventual state function for A is of type N∗ : S × Σ∗ → S

and is defined inductively by:

N∗(s,ε) = s (N1) N∗(s,xα) = N∗(N(s,x),α) (N2)

Or in Haskell, where strings are lists of elements of type Sigma

% n :: State -> Sigma -> State — given

nstar :: State -> [Sigma] -> State

nstar s [] = s

nstar s (a:as) = nstar (n s a) as

Informally. N∗(s,w) is the state A reached by starting in state s and reading string w.

20/42

An Important (but Unsurprising) Theorem about N∗

Theorem. For all states s ∈ S and for all strings α, β ∈ Σ∗ N∗(s,αβ) = N∗(N∗(s,α),β)

Proof by induction on the length of α. Base case: α = ε

LHS = N∗(s, εβ) = N∗(s, β) RHS = N∗(N∗(s, ε), β)

= N∗(s,β) = LHS

(by (N1))

21/42

Proof ctd: Step case:

Step Case. Show that N∗(s, (xα)β) = N∗(N∗(s, xα), β)

LHS = N∗(s, (xα)β) = N∗(s,x(αβ))

= N∗(N(s,x),αβ)

= N∗(N∗(N(s, x), α), β)

RHS = N∗(N∗(s, xα), β)

= N∗(N∗(N(s, x), α), β)

Corollary — when β is a single token

N∗(s,αy) = N(N∗(s,α),y)

(by (N2)) (by IH)

(by (N2))

22/42

Example

1

– S0 S2

0

1 @ 10 6

@R

S 1 0

N∗(S1, 1011) = N∗(N(S1, 1), 011) = N∗(S2,011)

= N∗(S1,11) = N∗(S2,1) = N∗(S0,ε) = S0

23/42

Language of an Automaton, Revisited

Acceptance, with eventual states. Let A = (Σ,S,s0,F,N) be an DFA and w be a string in Σ∗.

Then w is accepted by A if

N∗(s0,w) ∈ F

Q1. How does this compare with the earlier notion of acceptance? Q2. How can we prove that both are equivalent?

24/42

Example 1 again

1

– S0 S2

0

1 @ 10 A: 6

1

S 1 0

Q. Which strings are accepted?

e.g. 0011101 takes the machine from state S0 through states S1, S1,

S2, S0, S0, S1 to S2 (a final state).

N∗(S0, 0011101) = N∗(S1, 011101) = N∗(S1, 11101) =

…N∗(S1,1) = S2

others: 01, 001, 101, 0001, 0101, 00101101 . . .

25/42

Example 1 (ctd.)

1

– S0 S2

0

1 @ 10 A: 6

S 1 0

Accepted Strings.

01, 001, 101, 0001, 0101, 00101101 . . .

Strings that are not accepted.

ε, 0, 1, 00, 10, 11, 100 . . .

Q. What do the accepted strings have in common? How do we justify this?

1

26/42

Proving an Acceptance Predicate — in General

Our Claim. The automaton A accepts precisely the strings that are elements of the language L = {w ∈ Σ∗ | P(w)}.

(P is sometimes called an acceptance predicate.)

Proof Obligations.

1. Show that any string satisfying P is accepted by A. 2. Show any string accepted by A satisfies P.

27/42

Proving an Acceptance Predicate for A1

Proof obligation 1:

If a string ends in 01, then it is accepted by A1. That is: For all α ∈ Σ∗, N∗(S0,α01) ∈ F

Proof obligation 2:

If a string is accepted by A1, then it ends in 01. That is: Forallw∈Σ∗,ifN∗(S0,w)∈Fthen ∃α∈Σ∗. w=α01

28/42

Part 1: ∀α ∈ Σ∗, N∗(S0, α01) ∈ F Lemma:

Proof by cases:

∀s ∈ S. N∗(s,01) = S2

N∗(S0, 01) = N∗(S1, 1) = S2 N∗(S1, 01) = N∗(S1, 1) = S2 N∗(S2, 01) = N∗(S1, 1) = S2

So, by the “append” theorem above,

N∗(S0, α01) = N∗(N∗(S0, α), 01) = S2

29/42

Part2: N∗(S0,w)=S2 =⇒ ∃α. w=α01 Proof. Suppose N∗(S0,αxy) = S2.

By corollary to append-theorem (case of single token): N(N∗(S0, αx), y) = S2

By the definition of N, y must be 1 and N∗(S0,αx) must be S1. Similarly,

N(N∗(S0, α), x) = S1 and x is 0, again by the definition of N.

30/42

Another Example

What language does this DFA accept?

SOB:

– S0 – S1 – S2 1 1 1

0 0 0 666

31/42

Answer for SOB

SOB accepts the language of bitstrings containing exactly one 1-bit. Proof obligations:

Show that if a bitstring contains exactly one 1-bit then it is accepted by SOB.

Show that if a string is accepted by SOB it contains exactly one

1-bit.

SOB:

– S0 – S1 – S2 1 1 1

0 0 0

666

32/42

Mapping to Mathematics

Expressed mathematically, the main conclusion is L(SOB)={w∈Σ∗ |w=0n10m}

The two subgoals are

1. Ifw=0n10m thenN∗(S0,w)=S1 2. If N∗(S0,w) = S1 then w = 0n10m.

For this DFA the phrase “w is accepted by SOB” is captured by the expression N∗(S0,w)=S1.

33/42

Proving these subgoals

The first subgoal follows immediately from the following two lemmas, which are easily proved by induction:

Lemma 1: ∀n ≥ 0. N∗(S0, 0n) = S0 Lemma 2: ∀n ≥ 0. N∗(S1, 0n) = S1

Therefore

N∗(S0, 0n10m)

=N∗(N∗(S0, 0n), 10m) =N∗(S0, 10m) =N∗(N(S0, 1), 0m) =N∗(S1, 0m)

(by apppend Theorem) (by Lemma 1) (by def. N∗) (by def. N) (by Lemma 2)

∀w: N∗(S0,w)=S1 =⇒ ∃n,m≥0.w=0n10m can be proved in a similar fashion to Example 1 on earlier slides.

=S1

The second subgoal, stated more formally as

34 / 42

Limitations of FSAs

Q. Is an FSA a “good” model of computation?

Suppose we have a program P that always terminates

and outputs “yes” or “no” for every input string

Is there an FSA that accepts precisely the strings for which P says “yes”?

Technical Analysis. Properties of languages accepted by a DFA.

A very important example: L = { anbn | n ∈ N}

L = {ε,ab,aabb,aaabbb,a4b4,a5b5,…}

Claim. There is no FSA that recognises this language.

(because an FSA’s memory is limited.)

Q. Given the claim above, are FSA’s realistic models of computation?

35/42

Proof of Claim

Proof by contradiction.

Suppose A is an FSA that accepts L. That is L = L(A). Then each of the following are states of A:

N∗(S0,a), N∗(S0,a2), N∗(S0,a3) …

But A only has finitely many states, so some state must repeat:

There are distinct i and j such that N∗(S0, ai ) = N∗(S0, aj ). that is, the automaton cannot tell ai and aj apart.

36/42

Proof by contradiction (ctd)

Since ai bi is accepted, we know

N∗(S0,aibi) ∈ F

By the append theorem

N∗(N∗(S0,ai),bi) = N∗(S0,aibi) ∈ F

Now, since N∗(S0, ai ) = N∗(S0, aj )

N∗(N∗(S0,aj),bi) = N∗(S0,ajbi) ∈ F

So ajbi is accepted by A but ajbi is not in L, contradicting the initial assumption.

37/42

Pigeon-Hole Principle

The proof used the pigeon-hole principle:

No function from one set to a smaller finite set can be one-to-one.

••

••

(Finiteness is not really necessary — no function from one set to another with smaller cardinality can be one-to-one.)

“You cannot fit n + 1 pigeons into n holes”

••

•

38/42

Equivalence of Automata

Two automata are said to be equivalent if they accept the same language.

?0 ?0

S 1 S0 S -0-1 -0

Example:

A4: 6 1 A5: 61 11

? ?

000 -S31 S2 S1

Q. Can FSAs be simplified? is there an equivalent FSA with fewer states?

39/42

Equivalence of States

Two states Sj and Sk of an FSA are equivalent if, for all input strings w N∗(Sj,w) ∈ F if and only if N∗(Sk,w) ∈ F

Example. In A4, S2 is equivalent to S0 and S1 is equivalent to S3.

?0

S 1 S0 -0 -1

A4: 6 1 1

?

00

– S 3 1 S 2

40/42

Elimination of Equivalent States

Assumptions.

A = (Σ,S,S0,F,N) is an FSA

Sk and Sj be equivalent

Sk ̸= S0 (don’t eliminate the initial state!)

Elimination of Sk from A: new automaton A′ = (Σ,S′,S0,F′,N′) S′ is S without Sk

F′ is F without Sk

N′(s,w) = (if N(s,w) = Sk then Sj else N(s,w))

41/42

Example

Since S2 ≡ S0 in A4 , let’s eliminate S2 . Newsetofstatesis {S0,S1,S3}

New set of final states is {S0}

New transition function is:

?0

1-0

– S0 S1 0 1

1

A6: 61 S0S0S1 S1 S1 S0

0 SSS -S3 330

42/42