FINITE STATE AUTOMATA

0.5 setgray0 0.5 setgray1

Finite State Automata Automata: Theory and Practice Paritosh K. Pandya (TIFR, Mumbai, India) Unversity of Trento 10-24 May 2005

Trento’2005 – p. 1/4

Finite Word Langauges Alphabet Σ is collection of symbols (letters). E.g. Σ = {a, b}. Finite word is a finite sequence of letters. E.g. aabb. Set of all finite words is denoted by Σ∗ . Langauge U is a set of words, i.e. U ⊆ Σ∗ . Example: (a) Words over Σ = {a, b} with equal number of a and b. E.g. aabb or abba. Language recognition problem: To determine whether a word belongs to a language. Most computational problems can be encoded as language recognition problem. Automata are computational devices to solve langauge recognition problems.

Trento’2005 – p. 2/4

Finite State Automata Basic model of computational systems with finite memory. Widely applicable Embedded System Controllers. Languages: Esterel, Lustre, Verilog, SMV. Synchronous Circuits. Regular Expression Pattern Matching Grep, Lex, Perl, Awk, Emacs. Protocols Network Protocols Architecture: Bus, Cache Coherence ... Mobile Telephony. Good decision procedures

Trento’2005 – p. 3/4

Topics DFA, NFA and Equivalence Closure Properties and Decision Problems Regular Expressions and McNaughton Yamada Lemma Homomorphisms DFA minization Pumping Lemma Myhill Nerode Theorem Bisimulation and collapsing nondeterministic automta Textbook: Dexter Kozen, Automata and Computability. Springer, 1997.

Trento’2005 – p. 4/4

Notation a, b ∈ Σ finite alphabet. u, v, w ∈ Σ∗ finite words. ǫ empty word. u.v catenation. ui = u.u. .u repeated i-times. U, V ⊆ Σ∗ Finite word languages.

For a set S we use 2S to denote all its subsets. def 2S = {X | X ⊆ S}.

Trento’2005 – p. 5/4

Deterministic Finite State Automaton Example: DFA A1 over Σ = {a, b}. b

a s1

b s2

a

Trento’2005 – p. 6/4


a s1

b s2

a

The run of A1 over the word abba is : a b b a s1 −→ s1 −→ s2 −→ s2 −→ s1 . For a given word the run is unique.

Trento’2005 – p. 6/4


a s1

b s2

a

The run of A1 over the word abba is : a b b a s1 −→ s1 −→ s2 −→ s2 −→ s1 . For a given word the run is unique. Recognises words which do not end in b.

Trento’2005 – p. 6/4

DFA Definition DFA is (Q, Σ, δ, I, F ) Q Finite set of states. Σ is the finite alphabet. q0 ∈ Q the initial states. F ⊆ Q set of final states. δ : Q × Σ → Q, transition function (total). a

Notation: We use q −→ q ′ to denote δ(q, a) = q ′ . A run of DFA A on u = a0 , a1 , . . . , an−1 is a sequence of ai states q0 , q1 , . . . , qn s.t. qi −→ qi+1 for 0 ≤ i < n. For a given word w the DFA has a unique run. A run accepting if last state qn ∈ F .

Trento’2005 – p. 7/4

Regular Langauges Language accepted by A L(A) = {u ∈ Σ∗ | A has an accepting run on u}. A langauge accepted by a DFA is called a regular language.

Trento’2005 – p. 8/4

