Finite AutomataWhat are Finite Automata?What are the Really?What can they look like?Finite Acceptor QuintupleBut why are they useful?DFA for less than three 1'sSlide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Non-DeterminismTransducerTransducer SextuplePushdown AutomataPushdown Automata SeptupleTuring MachinesIn SummaryReferencesQUESTIONS FOR YOUFinite AutomataCOT 4810Topics in Computer Science©Daniel DassingJanuary 24, 2008What are Finite Automata?Finite meaning bounded/ not infiniteAutomata meaning machine, self acting constructWhat are the Really?MachinesFinite number of states Transitions between statesWhat can they look like?S0 S1 S2 S30 0 01 1 10,1Finite Acceptor Quintuple(Σ, Q, S0, δ, F)Input Alphabet: Σ = {0,1}{a,b,...,z}{it, was, is}Set of States Q = {S0, S1, S2,...SK}Initial State S0 Transition Functiuon: δ (S X Σ -> S)Final/Accept State(s): F = a subset of SBut why are they useful?Basis of a language definitionlanguage being a set of strings over an alphabetRegular LanguagesExample 1: Dictionary(very large FSA)Example 2: All binary strings with less than three 1'sDFA for less than three 1'sAlphabet: Σ = {0,1}States:DFA for less than three 1'sS0 S1 S2 S3DFA for less than three 1'sAlphabet: Σ = {0,1}States: Q = {S0, S1, S2, S3}Initial State: S0Transition Function:DFA for less than three 1'sS0 S1 S2 S30 0 01 1 10,1DFA for less than three 1'sS0/0 -> S0S0/1 -> S1S1/0 -> S1S1/1 -> S2S2/0 -> S1S2/1 -> S3S3/0 -> S3S3/1 -> S3State \ Input0 1S0 S0 S1S1 S1 S2S2 S2 S3S3 S3 S3DFA for less than three 1'sAlphabet: Σ = {0,1}States: Q = {S0, S1, S2, S3}Initial State: S0Transition Function: δFinal States:DFA for less than three 1'sS0 S1 S2 S30 0 01 1 10,1DFA for less than three 1'sAlphabet: Σ = {0,1}States: Q = {S0, S1, S2, S3}Initial State: S0Transition Function: δFinal States:{ S0, S1, S2}Non-DeterminismIncomplete Transition FunctionMultiple Transitions from one state/input pairλ TransitionsTransducerAllows for output.Generally does not have a final state.Used to implement control function.Transducer Sextuple(Σ, Γ, Q, S0, δ, ω)Input Alphabet: Σ = {0,1}{a,b,...,z}{get, stop}Output Alphabet: Γ = {a,b,c}{good, bad, done}Set of States Q = {S0, S1, S2,...SK}Initial State S0 Transition Functiuon: δ : S X Σ -> SOutput Function: ω : S X Σ -> Γ or ω : S -> ΓPushdown AutomataA Finite Acceptor with a stackTransition Function: δ : Q X Σ X Γ-> QCan be used to check syntax in a compilerPushdown Automata Septuple(Σ, Γ, Q, S0, Z0, δ, F)Input Alphabet: Σ = {0,1}{a,b,...,z}{it, was, is}Set of States Q = {S0, S1, S2,...SK}Initial State S0Initial Stack SymbolTransition Function: δ : Q X Σ X Γ-> QFinal/Accept State(s): F = a subset of STuring MachinesFinite Automata with external storageModel modern computing including recursion Turing machine can model other Turing machinesIn SummaryMachinesFinite Number of StatesTransitions Between StatesMany Different TypesVery Useful.References1. “Finite State Machine” Wikipedia. Jan 2008 http://en.wikipedia.org/wiki/Finite_state_machineQUESTIONS FOR YOUWhat are the 5 parts of a DFA? Name at least 3 types of finite state
View Full Document
Unlocking...