FINITE-STATE AUTOMATA AND ALGORITHMS

Finite-State Automata and Algorithms Bernd Kiefer, [email protected] Many thanks to Anette Frank for the slides MSc. Computational Linguistics Course, SS 2009

Overview  Finite-state automata (FSA) – What for? – Recap: Chomsky hierarchy of grammars and languages – FSA, regular languages and regular expressions – Appropriate problem classes and applications

 Finite-state automata and algorithms – Regular expressions and FSA – Deterministic (DFSA) vs. non-deterministic (NFSA) finite-state automata – Determinization: from NFSA to DFSA – Minimization of DFSA

 Extensions: finite-state transducers and FST operations

Finite-state automata: What for? Chomsky Hierarchy of Languages  Regular languages (Type-3)  Context-free languages (Type-2)  Context-sensitive languages (Type-1)  Type-0 languages

Hierarchy of Grammars and Automata  Regular PS grammar Finite-state automata  Context-free PS grammar Push-down automata  Tree adjoining grammars Linear bounded automata  General PS grammars Turing machine

computationally more complex less efficient

Finite automata executable! Finite-state MACHINE

i fy

des crib

spec

e / sp

/ ribe

ec i

Regular expressions

desc

fy

Finite-state automata model regular languages

describe/specify recognize

Regular languages

Finite Regular grammars automata executable! executable! Finite-state MACHINE

i fy

des crib

spec

e / sp

/ ribe

ec i

Regular expressions

desc

fy

Finite-state automata model regular languages

describe/specify recognize/generate

Regular languages • properties of regular languages • appropriate problem classes • algorithms for FSA

Languages, formal languages and grammars  Alphabet Σ : finite set of symbols  String : sequence x1 ... xn of symbols xi from the alphabet Σ – Special case: empty string ε

Strings

 Language over Σ : the set of strings that can be generated from Σ – Sigma star Σ* : set of all possible strings over the alphabet Σ Σ = {a, b} Σ* = {ε, a, b, aa, ab, ba, bb, aaa, aab, ...} – Sigma plus Σ+ : Σ+ = Σ* -{ε} – Special languages: ∅ = {} (empty language) ≠ {ε} (language of empty string)

 A formal language : a subset of Σ*  Basic operation on strings: concatenation • – If a = xi … xm and b = xm+1 … xn then a⋅ b = ab = xi … xmxm+1 … xn – Concatenation is associative but not commutative – ε is identity element : aε = ε a = a

 A grammar of a particular type generates a language of a corresponding type

Recap on Formal Grammars and Languages  A formal grammar is a tuple G = < Σ , Φ , S, R> – – – –

Σ alphabet of terminal symbols Φ alphabet of non-terminal symbols (Σ ∩ Φ =∅) S the start symbol R finite set of rules R ⊆ Γ * × Γ * of the form α → β where Γ = Σ ∪ Φ and α ≠ ε and α ∉ Σ*

 The language L(G) generated by a grammar G – set of strings w ⊆ Σ* that can be derived from S according to G=<Σ ,Φ, S, R>  Derivation: given G=<Σ, Φ, S, R> and u,v ∈ Γ* = (Σ ∪ Φ)* – a direct derivation (1 step) w ⇒ G v holds iff u1, u2 ∈ Γ* exist such that w = u1α u2 and v = u1β u2, and α → β ∈ R exists – a derivation w ⇒ G* v holds iff either w = v or z ∈ Γ* exists such that w ⇒G* z and z ⇒G v

 A language generated by a grammar G: L(G) = {w : S ⇒G* w & w ∈ Σ*} I.e., L(G) strongly depends on R !

Chomsky Hierarchy of Grammars  Classification of languages generated by formal grammars – A language is of type i (i = 0,1,2,3) iff it is generated by a type-i grammar – Classification according to increasingly restricted types of production rules L-type-0 ⊃ L-type-1 ⊃ L-type-2 ⊃ L-type-3 – Every grammar generates a unique language, but a language can be generated by several different grammars. – Two grammars are  (Weakly) equivalent if they generate the same string language  Strongly equivalent if they generate both the same string language and the same tree language

Chomsky Hierarchy of Grammars Type-0 languages: general phrase structure grammars  no restrictions on the form of production rules: arbitrary strings on LHS and RHS of rules  A grammar G = <Σ, Φ, S, R> generates a language L-type-0 iff – all rules R are of the form α → β, where α ∈ Γ+ and β ∈ Γ* (with Γ = Σ ∪ Φ) – I.e., LHS a nonempty sequence of NT or T symbols with at least one NT symbol and RHS a possibly empty sequence of NT or T symbols

 Example: G = <{S,A,B,C,D,E},{a},S,R>, L(G) = {a2n | n≥1} S → ACaB. CB → E. aE → Ea. Ca → aaC. aD → Da. AE → ε. CB → DB. AD → AC. a22 = aaaa ∈ L(G) iff S ⇒* aaaa

