Transcription of Deterministic Finite Automata - Chalmers
{{id}} {{{paragraph}}}
Example: air traffic controller
Deterministic Finite Automata - Chalmers
Deterministic Finite AutomataDefinition:A Deterministic Finite automaton (DFA) consists of1. a Finite set ofstates(often denotedQ)2. a Finite set ofsymbols(alphabet)3. atransition functionthat takes as argument a state and asymbol and returns a state (often denoted )4. astart stateoften denotedq05. a set offinaloracceptingstates (often denotedF)We haveq0 QandF Q1 Deterministic Finite AutomataSo a DFA is mathematically represented as a 5-uple(Q, , , q0, F)The transition function is a function inQ QQ is the set of 2-tuples (q, a) withq Qanda 2 Deterministic Finite AutomataHow to present a DFA? With atransition table01 q0q2q0 q1q1q1q2q2q1 The indicates thestartstate: hereq0 The indicates the final state(s) (here only one final stateq1)This defines the followingtransition diagramq001q210q10,13 Deterministic Finite AutomataFor this exampleQ={q0, q1, q2}start stateq0F={q1} ={0,1} is afunctionfromQ toQ :Q Q (q0,1) =q0 (q0,0) =q24 Example: passwordWhen does the automaton accepts a word?
Deterministic Finite Automata So a DFA is mathematically represented as a 5-uple (Q,Σ,δ,q0,F) The transition function δ is a function in 2
Loading..
Tags:
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document: