CPS 140 - Mathematical Foundations of CSDr. Susan RodgerSection: Finite Automata (Ch. 2) (handout)Deterministic Finite Accepter (or Automata)A DFA=(Q,Σ,δ,q0,F)head moves input tapetape headcurrent stateaab bab01whereQ is finite set of statesΣ is tape (input) alphabetq0is initial stateF ⊆ Q is set of final states.δ:Q×Σ→QExample: Create a DFA that accepts even binary numbers.Transition Diagram:01q1q010M=(Q,Σ,δ,q0,F) =Tabular Format01q0 q1 q0q1 q1 q0Example of a move: δ(q0,1)=1Algorithm for DFA:Start in start state with input on tapeq = current states = current symbol on tapewhile (s != blank) doq=δ(q,s)s = next symbol to the right on tapeif q∈F then acceptExample of a trace: 11010Pictorial Example of a trace for 100:100q0q1100q0q1100q0q11)3)2)4)100q0q1Definition:δ∗(q, λ)=qδ∗(q, wa)=δ(δ∗(q, w),a)Definition The language accepted by a DFA M=(Q,Σ,δ,q0,F) is set of all strings on Σ accepted by M.Formally,L(M)={w ∈ Σ∗| δ∗(q0,w) ∈F}2Trap StateExample: L(M) = {bna | n>0}q0 q1bbatrapaa,babq2You don’t need to show trap states! Any arc not shown will by default go to a trap state.Example: Create a DFA that accepts even binary numbers that have an even number of 1’s.Definition A language is regular iff there exists DFA M s.t. L=L(M).3Chapter 2.2Nondeterministic Finite Automata (or Accepter)DefinitionAn NFA=(Q,Σ,δ,q0,F)whereQ is finite set of statesΣ is tape (input) alphabetq0is initial stateF ⊆ Q is set of final states.δ:Q×(Σ ∪{λ})→2QExampleq0q1q2q3aabbaNote: In this example δ(q0,a)ExampleL={(ab)n| n>0}∪{anb|n>0}Definition qj∈ δ∗(qi,w) if and only if there is a walk from qito qjlabeled w.Example From previous example:δ∗(q0,ab)=δ∗(q0,aba)=Definition: For an NFA M, L(M)={w ∈ Σ∗| δ∗(q0,w)∩F 6=∅}The language accepted by nfa M is all strings w such that there exists a walk labeled w from the start stateto final state.42.3 NFA vs. DFA: Which is more powerful?Example:q0 q2q1aabbTheorem Given an NFA MN=(QN, Σ,δN,q0,FN), then there exists a DFA MD=(QD, Σ,δD,q0,FD)suchthat L(MN)=L(MD).Proof:We need to define MDbased on MN.QD=FD=δD:Algorithm to construct MD1. start state is {q0}2. While can add an edge(a) Choose a state A={qi,qj, ...qk} with missing edge for a ∈ Σ(b) Compute B = δ∗(qi,a)∪δ∗(qj,a)∪...∪δ∗(qk,a)(c) Add state B if it doesn’t exist(d) add edge from A to B with label a3. Identify final states4. if λ ∈ L(MN) then make the start state final.5Example:q0q1 q3 q5q2 q4q6abaabλλλMinimizing Number of states in DFAWhy?Algorithm• Identify states that are indistinguishableThese states form a new stateDefinition Two states p and q are indistinquishable if for all w ∈ Σ∗δ∗(q, w) ∈ F ⇒ δ∗(p, w) ∈ Fδ∗(p, w) 6∈ F ⇒ δ∗(q, w) 6∈ FDefinition Two states p and q are distinquishable if ∃ w ∈ Σ∗s.t.δ∗(q, w) ∈ F ⇒ δ∗(p, w) 6∈ F ORδ∗(q, w) 6∈ F ⇒ δ∗(p, w) ∈ F6Example:abbaababbabbaaAB CDEFG7Example:baabbaaAB
View Full Document