advertisement

Finite Automata • Two types – both describe what are called regular languages – Deterministic (DFA) – There is a fixed number of states and we can only be in one state at a time – Nondeterministic (NFA) –There is a fixed number of states but we can be in multiple states at one time • While NFA’s are more expressive than DFA’s, we will see that adding nondeterminism does not let us define any language a guage that a cannot ca o be defined de ed by a DFA.. • One way to think of this is we might write a program using a NFA, but then when it is “compiled” we turn the NFA into an equivalent DFA. DFA Informal Example • Customer shopping at a store with an electronic transaction with the bank – The customer may pay the e-money or cancel the emoney at any time. – The store may ship hi goods and redeem d the electronic money with the bank. – The bank mayy transfer f anyy redeemed moneyy to a different party, say the store. • Can model this problem with three automata Bank Automata Actions in bold are initiated by the entity. Otherwise, the actions are initiated by someone else and received by the specified automata Start a pay b ship Store c redeem transfer d ship redeem f ship transfer e g Cancel 2 Pay Cancel 1 Start Customer Start Bank Redeem 3 Transfer 4 Ignoring Actions • The automata only describes actions of interest – To be more precise, with a DFA (deterministic finite automaton) p y arcs for all possible p inputs. p we should specify – E.g., what should the customer automaton do if it receives a “redeem”? – What should the bank do if it is in state 2 and receives a “redeem”? • The typical behavior if we receive an unspecified action is for the automaton to die. – The automaton enters no state at all, and further action by the automaton would be ignored. – The best method though is to specify a state for all behaviors, as indicated as follows for the bank automaton. Complete Bank Automaton Redeem, Transfer, Pay, Ship, Cancel 2 Redeem, Pay, Ship, Cancel Cancel Transfer, Pay, Ship 1 Redeem 3 Redeem, Transfer, Pay, Ship, Cancel Transfer 4 Start Bank Ignores other actions that may be received Entire System as Automaton • • • When there are multiple automata for a system, it is useful to incorporate all of the automata into a single one so that we can better understand the interaction. Called the product automaton. automaton The product automaton creates a new state for all possible states of each automaton. Since the customer automaton only has one state, we only need to consider the pair of states between the bank and the store. – For example, we start in state (a,1) where the store is in its start state, and the bank is in its start state. From there we can move to states (a,2) if the bank receives a cancel, or state (b,1) if the store receives a pay. • To construct the product automaton, we run the bank and store automaton “in “i parallel” ll l” using i all ll possible ibl inputs i andd creating i an edge d on the product automaton to the corresponding set of states. Product Automaton start a b P 1 C c d e f g S C C R 2 S P R 3 S T 4 T S Product Automaton • How is this useful? It can help validate our protocol. • It tells us that not all states are reachable from the start state. – For example, we should never be in state (g,1) where we have shipped and transferred cash, but the bank is still waiting for a redeem. • It allows ll us to t see if potential t ti l errors can occur. – We can reach state (c, 2). This is problematic because it allows a product to be shipped but the money has not been transferred to the store. – In contrast, we can see that if we reach state (d, 3) or (e, 3) then the store should be okay – a transfer from the bank must occur • assuming the bank automaton doesn’t “die” which is why it is useful to add arcs for all possible inputs to complete the automaton Simple Example – 1 way door • As an example, consider a one-way automatic door. This door has two pads that can sense when someone is standing on them, a front and rear pad. We want people to walk through g the front and toward the rear, but not allow someone to walk the other direction: Front Pad Rear Pad One Way Door • • Let’s assign the following codes to our different input cases: a - Nobody on either pad b - Person on front pad p c - Person on rear pad d - Person on front and rear pad We can design the following automaton so that the door doesn doesn’tt open if someone is still on the rear pad and hit them: a,c,d Start b C b,c,d O a Formal Definition of a Finite Automaton 1. 2. 3. 4. 5. Finite set of states, typically Q. Alphabet of input symbols, typically ∑ One state is the start/initial state, typically q0 // q0 ∈ Q Zero or more final/accepting states; the set is typically F. // F ⊆ Q A transition function, typically δ. This function • • • • Takes a state and input symbol as arguments. Returns a state state. One “rule” would be written δ(q, a) = p, where q and p are states, and a is an input symbol. Intuitively: if the FA is in state q, and input a is received, then the FA goes to state p (note: q = p OK). OK) 6. A FA is represented as the five-tuple: A = (Q, ∑, δ,q0, F). Here, F is a set of accepting states. One Way Door – Formal Notation Using our formal notation, we have: Q = {C, O} (usually we’ll use q0 and q1 instead) F = {} There is no final state q0 = C This hi is i the h start state ∑ = {a,b,c,d} The transition function, δ , can be specified by the table: a ÆC C O C b O O c C O c C O Write each δ(state,symbol)? The start state is indicated with the Æ If there are final accepting states, that is indicated with a * in the proper row. Formal Definition of Computation • Let M = (Q, ∑, δ,q0, F) be a finite automaton and let w = w1w2…wn be a string g where each wi is a member of alphabet ∑. • M accepts p w if a sequence q of states r0r1…rn in Q exists with three conditions: 1. r0 = q0 2. δ(ri, wi+1) = ri+1 for i=0, … , n-1 3. rn ∈ F We say that M recognizes language A if A = {w | M accepts w } In other words, the language is all of those strings that are accepted by the finite automata. DFA Example • Here is a DFA for the language that is the set of all strings of 00’ss and 1’s whose numbers of 00’ss and 11’ss are both even: 1 Start q0 q1 1 0 0 0 0 1 q2 q3 1 Aside: Type Errors • A major source of confusion when dealing with automata (or mathematics in general) is making “type errors." errors " • Don't confuse A, a FA, i.e., a program, with L(A), which is of type “set set of strings. strings." • The start state q0 is of type “state," but the accepting states F is of type “set of states." • a could be a symbol or a could be a string of length 1 depending on the context DFA Example • The following figure below is a marble-rolling toy. A marble is dropped at A or B. Levers x1, x2, and x3 cause the marble to fall either to the left or to the right. Whenever a marble encounters a lever,, it causes the lever to reverse after the marble passes, so the next marble will take the opposite branch. • Model M d l this thi game by b a finite fi it automaton. t t Let L t acceptance correspond to the marble exiting at D. Non-acceptance p represents p a marble exiting g at C C. Marble Rolling Game A B x1 x3 x2 C D Marble Game Notation • • • • • • The inputs and outputs (A-D) become the alphabet of the automaton, while the levers indicate the possible states. If we define the initial status of each lever to be a 0, then if the levers change direction they are in state 1. 1 Let’s use the format x1x2x3 to indicate a state. The initial state is 000. If we drop a marble down B, then the state becomes to 011 and the marble exits at C. Since we have three levers that can take on binary values, we have 8 possible states for levers, 000 to 111. Further identify the states by appending an “a” for acceptance, or “r” o rejection. ejec o . for This leads to a total of 16 possible states. All we need to do is start from the initial state and draw out the new states we are led to as we get inputs from A or B. Messy Marble DFA A Start 000r B A 100r B A A 000a A B 111r A A 010r 011r B 001a B A B A 110a B B 101a B B 100a 101r B A To 010r To 111r A A B 110r A 010a B Marble DFA – Table Format • Easier to see in table format. Note that not all states are accessible. A B ->000r 100r 011r *000a 000a 100r 011r *001a 101r 000a 010r 110r 001a *010a 110r 001a 011r 111r 010a 100r 010r 111r *100a 010r 111r 101r 011r 100a *101a 011r 100a 110r 000a 101a *110a 000a 101a 111r 001a 110a Regular Operations • Brief intro here – will cover more on regular expressions shortly • In arithmetic, we have arithmetic operations – + * / etc. • For finite automata, we have regular operations – Union – Concatenation – Star Algebra for Languages 1. The union of two languages L and M is the set of strings that are in both L and M. • 2. Example: if L = { 0, 1} and M = {111} then L ∪ M is {0, 1, 111}. The concatenation of languages L and M is the set of strings that can be formed by taking any string in L and concatenating it with any string in M. Concatenation is denoted by LM although sometimes we’ll use L•M (pronounced “dot”) dot ). • Example, if L = {0, 1} and M = {ε, 010} then LM is { 0, 1, 0010, 1010}. Algebra g for Languages g g 3. The closure, star, or Kleene star of a language L is denoted L* and represents the set of strings that can be formed by taking any number of strings from L p and concatenatingg them. It is a unaryy operator. p with repetition More specifically, L0 is the set we can make selecting zero strings from L. L0 is always { ε }. L1 is the language consisting of selecting one string from L. L2 is the language consisting of concatenations selecting two strings from L. … L* is the union of L0, L1, L2, … L∞ For example, if L = {0 , 10} then L0 = { ε }. L1 = {0, 10 } L2 = {00, 010, 100, 1010} L3 = {000, 0010, 0100, 01010, 10010, 1000, 10100, 101010} … and L L* is the union of all these sets sets, up to infinity infinity. Closure Properties of Regular Languages • Closure refers to some operation on a language, resulting in a new language that is of the same “type” as those originally operated on – i.e., regular in our case • We won’t be using the closure properties extensively here; consequently we will state the theorems and give some examples. l See S the th book b k for f proofs f off the th theorems. th • The regular languages are closed under union, concatenation, and *. I.e., if A1 and A2 are regular l languages then th – A1 ∪ A2 is also regular – A1A2 is also regular – A1* is also regular Later we’ll see easyy ways y to prove the theorems Nondeterministic Finite Automata • A NFA ((nondeterministic finite automata)) is able to be in several states at once. – In a DFA, we can only take a transition to a single deterministic state – In a NFA we can accept multiple destination states for the same input. – You can think of this as the NFA “guesses” something about its input and will always follow the proper path if that can lead to an accepting state. paths and – Another way to think of the NFA is that it travels all possible paths, so it remains in many states at once. As long as at least one of the paths results in an accepting state, the NFA accepts the input. • NFA is a useful tool – More expressive than a DFA. – BUT we will see that it is not more powerful! For any NFA we can construct a corresponding DFA – Another way to think of this is the DFA is how an NFA would actually be implemented (e.g. on a traditional computer) NFA Example • This NFA accepts only those strings that end in 01 01 0,1 0 q0 Start 1 q1 q0 • Running in “parallel threads” for string 1100101 q0 1 1 q0 0 q0 q1 - stuck 0 1 q0 q1 q0 q2 - stuck 0 q0 q1 q0 q2 - accept 1 q2 Formal Definition of an NFA • Similar to a DFA 1. Finite set of states, typically Q. 2. Alphabet of input symbols, typically ∑ 3. One state is the start/initial state, typically q0 4. Zero or more final/accepting states; the set is typically F. 5. A transition function, typically δ . This function: • Takes a state and input symbol as arguments. • Returns a set of states instead of a single state, state as a DFA 6. A FA is represented as the five-tuple: A = (Q, ∑, δ ,q0, F). Here, F is a set of accepting states. Previous NFA in Formal Notation The previous NFA could be specified formally as: ({q0,q q1,q q2}, } {0,1}, {0 1} δδ, q0, {q2}) The transition table is: 0 Æ q0 {q0,q1} q1 Ø * q2 Ø 1 {q0} {q2} Ø Formal Definition of an NFA • Same idea as the DFA • Let L N = (Q, (Q ∑, ∑ δ,q δ 0, F) bbe an NFA and d llet w = w1w2…wn be a string where each wi is a member of alphabet ∑. • N accepts w if a sequence of states r0r1…rn in Q exists with three conditions: 1. r0 = q0 2. ri+1 ∈ δ(ri, wi+1) for i=0, … , n-1 3 rn ∈ F 3. Observe that δ(ri, wi+1) is the set of allowable next states We say that N recognizes language A if A = {w | N accepts w } Equivalence of DFA’s and NFA’s • For most languages, NFA’s are easier to construct than DFA’s • But it turns out we can build a corresponding DFA for any NFA – The downside is there may be up to 2n states in turning a NFA into a DFA However, DFA. However for most problems the number of states is approximately equivalent. • Theorem: A language L is accepted by some DFA if and only if L is accepted by some NFA; i.e. i e : L(DFA) = L(NFA) for an appropriately constructed DFA from an NFA. – Informal Proof: It is trivial to turn a DFA into an NFA (a DFA is already an NFA without nondeterminism) nondeterminism). The following slides will show how to construct a DFA from an NFA. NFA to DFA : Subset Construction Let an NFA N be defined as N = (QN, ∑, δ N,q0, FN). The equivalent DFA D = (QD, ∑,δD , {q0 }, FD) where: 1. QD = 2Qn ; i.e. QD is the set of all subsets of QN; that is, it is the power set of QN. Often, not all of these states are accessible from the start state; these states may be “thrown away.” 2 FD is 2. i the th sett off subsets b t S off QN such h that th t S ∩ FN ≠ Ø. Ø Th Thatt is, i FD is i all ll sets t off N’s N’ states that include at least one accepting state of N. 3. For each set S ⊆ QN and for each input symbol a in ∑: δ D ( S , a ) = U δ N ( p, a ) p∈S That is,, to compute p δD((S,, a)) we look at all the states p in S,, see what states N goes to starting from p on input a, and take the union of all those states. Subset Construction Example (1) 0,1 • Consider the NFA: q0 Start The power set of these states is: { Ø, Ø {q0}, } {q1}, } {q2}, {q0, q1}, {q0, q2},{q1, q2}, {q0, q1, q2} } New transition function with all of these states and go to the set of possible inputs: 0 1 q1 0 1 Ø Ø Ø Æ {q0} {q0, q1} {q0} {q1} Ø {q2} *{ 2} *{q Ø Ø {q0, q1} {q0, q1} {q0, q2} *{q0, q2} {q0, q1} {q0} *{q1, q2} Ø {q2} *{q0, q1, q2} {q0, q1} {q0, q2} q2 Subset Construction (2) • Many states may be unreachable from our start state. A good way to construct the equivalent DFA from an NFA is to start with the start states and construct new states on the fly as we reach them. 0 Ø {q0, q1} {q0, q1} {q0, q1} Ø Æ {q0} {q0, q1} *{q0, q2} 1 Ø {q0} {q0, q2} {q0} 1 0 Graphically: Start {q0} 0 {q0, q1} 1 1 0 {q0,q2} NFA to DFA Exercises a • Convert the following NFA’s to DFA’s Start q0 a,b b 15 possible states on this second one (might be easier to represent in table format) q1 Corollary • A language is regular if and only if some nondeterministic finite automaton recognizes it • A language is regular if and only if some deterministic finite automaton recognizes it Epsilon Transitions • Extension to NFA – a “feature” called epsilon transitions, denoted by ε, the empty string • The ε transition lets us spontaneously take a transition, without receiving an input symbol • Another mechanism that allows our NFA to be in multiple l i l states at once. – Whenever we take an ε edge, we must fork off a new “thread” for the NFA startingg in the destination state. • While sometimes convenient, has no more power than a normal NFA – Just as a NFA has no more power than a DFA Formal Notation – Epsilon Transition • Transition function δ is now a function that takes as arguments: g – A state in Q and – A member of ∑ ∪ {ε}; that is, an input symbol or the symbol ε. We require that ε not be a symbol of the alphabet ∑ to avoid any confusion. Epsilon NFA Example 0 Start q 1 r ε s ε 0 1 In this ε-NFA, the string “001” is accepted by the path qsrqrs, where the first qs matches 0, sr matches ε, rq matches 0, qr matches 1, 1 and then rs matches ε. ε In other words, words the accepted string is 0ε0ε1ε. Epsilon Closure • Epsilon closure of a state is simply the set of all states we can reach by following the transition function from the given state that are labeled εε. 0 Example: Start q 1 r ε s ε 0 1 • • ε closure(q) = { q } ε-closure(q) ε-closure(r) = { r, s} Eliminating g Epsilon p Transitions To eliminate ε-transitions, use the following to convert to a DFA: 1. Compute ε-closure for the current state, resulting in a set of states S. 2. δD(S,a) is computed for all a in Σ by a. Let S = {p1, p2, … pk} k b. Compute U δ ( p , a) and call this set {r1, r2, r3 … rm} i This set is achieved i =1 by following input a, not by following any ε-transitions m c. Add the ε-transitions in by computing δ ( S , a) = U ε − closure(ri ) i =1 3. Make a state an accepting state if it includes any final states in the ε-NFA. In simple terms: Just like converting a regular NFA to a DFA except follow the epsilon transitions whenever possible after processing an input Epsilon Elimination Example 0 Start q 1 r ε s ε 0 1 Converts to: Start q 0,1 , 01 0,1 sr