Chomsky Hierarchy of Grammars Type-1 languages: context-sensitive grammars  A grammar G = <Σ, Φ, S, R> generates a language L-type-1 iff – all rules R are of the form αAγ → αβγ , or S → ε (with no S symbol on RHS) where A ∈ Φ and α, β, γ ∈ Γ* (Γ = Σ ∪ Φ), β ≠ ε – I.e., LHS: non-empty sequence of NT or T symbols with at least one NT symbol and RHS a nonempty sequence of NT or T symbols (exception: S → ε ) – For all rules LHS → RHS : |LHS| ≤ |RHS|

 Example: L = { an bn cn | n≥1}  R = { S → a S B C, a B → a b, S → a B C, b B → b b, C B → B C, b C → b c, c C → c c } a3b3c3 = aaabbbccc ∈ L(G) iff S ⇒* aaabbbccc

Chomsky Hierarchy of Grammars Type-2 languages: context-free grammars  A grammar G = <Σ, Φ, S, R> generates a language L-type-2 iff – all rules R are of the form A → α, where A ∈ Φ and α ∈ Γ* (Γ = Σ ∪ Φ) – I.e., LHS: a single NT symbol; RHS a (possibly empty) sequence of NT or T symbols

 Example: L = { an b an | n ≥1}

R = { S → A S A, S → b, A → a }

Chomsky Hierarchy of Grammars Type-3 languages: regular or finite-state grammar  A grammar G = <Σ, Φ, S, R> is called right (left) linear (or regular) iff – all rules R are of the form  Α → w or A → wB (or A → Bw), where A,B ∈ Φ and w ∈ Σ∗ – i.e., LHS: a single NT symbol; RHS: a (possibly empty) sequence of T symbols, optionally followed (preceded) by a NT symbol

 Example: Σ = { a, b } Φ = { S, A, B} R = { S → a A,

B → b B, A → a A, B→b A→bbB }

S a

A b

S⇒aA⇒aaA⇒aabbB⇒aabbbB⇒aabbbb

A b

b b

B B b

Operations on languages  Typical set-theoretic operations on languages – – – –

Union: L1 ∪ L2 = { w : w∈L1 or w∈L2 } Intersection: L1 ∩ L2 = { w : w∈L1 and w∈L2 } Difference: L1 - L2 = { w : w∈L1 and w∉ L2 } Complement of L ⊆ Σ* wrt. Σ*: L– = Σ* - L

 Language-theoretic operations on languages – Concatenation: L1L2 = {w1w2 : w1∈L1 and w2∈L2} – Iteration: L0={ε}, L1=L, L2=LL, ... L*= ∪i≥0 Li, L+ = ∪i>0 Li – Mirror image: L-1 = {w-1 : w∈L}

 Union, concatenation and Kleene star are called regular operations  Regular sets/languages: languages that are defined by the regular operations: concatenation (⋅) , union (∪) and kleene star (*)  Regular languages are closed under concatenation, union, kleene star, intersection and complementation

Finite Regular grammars automata executable! executable! Finite-state MACHINE

ify

des

crib

spec

e / sp

/ ribe

ec i

Regular expressions

desc

fy

Regular languages, regular expressions and FSA

describe/specify recognize/generate

Regular languages

Regular languages and regular expressions  Regular sets/languages can be specified/defined by regular expressions Given a set of terminal symbols Σ, the following are regular expressions – ε is a regular expression – For every a ∈ Σ, a is a regular expression – If R is a regular expression, then R* is a regular expression – If Q,R are regular expressions, then QR (Q ⋅ R) and Q ∪ R are regular expressions  Every regular expression denotes a regular language – – – – –

L(ε) = {ε} L(a) = {a} for all a ∈ Σ L(αβ) = L(α)L(β) L(α ∪β) = L(α) ∪ L(β) L(α*) = L(α)*

Finite-state automata (FSA)  Grammars: generate (or recognize) languages Automata: recognize (or generate) languages  Finite-state automata recognize regular languages  A finite automaton (FA) is a tuple A = <Φ,Σ, δ, q0,F> – – – – –

Φ a finite non-empty set of states Σ a finite alphabet of input letters δ a transition function Φ × Σ → Φ q0 ∈ Φ the initial state F ⊆ Φ the set of final (accepting) states

 Transition graphs (diagrams): – states: circles – transitions: directed arcs between circles – initial state – final state

p∈ Φ

p p a p r

q

δ(p, a) = q p = q0 r⊆F

FSA transition graphs and traversal  Transition graph c

q0

q1

l q6

l

q2

e e

q7

e

q3

t

q8

a

r

q4

v

q5

e

t

l c

q0

δ(q0,e)=q3

l q6

δ(q0,l)=q6 δ(q1,l)=q2 δ(q2,e)=q3

e

q1

Transition function δ: Φ × Σ → Φ δ(q0,c)=q1

q9

 Traversal of an FSA = Computation with an FSA c

S = q0 F = {q5, q8 }

v l e e

q2 q7

e e

t

δ(q3,a)=q4

r q3 q8

δ(q3,v)=q9

a v t

q4 e q9

r

δ(q4,r)=q5

q5

δ(q6,e)=q7 δ(q7,t)=q8 δ(q8,t)=q9 δ(q9,e)=q4

FSA transition graphs and traversal  Transition graph c

q0

q1

l q6

l

q2

e e

q7

State diagram e

q3

t

q8

a

r

q4

v

q5

e

t

q9

 Traversal of an FSA = Computation with an FSA l

