Lecture Notes 6 Interpreters for Finite State Machines 1 Interpreters for Finite State Machines Deterministic FSAs as Algorithms Example: No more than one b a a a,b b b S T U Length of Program: |K| × (|Σ| + 2) Time required to analyze string w: O(|w| × |Σ|) We have to write new code for every new FSM. Until accept or reject do: S: s := get-next-symbol; if s = end-of-file then accept; else if s = a then go to S; else if s = b then go to T; T: s:= get-next-symbol; if s = end-of-file then accept; else if s = a then go to T; else if s = b then go to U; etc. A Deterministic FSA Interpreter To simulate M = (K, Σ, δ, s, F): ST := s; Repeat i := get-next-symbol; if i ≠ end-of-string then ST := δ(ST, i) Until i = end-of-string; If ST ∈ F then accept else reject Simulate the no more than one b machine on input: aabaa Nondeterministic FSAs as Algorithms Real computers are deterministic, so we have three choices if we want to execute a nondeterministic FSA: 1. Convert the NDFSA to a deterministic one: • Conversion can take time and space 2K. • Time to analyze string w: O(|w|) 2. Simulate the behavior of the nondeterministic one by constructing sets of states "on the fly" during execution • No conversion cost • Time to analyze string w: O(|w| × K2) 3. Do a depth-first search of all paths through the nondeterministic machine.Lecture Notes 6 Interpreters for Finite State Machines 2 A Nondeterministic FSA Interpreter To simulate M = (K, Σ, ∆, s, F): SET ST; ST := E(s); Repeat i := get-next-symbol; if i ≠ end-of-string then ST1 := ∅ For all q ∈ ST do For all r ∈ ∆(q, i) do ST1 := ST1 ∪ E(r); ST := ST1; Until i = end-of-string; If ST ∩ F ≠ ∅ then accept else reject A Deterministic Finite State Transducer Interpreter To simulate M = (K, Σ, O, δ, s, F), given that: δ1(state, symbol) returns a single new state (i.e., M is deterministic), and δ2(state, symbol) returns an element of O*, the string to be output. ST := s; Repeat: i := get-next-symbol; if i ≠ end-of-string then write(δ2(ST, i)); ST := δ1(ST, i) Until i = end-of-string; If ST ∈ F then accept else
View Full Document
Unlocking...