Regular Langauges Language accepted by A L(A) = {u ∈ Σ∗ | A has an accepting run on u}. A langauge accepted by a DFA is called a regular language. ˆ u) inductively over u ∈ Σ∗ . Define δ(q, ˆ ǫ) = q, ˆ ua) = δ(δ(q, ˆ u), a). δ(q, δ(q, def S ˆ u). ˆ δ(q, For X ⊆ Q define δ(X, u) = q∈X

Trento’2005 – p. 8/4

Nondeterministic FSA NFA A2

. a,b

b s1

b

s2

Trento’2005 – p. 9/4

Nondeterministic FSA NFA A2

. a,b

b s1

b

s2

A run of A2 over the word abbb is: b b b a s1 −→ s1 −→ s1 −→ s2 −→ s2 . Another run over the same word abbb is: b b b a s1 −→ s1 −→ s1 −→ s1 −→ s1 . A2 has no accepting run over the word aba as: a

b

a

s1 −→ s1 −→ s2 −→ ×

NFA can have 0, 1 or more than one runs on a given word.

Trento’2005 – p. 9/4

Nondeterministic FSA NFA A2 recognises words which end in b. a,b

b s1

b

s2

A run of A2 over the word abbb is: b b b a s1 −→ s1 −→ s1 −→ s2 −→ s2 . Another run over the same word abbb is: b b b a s1 −→ s1 −→ s1 −→ s1 −→ s1 . A2 has no accepting run over the word aba as: a

b

a

s1 −→ s1 −→ s2 −→ ×

NFA can have 0, 1 or more than one runs on a given word.

Trento’2005 – p. 9/4

NFA Definition Nodeterministic Finite State Automaton: NFA is (Q, Σ, δ, I, F ) Q Finite set of states. I ⊆ Q set of initial states. F ⊆ Q set of final states. δ ⊆ Q × Σ × Q transition relation (edges). a We use q −→ q ′ to denote (q, a, q ′ ) ∈ δ . Alternate Definition of δ δ : Q × Σ → 2Q . Exercise: Given that |Q| = n and |Σ| = k , give the number of syntactically distinct NFAs.

Trento’2005 – p. 10/4

NFA Runs A run of NFA A on u = a0 , a1 , . . . , an−1 is a sequence of ai states q0 , q1 , . . . , qn s.t. qi −→ qi+1 for 0 ≤ i < n and q0 ∈ I . For a given word w the NFA can have many runs. A run accepting if last state qn ∈ F . Language accepted by A is L(A) = {u ∈ Σ∗ | A has an accepting run on u}.

Trento’2005 – p. 11/4

NFA Runs A run of NFA A on u = a0 , a1 , . . . , an−1 is a sequence of ai states q0 , q1 , . . . , qn s.t. qi −→ qi+1 for 0 ≤ i < n and q0 ∈ I . For a given word w the NFA can have many runs. A run accepting if last state qn ∈ F . Language accepted by A is L(A) = {u ∈ Σ∗ | A has an accepting run on u}. ˆ w) inductively on w as follows. Define δ(S, ˆ a) = ∪s∈S δ(s, a) δ(S, ˆ ǫ) = S, ˆ wa) = δ( ˆ δ(S, ˆ w), a). δ(S, δ(S, ˆ x) ∩ F 6= ∅ Claim x ∈ L(A) ⇔ δ(I,

Trento’2005 – p. 11/4

Subset Construction Theorem (determinisation) Given NFA A = (Q, Σ, δ, I, F ) we can construct a DFA A′ s.t. L(A) = L(A′ ).

Trento’2005 – p. 12/4

Subset Construction Theorem (determinisation) Given NFA A = (Q, Σ, δ, I, F ) we can construct a DFA A′ s.t. L(A) = L(A′ ). Subset construction: 0,1 p

r

q 1

0,1

ˆ w) the set of states reached after word w . We Consider δ(I, define ∆(S, a). 0 1 → {p} {p} {p, q} {p, q} {p, r} {p, q, r} {p, r} {p} {p, q} {p, q, r} {p, r} {p, q, r}

Trento’2005 – p. 12/4

Subset Construction (cont) Let A′ = (2Q , Σ, ∆, I, F ′ ) where ∆(S, a) = {q | q ∈ δ(p, a) ∧ p ∈ S} F ′ = {S ∈ 2Q | S ∩ F 6= ∅}. Claim: L(A) = L(A′ ). ˆ w) = ∆(S, ˆ w). Proof Method: Show that δ(S, Complexity |A′ | ≤ 2|A| . Lower Bound Example: Consider NFA recognising words over {0, 1} such that the n-th last symbol is 1. Claim: Equivalent DFA will have at least 2n states. (Home Exercise: Prove this.)

Trento’2005 – p. 13/4

Closure Properties Theorem (boolean closure) Given NFA A1 , A2 over Σ we can construct NFA A over Σ s.t. L(A) = L(A1 ) (Complement). Size: |A| = 2|A1 | . L(A) = L(A1 ) ∪ L(A2 ) (union). Size: |A| = |A1 | + |A2 |. L(A) = L(A1 ) ∩ L(A2 ) (intersection). |A| = |A1 | × |A2 |.

Trento’2005 – p. 14/4

Synchronous Product: Example a

b

s0

t0 b

b

b

a a a

b

A1 recognises words with even number of b.

A2 recognises words with number of a a mod 3 = 0. The Product Automaton A1 × A2 with F = {s0 , t0 }. t2

s1

s0 t0 a a a s t 0 1 s0 t2 b b

b b

t1

s1 t0 a a a s t 1 1 s1 t2 b b

Trento’2005 – p. 15/4

Synchronous Product Construction Let A1 = (Q1 , Σ, δ1 , I1 , F1 ) and A2 = (Q2 , Σ, δ2 , I2 , F2 ). Then, A1 × A2 = (Q, Σ, δ, I, F ) where Q = Q1 × Q2 . F = F 1 × F2 . a

< p, q >−→<

p′ , q ′

I = I1 × I2 . a

> iff p −→

p′

a

and q −→ q ′ .

Theorem L(A1 × A2 ) = L(A1 ) ∩ L(A2 ). Semantics of many concurrent systems E.g. Esterel, Statecharts, Lustre, Synchronous circuits, SMV.

Trento’2005 – p. 16/4

Synchronised Product Construction Let A1 = (Q1 , Σ1 , δ1 , I1 , F1 ) and A2 = (Q2 , Σ2 , δ2 , I2 , F2 ). Then, A1 kA2 = (Q, Σ, δ, I, F ) where Q = Q1 × Q2 . I = I1 × I2 . a

p′ , q ′

a

p′ , q

a

p, q ′

< p, q >−→< a q −→ q ′ . < p, q >−→< < p, q >−→<

Σ = Σ1 ∪ Σ2 . F = F 1 × F2 . a

> if a ∈ Σ1 ∩ Σ2 and p −→ p′ and a

> if a ∈ Σ1 , a 6∈ Σ2 and p −→ p′ . a

> if a 6∈ Σ1 , a ∈ Σ2 and q −→ q ′ .

Trento’2005 – p. 17/4

Asynchronous Product Construction Let A1 = (Q1 , Σ1 , δ1 , I1 , F1 ) and A2 = (Q2 , Σ2 , δ2 , I2 , F2 ). Then, A1 kA A2 = (Q, Σ, δ, I, F ) where Q = Q1 × Q2 . I = I1 × I2 . a

p′ , q

a

p, q ′

< p, q >−→< < p, q >−→<

Σ = Σ1 ∪ Σ2 . F = F 1 × F2 . a

> if a ∈ Σ1 and p −→ p′ . a

> if a ∈ Σ2 and q −→ q ′ .

Trento’2005 – p. 18/4

Decision Problems Theorem (Emptiness) Given NFA A we can decide whether L(A) = ∅. Method Forward/Backward Reachability in Automaton graph using say Depth First Search. Complexity is O(|Q| + |δ|). In practice, symbolic techniques are used and often more effective. Theorem (Language Containment) Given NFA A1 and A2 we can decide whether L(A1 ) ⊆ L(A2 ). Method: L(A1 ) ⊆ L(A2 ) iff L(A1 ) ∩ L(A2 ) = ∅. Complexity is O(|A1 | × 2|A2 | ).

Trento’2005 – p. 19/4

Kleene Closure Let U, V ⊆ Σ∗ . def

(Catenation) Let U · V = {x · y | x ∈ U ∧ y ∈ V }. (Iteration) Let

def i U =

{x1 · x2 · . . . · xi | xk ∈ U, 1 ≤ k < i}.

By convention

def 0 U =

{ǫ}.

(Kleene Closure) Let

def ∗ U =

S

0≤i

U i.

Theorem Regular langauges are closed under the operations U · V and U ∪ V and U ∗ . Proof method: Using ǫ-NFA.

Trento’2005 – p. 20/4

Regular Expressions Syntax: ∅ | ǫ | a | reg1 .reg 2 | reg1 + reg 2 | reg ∗ .

Trento’2005 – p. 21/4

Regular Expressions Syntax: ∅ | ǫ | a | reg1 .reg 2 | reg1 + reg 2 | reg ∗ . Language L(reg) is defined inductively: L(∅) = ∅, L(a) = {a}, L(ǫ) = {ǫ}. L(re1 · re2 ) = L(re1 ) · L(re2 ), L(re1 + re2 ) = L(re1 ) ∪ L(re2 ), L(re∗ ) = (L(re1 ))∗

Example: a∗ .(b + bb).a∗ . Words over a, b having either 1 b or 2 consecutive b.

Trento’2005 – p. 21/4

Regular Expressions Syntax: ∅ | ǫ | a | reg1 .reg 2 | reg1 + reg 2 | reg ∗ . Language L(reg) is defined inductively: L(∅) = ∅, L(a) = {a}, L(ǫ) = {ǫ}. L(re1 · re2 ) = L(re1 ) · L(re2 ), L(re1 + re2 ) = L(re1 ) ∪ L(re2 ), L(re∗ ) = (L(re1 ))∗

Example: a∗ .(b + bb).a∗ . Words over a, b having either 1 b or 2 consecutive b. Equivalence of RegExp and FSA (McNaughton, Yamada) Theorem: For every regular expression reg we can construct a language equivalent ǫ-NFA of size O(|reg|).

Trento’2005 – p. 21/4

Automata to RegExp Theorem: For every NFA A = (Q, Σ, δ, I, F ) we can construct a langauge equivalent regular expression reg(A).

Trento’2005 – p. 22/4

Automata to RegExp Theorem: For every NFA A = (Q, Σ, δ, I, F ) we can construct a langauge equivalent regular expression reg(A). X for X ⊆ Q and Construction Define regular expression αp,q p, q ∈ Q. This denotes set of words w such that A has a run on w from p to q where all intermediate states are from X .

Trento’2005 – p. 22/4

Automata to RegExp Theorem: For every NFA A = (Q, Σ, δ, I, F ) we can construct a langauge equivalent regular expression reg(A). X for X ⊆ Q and Construction Define regular expression αp,q p, q ∈ Q. This denotes set of words w such that A has a run on w from p to q where all intermediate states are from X .

q 1

0 p

Example: q αp,r = 10

0

1 r 0

p,q αp,r = 0∗ · 1 · 0

p,q,r Aim: To compute αp,p

Trento’2005 – p. 22/4

Automata to RegExp (2) X can be recursively defined using the following rules: αp,r ∅ = a1 + . . . + ak αp,r where r ∈ δ(p, ai )

provided p 6= r

Trento’2005 – p. 23/4


provided p 6= r

∅ = a1 + . . . + ak + ǫ αp,p where p ∈ δ(p, ai )

Trento’2005 – p. 23/4


provided p 6= r


For any q ∈ X , X = αp,r

(X−{q}) αp,r

+

(X−{q}) αp,q

(X−{q}) ∗ (X−{q}) · αq,q · αq,r

Trento’2005 – p. 23/4


provided p 6= r


For any q ∈ X , X = αp,r

(X−{q}) αp,r

+

(X−{q}) αp,q

(X−{q}) ∗ (X−{q}) · αq,q · αq,r

The desired regular expression is given as follows: P P Q α p,q . p∈I q∈F

Trento’2005 – p. 23/4

Example q 1

0

0

1 p

r 0

p,q,r Compute αp,p as p,q,r p,r p,r p,r ∗ p,r αp,p . = αp,p + αp,q · (αq,q ) · αq,p

It is easy to see that p,r p,r αp,p = 0∗ , αp,q = 0∗ · 1 p,r p,r αq,p = 00(0∗ ), αq,q = ǫ + 01 + 00(0∗ )1 p,q,r Hence αp,p = 0∗ + 0∗ 1 · (ǫ + 01 + 00(0∗ )1)∗ · 00(0∗ )

Trento’2005 – p. 24/4

Kleene Algebra Axiomatizing equivalence of regular expression. Not covered in this course. (See Kozen.)

Trento’2005 – p. 25/4

Homomorphism Homomorphism is a map h : Σ∗ → Γ∗ with the property ∀u, v ∈ Σ∗ . h(u · v) = h(u) · h(v). Consequences: h(ǫ) = ǫ.

Giving h(a) for a ∈ Σ uniquely determines h.

Trento’2005 – p. 26/4


Giving h(a) for a ∈ Σ uniquely determines h. Theorem If h : Σ∗ → Γ∗ is a homomorphism and B ⊆ Γ∗ is regular then h−1 (B) = {x ∈ Σ∗ | h(x) ∈ B} is also regular.

Trento’2005 – p. 26/4


Giving h(a) for a ∈ Σ uniquely determines h. Theorem If h : Σ∗ → Γ∗ is a homomorphism and B ⊆ Γ∗ is regular then h−1 (B) = {x ∈ Σ∗ | h(x) ∈ B} is also regular. Proof method: Given DFA BB = (Q, Γ, δ, q0 , F ) for B construct DFA AA for h−1 (B) as follows. def ˆ h(a)). AA = (Q, Σ, δ ′ , q0 , F ) with δ ′ (q, a) = δ(q,

Trento’2005 – p. 26/4

Homomorphism (2) Theorem If h : Σ∗ → Γ∗ is a homomorphism and A ⊆ Σ∗ is regular then h(A) = {h(x) | x ∈ A} is also regular.

Trento’2005 – p. 27/4

Homomorphism (2) Theorem If h : Σ∗ → Γ∗ is a homomorphism and A ⊆ Σ∗ is regular then h(A) = {h(x) | x ∈ A} is also regular. Proof method: Given regular epxression re for A, obtain h(re) by substituting every letter a by h(a). Then L(h(re)) = h(A).

Trento’2005 – p. 27/4

Homomorphism (2) Theorem If h : Σ∗ → Γ∗ is a homomorphism and A ⊆ Σ∗ is regular then h(A) = {h(x) | x ∈ A} is also regular. Proof method: Given regular epxression re for A, obtain h(re) by substituting every letter a by h(a). Then L(h(re)) = h(A). Theorem (projection) Given N F A(A1 ) over Σ and surjection h : Σ → Γ, we can construct N F A(A2 ) over Γ s.t. L(A2 ) = h(L(A1 )). Proof Method: Substitute label a by h(a) in each transition of A1 to get A2 . Note that this can make DFA into NFA. We have |A2 | = |A1 |.

Trento’2005 – p. 27/4

Homomorphism (2) Theorem If h : Σ∗ → Γ∗ is a homomorphism and A ⊆ Σ∗ is regular then h(A) = {h(x) | x ∈ A} is also regular. Proof method: Given regular epxression re for A, obtain h(re) by substituting every letter a by h(a). Then L(h(re)) = h(A). Theorem (projection) Given N F A(A1 ) over Σ and surjection h : Σ → Γ, we can construct N F A(A2 ) over Γ s.t. L(A2 ) = h(L(A1 )). Proof Method: Substitute label a by h(a) in each transition of A1 to get A2 . Note that this can make DFA into NFA. We have |A2 | = |A1 |. Example: Given regular A over {0, 1} the language hamming3 (A) is regular.

Trento’2005 – p. 27/4

DFA Minimization a

1

a b

3

a,b 5

0 b

2

b a

4

a,b

a,b

Trento’2005 – p. 28/4

DFA Minimization a

1

a b

3

a,b 5

0 b

2

b a

4

a,b

a,b

Trento’2005 – p. 28/4

DFA Minimization a

1

a b

3

a,b 5

0 b

p≈q

def

=

2

b a

4

a,b

a,b

ˆ x) ∈ F ⇔ δ(q, ˆ x) ∈ F ) ∀x ∈ Σ∗ . (δ(p,

Trento’2005 – p. 28/4

DFA Minimization 1

a

a b

3

a,b 5

0 2

b

p≈q

def

=

b a

4

a,b

a,b

ˆ x) ∈ F ⇔ δ(q, ˆ x) ∈ F ) ∀x ∈ Σ∗ . (δ(p,

Equivalent Automaton

6

a,b

a,b 7

8

a,b

Trento’2005 – p. 28/4

DFA Minimization (2) p≈q

def

=

ˆ x) ∈ F ⇔ δ(q, ˆ x) ∈ F ) ∀x ∈ Σ∗ . (δ(p,

Trento’2005 – p. 29/4


def

=

ˆ x) ∈ F ⇔ δ(q, ˆ x) ∈ F ) ∀x ∈ Σ∗ . (δ(p,

Proposition ≈ is an equivalence relation, i.e. (a) ∀p. p ≈ p, (b) ∀p, q. p ≈ q ⇒ q ≈ p (c) ∀p, q, r. p ≈ q ∧ q ≈ r ⇒ p ≈ r (Exercise: Check that above properties are true.)

Trento’2005 – p. 29/4


def

=

ˆ x) ∈ F ⇔ δ(q, ˆ x) ∈ F ) ∀x ∈ Σ∗ . (δ(p,

Proposition ≈ is an equivalence relation, i.e. (a) ∀p. p ≈ p, (b) ∀p, q. p ≈ q ⇒ q ≈ p (c) ∀p, q, r. p ≈ q ∧ q ≈ r ⇒ p ≈ r (Exercise: Check that above properties are true.) ≈ partitions Q into equivalence classes. Let [p] denote the equivalence class of p.

Example The classes are {0}, {1, 2} and {3, 4, 5}.

Trento’2005 – p. 29/4

Quotient Automaton Given DFA A = (Q, Σ, δ, [q0 ], F ) and ≈ as before, the def

Quotient automaton is A/ ≈ = (Q′ , Σ, δ ′ , [q0 ], F ′ ), where Q′ = {[p] | p ∈ Q} δ ′ ([p], a) = [δ(p, a)] F ′ = {[f ] | f ∈ F }

Trento’2005 – p. 30/4


Quotient automaton is A/ ≈ = (Q′ , Σ, δ ′ , [q0 ], F ′ ), where Q′ = {[p] | p ∈ Q} δ ′ ([p], a) = [δ(p, a)] F ′ = {[f ] | f ∈ F } Well-formedness Theorem(Congruence) p ≈ q ⇒ ∀a ∈ Σ. δ(p, a) ≈ δ(q, a).

Trento’2005 – p. 30/4


Quotient automaton is A/ ≈ = (Q′ , Σ, δ ′ , [q0 ], F ′ ), where Q′ = {[p] | p ∈ Q} δ ′ ([p], a) = [δ(p, a)] F ′ = {[f ] | f ∈ F } Well-formedness Theorem(Congruence) p ≈ q ⇒ ∀a ∈ Σ. δ(p, a) ≈ δ(q, a). Now we can show that quotient automaton recognises the same language. Theorem δˆ′ ([p], w)

=

ˆ w)]. [δ(p,

Corollary L(A/ ≈) = L(A).

Trento’2005 – p. 30/4

Minimization algorithm 1. Make pairs table with (p, q) ∈ Q × Q and p < q . 2. Mark (p, q) if p ∈ F ∧ q ∈ / F or vice versa. 3. Repeat following steps until no change occurs. (a) Pick unmarked state (p, q). (b) If (δ(p, a), δ(q, a)) is marked for some a ∈ Σ then mark (p, q)

Trento’2005 – p. 31/4

Minimization algorithm 1. Make pairs table with (p, q) ∈ Q × Q and p < q . 2. Mark (p, q) if p ∈ F ∧ q ∈ / F or vice versa. 3. Repeat following steps until no change occurs. (a) Pick unmarked state (p, q). (b) If (δ(p, a), δ(q, a)) is marked for some a ∈ Σ then mark (p, q) Termination: In each pass at least one new pair must get marked. ˆ x) ∈ F ∧ δ(q, ˆ x) ∈ Lemma (p, q) is marked iff ∃x ∈ Σ∗ .δ(p, /F or vice versa.

Trento’2005 – p. 31/4

Minimization algorithm 1. Make pairs table with (p, q) ∈ Q × Q and p < q . 2. Mark (p, q) if p ∈ F ∧ q ∈ / F or vice versa. 3. Repeat following steps until no change occurs. (a) Pick unmarked state (p, q). (b) If (δ(p, a), δ(q, a)) is marked for some a ∈ Σ then mark (p, q) Termination: In each pass at least one new pair must get marked. ˆ x) ∈ F ∧ δ(q, ˆ x) ∈ Lemma (p, q) is marked iff ∃x ∈ Σ∗ .δ(p, /F or vice versa. Question: Can there be a DFA smaller than A/ ≈ equivalent to A?

Trento’2005 – p. 31/4

Pumping Lemma Idea: Consider a long word recognized by a DFA with n states. Consider substring y s.t. |y| ≥ n. Some state during y part of the run must repeat. The string between repeating states can be pumped.

Trento’2005 – p. 32/4

Pumping Lemma Idea: Consider a long word recognized by a DFA with n states. Consider substring y s.t. |y| ≥ n. Some state during y part of the run must repeat. The string between repeating states can be pumped. Lemma For every regular language L ∃n > 0 such that ∀ x, y, z with x · y · z ∈ L and |y| ≥ n ∃ u, v, w s.t. y = u · v · w with |v| > 0 and x · u · v i · w · z ∈ L for all 0 ≤ i.

Trento’2005 – p. 32/4

Pumping Lemma Idea: Consider a long word recognized by a DFA with n states. Consider substring y s.t. |y| ≥ n. Some state during y part of the run must repeat. The string between repeating states can be pumped. Lemma For every regular language L ∃n > 0 such that ∀ x, y, z with x · y · z ∈ L and |y| ≥ n ∃ u, v, w s.t. y = u · v · w with |v| > 0 and x · u · v i · w · z ∈ L for all 0 ≤ i. Pumping Lemma is used to prove that some langugages n 2 are not regular. E.g. {a | n ≥ 0}.

Trento’2005 – p. 32/4

Proving non-regularity Game with Demon Demon claims L is regular and chooses n. You choose a string xyz ∈ L with |y| ≥ n. Demon partitions y = uvw with |v| = 6 0. You show that xu(v i )wz ∈ / L for some i for your choice.

Trento’2005 – p. 33/4

Myhill-Nerode Relations Let ≡ be an equivalence relation over Σ∗ . ≡ is right congruent if ∀x, y ∈ Σ∗ , a ∈ Σ we have x≡y ⇒ x·a≡y·a

Trento’2005 – p. 34/4


Let R ⊆ Σ∗ (not necessarily regular). ≡ refines R if ∀x, y ∈ Σ∗ x ≡ y ⇒ (x ∈ R ⇔ y ∈ R)

Trento’2005 – p. 34/4


Let R ⊆ Σ∗ (not necessarily regular). ≡ refines R if ∀x, y ∈ Σ∗ x ≡ y ⇒ (x ∈ R ⇔ y ∈ R) ≡ is of finite index if ≡ partitions the Σ∗ into only finitely many equivalence classes.

Trento’2005 – p. 34/4


Let R ⊆ Σ∗ (not necessarily regular). ≡ refines R if ∀x, y ∈ Σ∗ x ≡ y ⇒ (x ∈ R ⇔ y ∈ R) ≡ is of finite index if ≡ partitions the Σ∗ into only finitely many equivalence classes.

Equivalence relation ≡ is called Myhill-Nerode Relation refining R if it satisfies all the three properties above.

Trento’2005 – p. 34/4

Machine Equivalence Given a DFA A = (Q, Σ, δ, q0 , F ) define the induced equivalence ≡A over Σ∗ as follows: def ˆ 0 , x) = δ(q ˆ 0 , y). x ≡A y = δ(q

Trento’2005 – p. 35/4

Machine Equivalence Given a DFA A = (Q, Σ, δ, q0 , F ) define the induced equivalence ≡A over Σ∗ as follows: def ˆ 0 , x) = δ(q ˆ 0 , y). x ≡A y = δ(q Proposition ≡A is a Myhill-Nerode relation refining L(A). Proof Method Check the following: (a) ≡A is an equivalence relation over Σ∗ . (b) x ≡A y ⇒ ∀a. xa ≡A ya. (c) x ≡A y ⇒ x ∈ L(A) ⇔ y ∈ L(A) (d) ≡A is of finite index.

Trento’2005 – p. 35/4

Machine Equivalence Given a DFA A = (Q, Σ, δ, q0 , F ) define the induced equivalence ≡A over Σ∗ as follows: def ˆ 0 , x) = δ(q ˆ 0 , y). x ≡A y = δ(q Proposition ≡A is a Myhill-Nerode relation refining L(A). Proof Method Check the following: (a) ≡A is an equivalence relation over Σ∗ . (b) x ≡A y ⇒ ∀a. xa ≡A ya. (c) x ≡A y ⇒ x ∈ L(A) ⇔ y ∈ L(A) (d) ≡A is of finite index. Example: We give automaton A and the induced equivalence partitions.

Trento’2005 – p. 35/4

From Equivalence to DFA Let ≡ be Myhill-Nerode refining R. Define DFA def

A≡ = (Q, Σ, δ, q0 , F ) as follows: def

Q = {[x] | x ∈ Σ∗ } def

q0 = [ǫ] def

F = {[x] | x ∈ R} def

δ([x], a]) = [xa]. (Check well-formedness.)

Trento’2005 – p. 36/4

From Equivalence to DFA Let ≡ be Myhill-Nerode refining R. Define DFA def

A≡ = (Q, Σ, δ, q0 , F ) as follows: def

Q = {[x] | x ∈ Σ∗ } def

q0 = [ǫ] def

F = {[x] | x ∈ R} def

δ([x], a]) = [xa]. (Check well-formedness.)

