Unformatted text preview:

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

Duke CPS 140 - Lecture

Download Lecture
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?