Finite State MachinesDefinition of a Deterministic Finite State Machine (DFSM)L1 = {w {a, b}* : every a is immediately followed a b}L2 = {w {a, b}* : every a has a matching b somewhere before it}Finite State MachinesRead K & S 2.1Do Homeworks 4 & 5.Finite State Machines 1A DFSM to accept odd integers:Definition of a Deterministic Finite State Machine (DFSM)M = (K, , , s, F), where K is a finite set of states is an alphabets K is the initial stateF K is the set of final states, and is the transition function. It is function from (K ) to Ki.e., each element of maps from: a state, input symbol pair to a new state.Informally, M accepts a string w if M winds up in some state that is an element of F when it has finished reading w (if not, it rejects w).The language accepted by M, denoted L(M), is the set of all strings accepted by M.Deterministic finite state machines (DFSMs) are also called deterministic finite state automata (DFSAs or DFAs).Computations Using FSMsA computation of A FSM is a sequence of configurations, where a configuration is any element of K *.The yields relation |-M: (q, w) |-M (q', w') iff w = a w' for some symbol a , and (q, a) = q' (The yields relation effectively runs M one step.)|-M * is the reflexive, transitive closure of |-M.(The |-M* relation runs M any number of steps.)Formally, a FSM M accepts a string w iff (s, w) |-M * (q, ), for some q F.An Example ComputationA DFSM to accept odd integers:On input 235, the configurations are:(q0, 235) |-M(q0, 35)|-M|-MThus (q0, 235) |-M* (q1, ). (What does this mean?)Lecture Notes 4 Finite State Machines 1Finite State Machines 2A DFSM to accept $.50 in change:More Examples((aa) (ab) (ba) (bb))*(b )(ab)*(a )More ExamplesL1 = {w {a, b}* : every a is immediately followed a b}A regular expression for L1:A DFSM for L1:L2 = {w {a, b}* : every a has a matching b somewhere before it}A regular expression for L2:A DFSM for L2:Lecture Notes 4 Finite State Machines 2Another Example: Socket-based Network CommunicationClient Server = {Open, Req, Reply, Close}open socketsend requestsend reply L = Open (Req Reply)* (Req ) Closesend requestsend reply… M = close socketDefinition of a Deterministic Finite State Transducer (DFST)M = (K, , O, , s, F), whereK is a finite set of states is an input alphabetO is an output alphabets K is the initial stateF K is the set of final states, and is the transition function. It is function from(K ) to (K O*)i.e., each element of maps from: a state, input symbol pair to : a new state and zero or more output symbols (an output string)M computes a function M(w) if, when it reads w, it outputs M(w).Theorem: The output language of a deterministic finite state transducer (on final state) is regular.A Simple Finite State TransducerConvert 1's to 0's and 0's to 1's (this isn't just a finite state task -- it's a one state task) 1/0 q0 0/1An Odd Parity GeneratorAfter every three bits, output a fourth bit such that each group of four bits has odd parity.Lecture Notes 4 Finite State Machines
View Full Document
Unlocking...