Automata Theory

Two sorts – each describe what are known as regular languages – Deterministic (DFA) – There is a onerous and fast variety of states and we are in a position to solely be in one state at a time – Nondeterministic (NFA) -There is a exhausting and fast number of states but we could be in multiple states at one time While NFA’s are extra expressive than DFA’s, we are going to see that adding nondeterminism doesn’t allow us to define any language that can’t be defined by a DFA. One means to consider that is we would write a program using a NFA, however then when it’s “compiled” we turn the NFA into an equivalent DFA.

Informal Example ? Customer buying at a store with an digital transaction with the bank – The customer could pay the e-money or cancel the emoney at any time. – The store may ship goods and redeem the digital money with the bank. – The financial institution could switch any redeemed cash to a special get together, say the shop. Can mannequin this problem with three automata Bank Automata Actions in daring are initiated by the entity.

Otherwise, the actions are initiated by another person and obtained by the required automata Start pay b ship redeem ship redeem transfer Store Pay Cancel Redeem 3 Transfer four Start Customer

Bank 2 Ignoring Actions The automata solely describes actions of interest – To be more precise, with a DFA (deterministic finite automaton) we should specify arcs for all potential inputs. – E. g. , what should the client automaton do if it receives a “redeem”? – What should the bank do if it is in state 2 and receives a “redeem”? The typical habits if we receive an unspecified action is for the automaton to die.

– The automaton enters no state at all, and additional action by the automaton could be ignored. The finest technique although 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 might be acquired Entire System as Automaton When there are multiple automata for a system, it’s useful to incorporate all the automata right into a single one in order that we are ready to higher perceive the interplay.

Called the product automaton. The product automaton creates a brand new state for all attainable states of each automaton. Since the shopper automaton only has one state, e solely need to contemplate the pair of states between the bank and the shop. – For instance, we start in state (a,l) where the store is in its begin state, and the financial institution is in its start state. From there we will transfer to states (a,2) if the bank receives a cancel, or state (b,l) if the store receives a pay.

To assemble the product automaton, we run the financial institution 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 might help validate our protocol. ? It tells us that not all states are reachable from the beginning state. – For example, we should never be in state (g, 1) the place we’ve shipped and transferred money, but the bank continues to be waiting for a redeem. It permits us to see if potential errors can occur. We can reach state (c, 2). This is problematic because it permits a product to be shipped however the cash has not been transferred to the shop. – In contrast, we will see that if we reach state (d, 3) or (e, 3) then the store ought to be okay – a switch from the financial institution must happen assuming the financial institution automaton doesn’t “die” which is why t is beneficial to add arcs for all possible inputs to finish the automaton Simple Example – 1 method 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 need individuals to stroll through the front and towards the rear, but not enable someone to stroll the other direction: Rear Pad 5 One Way Door Let’s assign the following codes to our different enter circumstances: a – Nobody on both 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 doesn’t open if somebody 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, usually Q. 2. Alphabet of enter symbols, usually 3.

One state is the startlinitial state, usually qO // qO e Q four. Zero or extra final/accepting states; the set is often F. // F C Q 5. A transition operate, sometimes . This operate Takes a state and input image as arguments. 6 One Way Door – Formal Notation Using our formal notation, we have: Q = {C, O} (usually we’ll use qO and ql instead) F zero There is not any last state This is the beginning state qO = C = {a,b,c,d} The transition function, 6 , may be specified by the table: a C C O C b O Oc C O c C O Write each (state,symbol)?

The begin state is indicated with the If there are last 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 whatever the input. However, to avoid clamping on spurious noise, design a DFA that s waits for 2 1′ in a row, and “clamps” only then. Write the transition unction in table format in addition to graph format. 7 Let M = (Q, , ,qO, F) be a finite automaton and let w = w1w2… wn be a string where every 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 three. rn e F We say that M recognizes language A if A = {w I M accepts w} In other phrases, the language is all of these strings which might be accepted by the finite automata. DFA Example Here is a DFA for the language that’s the set of all strings of O’s and I’s whose numbers of O’s and I’s are both even: 1 Start O 10010 ql 8 Aside: Type Errors A main supply of confusion when dealing with automata (or mathematics in general) is making “type errors. Don’confuse A, a FA, i. e. , a program, with L(A), t which is of type “set of strings. ” The begin state qO is of type “state,” but the accepting states F is of type “set of states. ” a could be an emblem or a might be a string of length 1 relying on the context DFA Exercise The following determine beneath 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 proper. Whenever a marble encounters a lever, it causes the lever to reverse after the marble passes, so the subsequent marble will take the alternative 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 thirteen 12 Marble Game Notation The inputs and outputs (A-D) become the alphabet of the automaton, whereas the levers indicate the possible states. If we outline the preliminary status of every lever to be a O, then if the levers change path they are in state 1. Let’s use the format xlx2x3 to point a state. The preliminary state is 000. If we drop a marble down B, then the state turns into to 011 and the marble exits at C.

Since we have three levers that can tackle binary values, we have 8 attainable states for levers, 000 to 111. Further determine the states by appending an “a” for acceptance, or “r” for rejection. This leads to a complete of 16 attainable states. All we need to do is start from the preliminary 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 eleven Ir moa loor Olor 11 Ir *looa Olor eleven Ir 101r 01 Ir looa *101a 01 Ir looa 1 lor oooa 101a *Iloaoooa Iloa 11 Regular Operations Brief intro right here – will cowl extra on common expressions shortly In arithmetic, we have arithmetic operations – + * / and so forth. 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 which are in each 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 might be shaped by taking any string in L and concatenating it with any string in M. Concatenation is denoted by LM although sometimes we’ll use LM (pronounced “dot”). Example, if L = {0, 1} and M = { , 010} then LM {0, 1, 0010, 1010}. set of strings that can be fashioned by taking any number of strings from L with repetition and concatenating them. It is a unary operator. More particularly, LO is the et we are able to make selecting zero strings from L. LO is all the time {}. 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 instance, if 10} then Ll 10} 010, a hundred, 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 brand new language that’s of the same “type” as these originally operated on – i. e. , regular in our case ? We won’t be utilizing the closure properties extensively here; consequently we’ll state the theorems and give some examples.