Theorem L(A≡ )

=

R.

ˆ Lemma δ([x], y) = [xy].

Trento’2005 – p. 36/4

Correspondence The ≡A and A≡ are inverses of each other. Theorem ≡A≡

=

≡.

Theorem If A is automaton without unreachable states then A≡A is isomorphic to A.

Trento’2005 – p. 37/4

Language Induced Equivalence An equivalence relation ≡1 refines equivalence relation ≡2 provided x ≡1 y ⇒ x ≡2 y (Set theoretically, ≡1 ⊆≡2 .) Intuitively, ≡1 makes finer partitions than ≡2 .

Trento’2005 – p. 38/4

Language Induced Equivalence An equivalence relation ≡1 refines equivalence relation ≡2 provided x ≡1 y ⇒ x ≡2 y (Set theoretically, ≡1 ⊆≡2 .) Intuitively, ≡1 makes finer partitions than ≡2 . Definition (Language Induced Equivalence) Given R ⊆ Σ∗ , x ≡R y

def

=

∀z ∈ Σ∗ . (xz ∈ R ⇔ yz ∈ R).

Trento’2005 – p. 38/4


def

=

∀z ∈ Σ∗ . (xz ∈ R ⇔ yz ∈ R).

Proposition ≡R is right congruent. Proposition ≡R refines R.

Trento’2005 – p. 38/4


def

=

∀z ∈ Σ∗ . (xz ∈ R ⇔ yz ∈ R).

Proposition ≡R is right congruent. Proposition ≡R refines R. Proposition(Coarseness) Let ≡ be right-congruent refining R. Then, ≡ ⊆ ≡R .

Trento’2005 – p. 38/4

Myhill-Nerode Theorem Let R ⊆ Σ∗ . The following statements are equivalent. 1. R is regular 2. There exists a Myhill-Nerode relation refinining R. 3. The relation ≡R is of finite index. The automaton A≡R gives the minimal DFA for R.

Trento’2005 – p. 39/4

State Minimization is optimal Let A recognise R. Consider the quotient automaton M = A/ ≈ as before, and assume that it has no inaccessible states. Lemma x ≡R y

⇔

x ≡M y

Trento’2005 – p. 40/4

Bisimulation Postponed to the End of course. See Kozen Supplementary Lecture B.

Trento’2005 – p. 41/4

FINITE STATE AUTOMATA

Recommend Documents