Automata Theory free essay sample

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 NFAs are more expressive than DFAs, we will see that adding nondeterminism does not let us define any language that cannot be defined 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. 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 goods and redeem the electronic money with the bank. The bank may transfer any redeemed money 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 pay b ship redeem ship redeem transfer Store Pay Cancel Redeem 3 Transfer 4 Start Customer Bank 2 Ignoring Actions The automata only describes actions of interest To be more precise, with a DFA (deterministic finite automaton) we should specify arcs for all possible inputs. 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 s follows for the bank automaton. Complete Bank Automaton Cancel Transfer, Pay, Ship Redeem, Pay, Ship, Cancel Redeem, Transfer, Pay, Ship, Cancel 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. The product automaton creates a new state for all possible states of each automaton. Since the customer automaton only has one state, e only need to consider the pair of states between the bank and the store. For example, we start in state (a,l) 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,l) if the store receives a pay. To construct the product automaton, we run the bank and store automaton in parallel using all possible inputs and creating an edge on the product automaton to the corresponding set of states. Product Automaton start pcc sc d 1234 RS PRS TTS 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 us to see if potential 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 doesnt die which is why t 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 the front and toward the rear, but not allow someone to walk the other direction: Rear Pad 5 One Way Door Lets assign the following codes to our different input cases: a Nobody on either pad b Person on front pad c Person on rear pad d Person on front and rear pad We can design the following automaton so that the door doesnt open if someone is still on the rear pad and hit them: a,c,d b b,c,d c o Formal Definition of a Finite Automaton 1 . Finite set of states, typically Q. 2. Alphabet of input symbols, typically 3. One state is the startlinitial state, typically qO // qO e Q 4. Zero or more final/accepting states; the set is typically F. // F C Q 5. A transition function, typically . This function Takes a state and input symbol as arguments. 6 One Way Door Formal Notation Using our formal notation, we have: Q = {C, O} (usually well use qO and ql instead) F 0 There is no final state This is the start state qO = C = {a,b,c,d} The transition function, 6 , can be specified by the table: a C C O C b O Oc 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. Exercise Using ={O,1}a clamping circuit waits for a 1 input, and forever after makes a 1 output regardless of the input. However, to avoid clamping on spurious noise, design a DFA that s waits for two 1 in a row, and clamps only then. Write the transition unction in table format as well as graph format. 7 Let M = (Q, , ,qO, F) be a finite automaton and let w = w1w2 wn be a string where each wi is a member of alphabet . Ђ M accepts w if a sequence of states rorl rn in Q exists with three conditions: 1. qO 2. (ri, wi+l) = ri+l for 1=0, , n-1 3. rn e F We say that M recognizes language A if A = {w I 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 Os and Is whose numbers of Os and Is are both even: 1 Start O 10010 ql 8 Aside: Typ e Errors A major source of confusion when dealing with automata (or mathematics in general) is making type errors. Donconfuse A, a FA, i. e. , a program, with L(A), t which is of type set of strings. The start state qO 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 Exercise The following figure below is a marble-rolling toy. A marble is dropped at A or B. Levers xl, 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 this game by a finite automaton. Let acceptance correspond to the marble exiting at D. Non- acceptance represents a marble exiting at C. 9 Marble Rolling Game 13 12 Marble Game Notation The inputs and outputs (A-D) become the alphabet of the automaton, while the levers indicate the possibl e states. If we define the initial status of each lever to be a O, then if the levers change direction they are in state 1. Lets use the format xlx2x3 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 for rejection. 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. 10 Messy Marble DFA ooor A loor OilrA BABBA OloaA 101rB -romorT0111rB 111rA ooa A Olor A 001 a oooa A 1 lor AB Marble DFA Table Format Easier to see in table format. Note that not all states are accessible. A B -OOOr 100r *oooa loor 01 Ir *001a 101roooa Olor 1 lor 001a *Oloa 1 lor 001a 01 Ir 11 Ir moa loor Olor 11 Ir *looa Olor 11 Ir 101r 01 Ir looa *101a 01 Ir looa 1 lor oooa 101a *Iloaoooa Iloa 11 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 The union of two languages L and M is the set of strings that are in both L and M. Example: if L = {0, 1} and M then LU M {0, 1, 111}. 2. 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 well use LM (pronounced dot). Example, if L = {0, 1} and M = { , 010} then LM {0, 1, 0010, 1010}. set of strings that can be formed by taking any number of strings from L with repetition and concatenating them. It is a unary operator. More specifically, LO is the et we can make selecting zero strings from L. LO is always {}. Ll 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 LO, L 1, L2, Lm For example, if 10} then Ll 10} 010, 100, 1010} 0010, 0100, 01010, 10010, 1000, 10100, 101010} and L* the unton of all these sets, up to 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 wont be using the closure properties extensively here; consequently we will state the theorems and give some examples.