c c

q0

e

q1

l q6

v l e e

q2 q7

e e

t

r q3 q8

a v t

q4 e q9

r

q5

δ q0 q1 q2 q3 q4 q5 q6 q7 q8 q9

a 0 0 0 q4 0 0 0 0 0 0

c q1 0 0 0 0 0 0 0 0 0

e q3 0 q3 0 0 0 q7 0 0 q4

l q6 q2 0 0 0 0 0 0 0 0

r 0 0 0 0 q5 0 0 0 0 0

t 0 0 0 0 0 0 0 q8 q9 0

v 0 0 0 q9 0 0 0 0 0 0

FSA can be used for • acceptance (recognition) • generation

FSA traversal and acceptance of an input string  Traversal of a (deterministic) FSA – FSA traversal is defined by states and transitions of A, relative to an input string w∈Σ* – A configuration of A is defined by the current state and the unread part of the input string: (q, wi,), with q∈Φ, wi suffix of w – A transition: a binary relation between configurations (q,wi) |–A (q’,wi+1) iff wi = zwi+1 for z∈Σ and δ(q,z)= q’ (q,wi) yields (q’,wi+1) in a single transition step – Reflexive, transitive closure of |–A: (q, wi) |–*A (q’, wj) (q, wi) yields (q’, wj) in zero or a finite number of steps

 Acceptance – Decide whether an input string w is in the language L(A) defined by FSA A – An FSA A accepts a string w iff (q0,w) |–*A (qf, ε), with q0 initial state, qf ⊆ F – The language L(A) accepted by FSA A is the set of all strings accepted by A I.e., w ∈ L(A) iff there is some qf ⊆ FA such that (q0,w) |–*A (qf, ε)

Regular grammars and Finite-state automata  A grammar G = <Σ, Φ, S, R> is called right linear (or regular) iff all rules R are of the form A → w or A → wB, where A,B ∈ Φ and w ∈ Σ* – Σ={a, b}, Φ={S,A,B}, R={S → aA, A → aA, A → bbB, B → bB, B → b} S ⇒ aA ⇒ aaA ⇒ aabbB ⇒ aabbbB ⇒ aabbbb – The NT symbol corresponds to a state in an FSA: the future of the derivation only depends on the identity of this state or symbol and the remaining production rules. S – Correspondence of type-3 grammar rules a A with transitions in a (non-deterministic) FSA:  

Α → w B ≡ δ(Α,w)=Β Α→w ≡ δ(Α,w)=q, q ∈Φ

– Conversely, we can construct an FSA from the rules of a type-3 language

b

A b

b

b  Regular grammars and FSA can be shown to be equivalent  Regular grammars generate regular languages  Regular languages are defined by concatenation, union, kleene star

B B b

Deterministic finite-state automata  Deterministic finite-state automata (DFSA) – at each state, there is at most one transition that can be taken to read the next input symbol – the next state (transition) is fully determined by current configuration – δ is functional (and there are no ε-transitions)

 Determinism is a useful property for an FSA to have! – Acceptance or rejection of an input can be computed in linear time 0(n) for inputs of length n – Especially important for processing of LARGE documents

 Appropriate problem classes for FSA – Recognition and acceptance of regular languages, in particular string manipulation, regular phonological and morphological processes – Approximations of non-regular languages in morphology, shallow finitestate parsing, …

Multiple equivalent FSA  FSA for the language Llehr = { lehrbar, lehrbarkeit, belehrbar, belehrbarkeit, unbelehrbar, unbelehrbarkeit, unlehrbar, unlehrbarkeit }  DFSA for Llehr be lehr un

be

lehr

bar

keit

lehr

 Regular expression and FSA for Llehr : (un | ε) (be lehr | lehr) bar (keit | ε) (non-deterministic) un keit be lehr bar

ε  Equivalent FSA (non-deterministic)

un

ε

lehr be lehr

ε

ε

bar

keit

Defining FSA through regular expressions  FSA for even mildly complex regular languages are best constructed from regular expressions! 

Every regular expression denotes a regular language – –

L(ε) = {ε} L(a) = {a} for all a ∈ Σ

● ● ●

L(αβ ) = L(α)L(β) L(α ∪β) = L(α) ∪ L(β) L(α*) = L(α)*

 Every regular expression translates to a FSA (Closure properties) – An FSA for a (with L(a) = {a}), a ∈ Σ:

a

– An FSA for ε (with L(ε) = {ε }), ε ∈ Σ:

ε

– Concatenation of two FSA FA and FB: 

ΣΑΒ = ΣΑ (Σ initial state)



ΦΑΒ = ΦΒ (Φ set of final states)

∀ δΑΒ = δΑ ∪ δΒ ∪ {δ(,qj) | qi ∈ ΦΑ, qj = ΣΒ }

FA

ε

FB

FAB

Defining FSA through regular expressions – union of two FSA FA and FB: FA ε  SAB = s0 (new state)  FAB = { sj } (new state) ε FB ∀ δAB = δA ∪ δB ∪ {δ(,qz) | q0 = SAB, ( qz = SA or qz = SB)} ∪ {δ(,qj) | (qz∈FA or qz∈FB), qi ∈FAB}

ε – Kleene Star over an FSA FA : ε FA  SA* = s0 (new state) ε  FA* = { qj } (new state) ∀ δAB = δA ∪ ∪ {δ(,qz) | qj ∈ FA, qz = SA)} ∪ {δ(,qz) | q0 = SA*, ( qz = SA or qz = FA*)} ∪ {δ(,qj) | qz∈FA , qj∈FA*}

ε

FA∪ B

ε

ε

FA*

Defining FSA through regular expressions (ab ∪ aba)*

ε

ε

ε ε

ε ε

ε

a

a

ε

b

b

ε

ε

ε a

ε

ε ε

ε  

ε-transition: move to δ(q, ε) without reading an input symbol FSA construction from regular expressions yields a non-deterministic FSA (NFSA) – Choice of next state is only partially determined by the current configuration, i.e., we cannot always predict which state will be the next state in the traversal

Non-deterministic finite-state automata (NFSA)  Non-determinism  

Introduced by ε-transitions and/or Transition being a relation Δ over Φ × Σ* × Φ, i.e. a set of triples Equivalently: Transition function δ maps to a set of states: δ: Φ × Σ → ℘(Φ)

 A non-deterministic FSA (NFSA) is a tuple A = <Φ,Σ, δ, q0,F>     

Φ a finite non-empty set of states Σ a finite alphabet of input letters δ a transition function Φ × Σ* → ℘ (Φ) q0 ∈ Φ the initial state F ⊆ Φ the set of final (accepting) states

(or a finite relation over Φ × Σ* × Φ)

 Adapted definitions for transitions and acceptance of a string by a NFSA  



(q,w) |–A (q’,wi+1) iff wi = zwi+1 for z∈Σ* and q’∈ δ(q,z) An NDFA (w/o ε) accepts a string w iff there is some traversal such that (q0,w) |–*A (q’, ε) and q’ ⊆ F. A string w is rejected by NDFA A iff A does not accept w, i.e. all configurations of A for string w are rejecting configurations!

Non-determinism in FSA (ab ∪ aba)* ε

ε

ε ε

ε ε

ε

a

a

ε

b

ε

a

b a

b

ε

ε

ε a

ε

ε ε


ε

ε ε

ε ε

ε

a

a

ε

b

ε

a

b a

b

ε

ε

ε a

ε

ε ε


ε

ε ε

ε ε

ε

a

a

ε

b

ε

a

b a

b

ε

ε

ε a

ε

ε ε


ε

ε ε

ε ε

ε

a

a

ε

b

ε

a

b

b a eof

ε

ε

ε

ε

 ε ε 

a


ε

ε ε

ε

ε

ε

    ε ε

a

a

ε

b

ε

a

b

b a eof

ε

a

ε

ε ε

Equivalence of DFSA and NFSA  Despite non-determinism, NFSA are not more powerful than DFSA: they accept the same class of languages: regular languages  For every non-deterministic FSA there is deterministic FSA that accepts the same language (and vice versa) – The corresponding DFSA has in general more states, in which it models the sets of possible states the NFSA could be in in a given traversal

 There is an algorithm (via subset construction) that allows conversion of an NFSA to an equivalent DFSA Efficiency considerations: an FSA is most efficient and compact iff  It is a DFSA (efficiency) → Determinization of NFSA  It is minimal (compact encoding) → Minimization of FSA

Equivalence of DFSA and NFSA   

FSA A1 and A2 are equivalent iff L(A1) = L(A2) Theorem: for each NFSA there is an equivalent DFSA Construction: A = < Φ, Σ, δ, q0, F > a NFSA over Σ – define eps(q) = { p ∈ Φ | (q, ε, p) ∈δ }



– define an FSA A‘= <Φ’,Σ, δ’, q0’,F’> over sets of states, with Φ’={B | B⊆ Φ} q0’={eps(q0)} δ’(B,a) = ⋃ { eps(p) | q ∈Β and ∃ p∈B such that (q, a, p) ∈ δ } F’={B ⊆ Φ | B ∩ F ≠ ∅} A’ satisfies the definition of a DFSA. We need to show that L(A) = L(A’)



Define D(q, w) := { p ∈ Φ | (q, w) ⊢

*

(p, ε) }

A

D'(Q, w) := { P ∈ Φ' | (Q, w) ⊢

* A'

(P, ε) }

and

Equivalence of DFSA and NFSA: Proof Prove: D(q0, w) = D'({q0}, w) by induction over length of w  

|w| = 0 : by definition of D and D' Induction step: |w| = k+1, w = v a, by hypothesis: D(q0, v) = D'({q0}, v) = {p1, p2, ... , pk }= P by def. of D: D(q0, w) =⋃p ∈ P {eps(q) | (p, a, q) ∈ δ } by def. of δ': D'({p1, p2, ... , pk }, a) =⋃p ∈ P {eps(q) | (p, a, q) ∈ δ } it follows: D'({q0}, w) = δ'(D'({q0}, w), a) = D'({p1, p2, ... , pk }, a)

= ⋃p ∈ P {eps(q) | (p, a, q) ∈ δ } = D(q0, w) q.e.d. 

Finally, A and A' only accept if D'({q0}, w) = D(q0, w) contain a state ∈F

Determinization by subset construction NFSA A=<Φ,Σ, δ,q0,F>

A‘=<Φ’,Σ, δ’,q0’,F’>

b

Subset construction:

a

a

b

a a

b

L(A)= a(ba)* ∪ a(bba)*

Compute δ’ from δ for all subsets S ⊆ Φ and a∈Σ s.th. δ’(S,a) = { s’| ∃s∈S s.th. (s,a,s‘)∈δ}

Determinization by subset construction NFSA A=<Φ,Σ, δ,q0,F> b

1

a

2

a

4

b

a

3 a

5 6

b

L(A)= a(ba)* ∪ a(bba)*

A‘=<Φ’,Σ, δ’, q0’,F’> Φ’= { B | B ⊆ {1,2,3,4,5,6} q0’={1}, δ’({1},a)={2,3}, δ’({4},a)= {2}, δ’({1},b)=∅, δ’({4},b)= ∅, δ’({2,3},a)= ∅, δ’({3},a)= ∅, δ’({2,3},b)= {4,5}, δ’({3},b)= {5}, δ’({4,5},a)= {2}, δ’({5},a)= ∅, δ’({4,5},b)= {6}, δ’({5},b)= {6} δ’({2},a)= ∅, δ’({2},b)= {4}, F’= {{2,3},{2},{3}} δ’({6},a)= {3}, δ’({6},b)= ∅,


1

b

a

3 a

1

a

2

a

a

4

5 6

2,3

b



1

b

a

3 a

1

a

2

a

a

4

5 6

2,3 b

b

4,5



a

2

a 1

4

b

a

3 a

5 b

6

2 a 1

a

2,3 b

4,5 b

6


Determinization by subset construction NFSA A=<Φ,Σ, δ,q0,F>

b

b

1

4

2 a

a

2

a

1

b

a

3 a

DFSA A‘=<Φ’,Σ, δ’, q0’,F’>

5 6

a

2,3

b

4 a

4,5 b

b 6

b

L(A) = L(A’) = a(ba)* ∪ a(bba)*

a

3

b

5

ε-transitions and ε-closure  Subset construction must account for ε-transitions  ε-closure – The ε-closure of some state q consists of q as well as all states that can be reached from q through a sequence of ε-transitions  

q ∈ ε−closurε(q) If r∈ε−closure(q) and (r, ε,q‘)∈δ, then q’∈ ε−closure(q),

− ε-closure defined on sets of states ∀ ε-closure(R) =

∪

q∈R

ε-closure(q)

(with Ρ ⊆ Φ)

 Subset construction for ε-NFSA – Compute δ’ from δ for all subsets S ⊆Φ and a∈Σ s.th. δ’(S,a) = { s’’| ∃s∈S s.th. (s,a,s‘)∈δ and s’’∈ ε-closure(s’) }

Example  ε-NFSA for (a|b)c*

ε 0 ε

ε-closure for all s∈Φ: ε-closure(0)={0,1,2}, ε-closure(1)={1}, ε-closure(2)={2}, ε-closure(3)={3,5,6,7,9}, ε-closure(4)={4,5,6,7,9}, ε-closure(5)={5,6,7,9}, ε-closure(6)={6,7,9}, ε-closure(7)={7}, ε-closure(8)={8,7,9}, ε-closure(9)={9}

1 2

a b

ε

3 ε 4

ε

ε

5

6

ε

7

c

Transition function over subsets δ’({0},ε)= {0,1,2}, δ’({0,1,2},a)={3,5,6,7,9}, δ’({0,1,2},b)= {4,5,6,7,9}, δ’({3,5,6,7,9},c)= {8,7,9}, δ’({4,5,6,7,9},c)= {8,7,9}, δ’({8,7,9},c)= {8,7,9} a 012

35679 b

45679

c c

879

c

ε

8

ε

9

An algorithm for subset construction  Construction of DFSA A‘=<Φ’,Σ, δ’,q0’,F’> from NFSA A=<Φ,Σ, δ, q0,F> – Φ’={B| B ⊆ Φ}, if unconstrained can be 2|Φ| with |Φ| = 33 this could lead to an FSA with 233 states (exceeds the range of integers in most programming languages) – Many of these states may be useless 0

a

b

1

0

1

2

01

12

02

b a,b

2

a

L= (a|b)a* ∪ ab+a*

012

An algorithm for subset construction  Construction of DFSA A‘=<Φ’,Σ, δ’,q0,F’> from NFSA A=<Φ,Σ, δ, q0,F> – Φ’={B| B⊆Φ}, if unconstrained can be 2|Φ| with |Φ| = 33 this could lead to an FSA with 233 states (exceeds the range of integers in many programming languages) – Many of these states may be useless b 0

a

b

1

b a,b

2

a

0

1

a

b

01 a,b b

L= (a|b)a* ∪ ab+a*

12 a,b 012

a a

2 02

a


a

b

1

b a,b

2

a

0

1

a

b

01 a,b b

L= (a|b)a* ∪ ab+a*

12

a a

2

a

02

a,b 012 No transition can ever enter these states


a

b

1

b a,b

2

0

a

a

a

2

a

12 b

L= (a|b)a* ∪ ab+a*

Only consider states that can be traversed starting from q0

An algorithm for subset construction  Basic idea: we only need to consider states B ⊆ Φ that can ever be traversed by a string w∈Σ*, starting from q0‘  I.e., those B ⊆ Φ for which B = δ’(q0,w), for some w∈Σ*, with δ’ the recursively constructed transition function for the target DFSA A’  Consider all strings w∈Σ* in order of their length: ε, a,b, aa,ab,ba,bb, aaa,... b 0

0

2

a 12

l=0 (ε)

– – – –

l=1 (a,b)

b

0 a b

12

2 a

a

l=2,3,4, … (aa, ab, ba, bb, aaa, aab, aba, …)

Construction by increasing lengths of strings For each a∈Σ, construct transitions to known or new states according to δ New target states (A’) are placed in a queue (FIFO) Termination: no states left on queue

An algorithm for subset construction DETERMINIZE(Φ, Σ, δ, q0, F) q0‘← q0 Φ’ ← {q0‘} ENQUEUE(Queue, q0‘) while Queue ≠ ∅ S ← DEQUEUE(Queue) for a∈Σ

δ’(S,a) = ∪r∈S δ(r,a) if δ’(S,a) ∉ Φ’ Φ’ ← Φ’ ∪ δ’(S,a) ENQUEUE(Queue, δ’(S,a)) if δ’(S,a) ∩ F ≠ ∅ F‘ ← {δ’(S,a)} fi fi return (Φ’,Σ, δ’, q0‘, F’)

Complexity Maximal number of states placed in queue is 2|Φ| So, worst case runtime is exponential • determinization is a costly operation, • but results in an efficient FSA (linear in size of the input) • avoids computation of isolated states Actual run time depends on the shape of the NFSA

Minimization of FSA  Can we transform a large automaton into a smaller one (provided a smaller one exists)?  If A is a DFSA, is there an algorithm for constructing an equivalent minimal automaton Amin from A? A

b

0 a 1

A‘ 2

a

c b

0 a

3

a

1

b,c

A is equivalent to A‘ i.e., L(A) = L(A‘)

2 b

a

A‘ is smaller than A i.e., |Φ| > |Φ‘|

 A can be transformed to A‘: – States 2 and 3 in A “do the same job”: once A is in state 2 or 3, it accepts the same suffix string. Such states are called equivalent. – Thus, we can eliminate state 3 without changing the language of A, by redirecting all arcs leading to 3 to 2, instead.

Minimization of FSA  A DFSA can be minimized if there are pairs of states q,q‘∈Φ that are equivalent  Two states q,q’ are equivalent iff they accept the same right language.  Right language of a state: – For A=<Φ,Σ, δ, q0,F> a DFSA, the right language L→(q) of a state q∈Φ is the set of all strings accepted by A starting in state q: L→(q) = {w∈Σ* | δ*(q,w) ∈F} – Note: L→(q0) = L(A)  State equivalence: – For A=<Φ,Σ, δ, q0,F> a DFSA, if q,q’∈Φ, q and q‘ are equivalent (q ≡ q’) iff L→(q) = L→(q’) – ≡ is an equivalence relation (i.e., reflexive, transitive and symmetric) – ≡ partitions the set of states Φ into a number of disjoint sets Q1 .. Qn of equivalence classes s.th. ∪i=1..m Qi = Φ and q ≡ q’ for all q,q’∈ Qi

Partitioning a state set into equivalence classes C0 C2

a

0

C1

1

b

a b

2

6

a

5

a

a 3

C3

a

4 b

C4

All classes Ci consist of equivalent states qj=i..n that accept identical right languages L→(qj) Whenever two states q,q‘ belong to different classes, L→(q) ≠ L→(q‘)

7

Equivalence classes on state set defined by ≡

Minimization: elimination of equivalent states

Minimization of a DFSA A DFSA A=<Φ,Σ, δ, q0,F> that contains equivalent states q, q’ can be transformed to a smaller, equivalent DFSA A’=<Φ’,Σ, δ’, q0,F’> where 



Φ’ = Φ\{q’}, F’=F\{q’},

δ’(s,a) = q if δ(s,a) = q’; δ’ is like δ with all transitions to q’ redirected to q:δ’(s,a) = δ(s,a) otherwise

 Two-step algorithm – Determine all pairs of equivalent states q,q’ – Apply DFSA reduction until no such pair q,q’ is left in the automaton

 Minimality



– The resulting FSA is the smallest DFSA (in size of Φ) that accepts L(A): we never merge different equivalence classes, so we obtain one state per class.  We cannot do any further reduction and still recognize L(A).  As long as we have >1 state per class, we can do further reduction steps. A DFSA A=<Φ,Σ, δ, q0,F> is minimal iff there is no pair of distinct but equivalent states ∈Φ, i.e. ∀ q, q’∈Φ : q ≡ q’ ⇔ q = q’

Example

a

0

1

b b

6

a

a 3

b

a

2

a

0 5

a

a

1

b

2 a

a

4 b

3

a

4 b

7

7

Example

a

0 b

a

1

b

b

2

a

1

b

2

a 3

a

0

a a

4 b 7

3

a,b

4

Algorithm MINIMIZE(Φ, Σ, δ, q0, F) main EqClass[] ← PARTITION(A) q0 ← EqClass[q0] for ∈δ δ(q,a) ← min(EqClass[q‘]) for q∈ Φ if q ≠ min(EqClass[q]) Φ ← Φ\{q} if q∈ F F ← F\{q}

MINIMIZE • PARTITION(A): - determines all eqclasses of states in A - returns array EqClass[q] of eq. classes of q • redirect all transitions ∈δ to point to min(EqClass[q’]) • remove all redundant states from Φ and F

Computing partitions: Naïve partitioning NAIVE_PARTITION(Φ, Σ, δ, q0, F) for each q∈ Φ

EqClass[q] ← {q} for each q∈ Φ for each q‘∈ Φ if EqClass[q] ≠ EqClass[q‘] ∧ CHECKEQUIVALENCE(Aq,Aq‘) = True EqClass[q] ← EqClass[q] ∪ EqClass[q‘] EqClass[q‘] ← EqClass[q]

NAIVE_PARTITION • array EqClass of pointers to disjoint sets for equivalence classes • first loop: initializing EqClass by {q}, for each q∈ Φ

• second nested loop: if we find new equivalent states q ≡ q’, we merge the respective equivalence classes EqClasses and reset EqClass[q] to point to the new merged class Runtime complexity: loops: 0(|Φ|2 ) CheckEquivalence: 0(|Φ|2 · |Σ|) ⇒ 0(|Φ|4 · |Σ|) !

Computing partitions: Dynamic Programming  Source of inefficiency: naive algorithm traverses the whole automaton to determine, for pairs q,q‘, whether they are equivalent  Results of previous equivalence checks can be reused

p

a

p ≡ p‘ b

p‘

q

b a

q ≡ q‘ a

q‘

If q ≡ q‘, L→(q) ≠ L→(q’), therefore, for all s.th. δ-1(p,a)=q and δ-1(p’,a)=q’ for some a∈Σ, p ≡ p’.

a

 Thus, non-equivalence results can be propagated ● Propagation from final/non-final pairs: L→(q) ≠ L→(q’) if q ∈F ∧ q’∉F ● Propagation from pairs where δ(q,a) is defined but δ(q’,a) is not.

Propagation of non-equivalent states LocalEquivalenceCheck(q,q‘) if (q∈F and q‘∉F) or (q∉F and q‘∈F) return (False) if ∃a∈Σ s.th. only one of δ(q,a), δ(q’,a) is defined return (False) return (True) PROPAGATE(q,q‘) for a∈Σ for p∈δ-1(q,a), for p’∈δ-1(q’,a) if Equiv[min(p,p’),max(p,p’)]=1 Equiv[min(p,p’),max(p,p’)] ← 0 PROPAGATE(p,p‘)

Non-equivalence check for states – Only one of q, q’ is final – For some a∈Σ, δ(q,a) is defined, δ(q’,a) is not

Propagation (I): Table filling algorithm (Aho, Sethi, Ullman)  represent equivalence relation as a table Equiv, cells filled with boolean values  initialize all cells with 1; reset to 0 for non-equivalent states  main loop: call of PROPAGATE for nonequivalent states from LocalEquivalenceCheck

Propagation of non-equivalent states LocalEquivalenceCheck(q,q‘) if (q∈F and q‘∉F) or (q∉F and q‘∈F) return (False) if ∃a∈Σ s.th. only one of δ(q,a), δ(q’,a) is defined return (False) return (True) PROPAGATE(q,q‘) for a∈Σ for p∈δ-1(q,a), for p’∈δ-1(q’,a) if Equiv[min(p,p’),max(p,p’)]=1 Equiv[min(p,p’),max(p,p’)] ← 0 PROPAGATE(p,p‘)

Runtime Complexity: 0(|Φ|2 · |Σ|) • PROPAGATE is never called twice on a given pair of states (checks Equiv[q,q’]=1)

Space requirements: 0(|Φ|2) cells TableFillingPARTITION(Φ, Σ, δ, q0, F) for q,q‘∈Φ, q
More optimizations  Hopcroft and Ullman: space requirement 0(|Φ|), by associating states with their equivalence classes  Hopcroft: Runtime complexity of 0(|Φ| · log|Φ| · |Σ|), by distinction of active/non-active blocks

Brzozowski‘s Algorithm Minimization by reversal and determinization L(A)-1

L(A)

DFSA A

reverse

NFSA A-1

determinize

DFSA A-1 L(A)

DFSA (A-1)-1

L(A) determinize

Reversal • Final states of A— : set of initial states of A • Initial state of A— : F of A • δ–(q,a) = {p∈Φ | δ(p,a)=q } • L(A-1) = L(A)-1

reverse

NFSA (A-1)-1

Why does it yield a minimal DFSA A‘? DFSA A

rev

NFSA A-1 a

c

DFSA A-1 qo

det

DFSA A-1

NFSA (A–1) -1

b d

a

rev

NFSA (A-1)-1 a

det c

b

rev

DFSA (A-1)-1

a

d

qo

Consider the right languages of states q, q‘ in NFSA (A-1)-1: • If for all distinct states q, q‘ L→(q) ≠ L→(q’), i.e. L→(q) ∩ L→(q’) = ∅, it holds that each pair of states q,q’ recognize different right languages, and thus, that the NFSA (A-1)-1 satisfies the minimality condition for a DFSA. • If there were states q,q’ in NFSA (A-1)-1 s.th. L→(q) ∩ L→(q’) ≠ ∅, there would be some string w that leads to two distinct states in DFSA A-1. This contradicts the determinicity criterion of a DFSA. • Determinization of NFSA (A-1)-1 does not destroy the property of minimality

Applications of FSA: String Matching  Exact, full string matching – Lexicon lookup: search for given word/string in a lexicon – Compile lexicon entries to FSA by union – Test input words for acceptance in lexicon-FSA

Word list

compile to FSA

transition table!

recognition/application/lookup of input word w in/to FSA Alexicon: (q0,w) |–*Alexicon (qf, ε) is true, with q0 initial state and qf ⊆ F

traversal and recognition (acceptance)

Applications of FSA: String Matching  Substring matching – Identify stop words in stream of text – Stem recognition: small, smaller, smallest

 Make use of full power of finite-state operations! – Regular expression with any-symbols for text search  

?∗ small( ε | er | est) ?∗ ?∗ ( a | the | …) ?∗

– Compilation to NFSA, convert to DFSA – Application by composition of FST with full text 

FSAtext stream ∘ FSTsmall : if defined, search term is substring of text

Application of FSA: Replacement  (Sub)string replacement – Delete stop words in text – Stemming: reduce/replace inflected forms to stems: smallest → small – Morphology: map inflected forms to lemmas (and PoS-tags): good, better, best → good+Adj – Tokenization: insert token boundaries – …

⇒ Finite-state transducers (FST)

From Automata to Transducers Automata

Transducers

 recognition of an input string w

 recognition of an input string w  generation of an output string w‘

q0

l

q1

e

q2

a

q3

v

q4

e

 define a language  accept strings, with transitions defined for symbols ∈Σ

q0

q5

l l

q1

e e

q2

a f

q3

v t

q4

e ε

q5

 define a relation between languages  equivalent to FSA that accept pairs of strings, with transitions defined for pairs of symbols  operations: replacement ● ● ●

deletion , a ∈Σ -{ε} insertion <ε, a>, a ∈Σ -{ε} substitution , a,b ∈Σ, a ≠ b

Transducers and composition  An FSTs encodes a relation between languages  A relation may contain an infinite number of ordered pairs, e.g. translating lower case letters to upper case a:A, b:B, c:C,...

a lower/upper case transducer

a path through the lower/upper case transducer, for string xyzzy  The application of a transducer to a string may also be viewed as composition of the FST with the (identity relation on the string) x:X

q0

l l l L

q1

e e e E

q2

y:Y

f f f F

q3

v t t T

z:Z

q4

e ε

z:Z

+VBD q5 q4 ε

y:Y

q0

l L

q1

e E

q2

f F

q3

v T

q4

e ε

q4

+VBD q5 ε

Literature    

 

H.R. Lewis and C.H. Papadimitriou: Elements of the Theory of Computation. Prentice-Hall, New Jersey (Chapter 2). J. Hopcroft and J. Ullman: Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, Massachusetts, (Chapter 2,3). B.H. Partee, A. ter Meulen and R.E. Wall: Mathematical Methods in Linguistics, Kluwer Academic Publishers, Dordrecht (Chapter 15.5,15.6, 17) D. Jurafsky and J.H. Martin: Speech and Language Processing. An introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition, Prentice-Hall, New Jersey (Chapter 2). C. Martin-Vide: Formal Grammars and Languages. In: R. Mitkov (ed): Oxford Handbook of Computational Linguistics, (Chapter 8). L. Karttunen: Finite-state Technology. In: R. Mitkov (ed): Oxford Handbook of Computational Linguistics, (Chapter 18).

Off-the-shelf finite-state tools 

  

Xerox finite-state tools – http://www.xrce.xerox.com/competencies/content-analysis/fst/ > Xerox Finite State Compiler (Demo) – XFST Tools (provided with Beesley and Karttunen: Finite-State Morphology, CSLI Publications) Geertjan van Noord’s finite-state tools – http://odur.let.rug.nl/~vannoord/Fsa/ FSA Utilities at John Hopkins – http://cs.jhu.edu/~jason/406/software.html AT&T FSM Library – http://www.research.att.com/sw/tools/fsm/

Exercises 



Write a program for acceptance of a string by a DFSA. Then extend it to a finite-state transducer that can translate a surface form to lemma + POS, or between upper and lower case. b Determinize the following NFSA by subset construction. δ1 a p p,q p A1=<{p,q,r,s},{a,b},δ1,p,{s}> where δ1 is as follows: q r r r s





s s

s

Construct an NFSA with ε-transitions from the regular expression (a|b)ca*, according to the construction principles for union, concatenation and kleene star. Then transform the NFSA to a DFSA by subset construction. Find a minimal DFSA for the FSA A=<{A,..,E},{0,1}, δ3,A,{C,E}> (using the table filling algorithm by propagation). δ 0 1 3

A B C D E

B B D D C

D C E E -

FINITE-STATE AUTOMATA AND ALGORITHMS

Recommend Documents