Subject Notes €3501- Theory of Computation B.Tech, CSE-5" Semester Syllabus: Introduction of Automata Theory: Examples of automata machines, Finite Automata as a language acceptor and translator, Moore machines and mealy machines, composite machine, Conversion from Mealy to Moore and vice versa. Unit- Introduction of Automata Theory Eee Automata” The term "Automata’ is derived from the Greek rc ARTERY means "self-acting". An automaton TAutomata in plural) is an abstract self-propelled computing device which follows a predetermined sequence of operations automatically. Automata are computational devices to solve language recognition problems. Language recognition problem is to determine whether 2 word belongs to a language. Automaton = abstract computing device, or “machine” ae) \ Figure 1. Putational Model of Automata Theory Examples of automata machines: aa—-_seteeer="’™r- Sequential machine: A sequential machine is a mathematical model of a certain type of simple ‘computational structure. Its behavior represents the working process of finite Automata * Vending Machines: A vending machine is an automated machine that dispenses numerous items such as cold drinks, snacks, beverages, alcohol ete. Vending machine is works on finite state automate to control the functions process. 2 Traffic Lights: The optimization of traffic light controllers in a city is a systematic representation of handling the instructions of traffic rules(Its process depends on a set of instruction works in a loop with syitching among instruction to contrl tafe ete aren ges vl rrr oes of stom nich sagen fiction is followed by Me players to accomplish the task. ‘Text Parsing: Text parsing is a technique which is used to derive a text string using the production rules of a grammar to check the acceptability of a string. ‘© Regular Expression Matching: It is @ technique to checking the two or more regular expression are similar to each other or not. The finite state machine is useful to checking out that the expressions are acceptable or not by a machine or not. ‘* Speech Recognition: Speech recognition via machine is the technology enhancement that is capable to identify words and phrases in spoken language and convert them to a machine-readable format.Receiving words and phrases from real world and then converted it into machine readable language automatically is effectively solved by using finite state machine. Characteristics: Fas having only a finite number of states. * Finite Automata can only "count" (that is, maintain a counter, where different states correspond to different values of the counter) a finite number of input scenarios. Able to solve limited set of problem Outcome in the form of “yes “or "No" (Accept / Reject) \ upsenon There is no finite automaton that recognizes these strings: ‘© The set of binary strings consisting of an equal number of 1's and 0's The set of strings over '' and ')' that have "balanced" parentheses. pplications of TOC: Finite State Programming ‘+ Event Driven Finite State Machine ( © Virtual FSM ‘+ DFA based text filter in Java ‘+ Acceptors and Recognizers Transducers UML state diagrams Hardware Applicatio Finite Automata: An automaton with a finite number of states is called a Finite Automaton (FA) or Finite State Machine (FSM). ‘An automaton has a mechanism to read input, which is string over a given alphabet. This input is actually written on an input tape /file, which can be read by automaton but cannot change it. Input file is divided into cells each of which can hold one symbol. Automaton has a control unit which is said to be in one of finite number of internal states Input tape Finite“ a control yg, Sue ds Figure 1.2: Finite Automata Formal definition of Finite Automata: A finite automaton is a 5-tuple M = (Q, £, 6, q, F), whereisa finite set, called the alphabet; the elements of 8 are called symbols, 65:09 O's funtion, called the transition funtion, ee an element of Q; itis called the start state or initial state, AF i “2 is a finite set, whose elements are called states, 4S i a subset of Q; the elements of F are called accept states or final state. Related Terminologies: Alphabet: An alphabet is any finite set of symbols. Example: 2 = {a, b, ¢, dhis an alphabet set where ‘a, ‘b’,‘c, and d’ are symbols. String: A string is a finite sequence of symbols taken from &. Example: ‘cabcad’ is a valid string on the alphabet set Z = {a, b, ¢, d} Length of a String: itis the number of symbols present in a string. (Denoted by |S) Examples: If S=/cabcad’, |S|= 6 IF Isl= itis called an empty string (Denoted by A or €} Language: A language is a subset of 3* for some alphabet 3. It can be finite or infinite, Example: Ifthe language takes all possible strings of length 2over I= (2, b), then L= (ab, bb, ba, bb} Classification of Finite Automata: Finite Automata With Output ——— ———_ Mealy | Moore Epsilon Machine | Machine oe | nes | NFA Figure 13: ‘An example of finite automata Let A = {w: wis a binary string containing an odd number of 1s}.We claim that this language A is regular. In order to prove this, we have to construct a finite automaton M such that A =L(M). Steps to construct finite automata: ‘+The FA reads the input string w from left to right and keep scanning on the number of 1’s + After scanning the entire string, it counts the number of 1's to check whether it is odd or even ‘+ Ifthe number of 1’s is odd then the string is acceptable otherwise itis rejected Using this approach, the finite automaton needs a state for every integer i2 0; indicating that the number of 1 read so far is equal to I. Hence, to design 2 finite automaton that follows this approach, we need an infinite number of states. But, the definition of finite automaton requires the number of states to be finite, A better, and correct approach, is to keep track of whether the number of 1s read so far is even or odd, This leads to the following finite automaton: * The set of states is Q = (qo, qi} Ifthe finite automaton is in state qi, then it has an even number of 1’; fit is in state gO, then it has an odd number of 1's. + The alphabet is = (0, 1}. + The start state is 90, because at the start, the number of 1's read by the automaton is equal to 0, and Ois even The set F of accept state: (a1). + The transition function 6 is given by the following table: % qo a a a qe Table 1.1: Transition Table/Matrix This finite automaton M = (Q, Z, 6, qo, F} can also be represented by its state diagram. Figure 1.4: Transition Graph Transition Graph: itis a finite directed labeled graph in which each vertex (or node) represent a state and the directed edges indicate the transition of state. Edges are labeled with input symbol, Transition Matrix: It is two-dimension matrixes between states of automata and Input symbol. Elements of matrix are state form mapping (2 X Q) into Q. Finite state acceptors 2 finite state machine with no outputs. The user of a finite state acceptor cares only about the final state: if the machine ends in an accepting state after processing a series of inputs, the machine is said to have accepted the input; otherwise, itis said to have rejected the inputDescription of Finite-State Machines using Graphs Any finite-state machine can be shown as a graph with a finite set of nodes. The nodes correspond to the states. There is no other memory implied other than the state shown. The start state is designated with an arrow directed into the corresponding node, but otherwise unconnected. Figure 1.5: An unconnected in-going arc indicates that the node is the start state The arcs and nodes are labeled differently, depending on whether we are representing a transducer, a classifier, or an acceptor. In the case of a transducer, the arcs are labeled as shown below, where ql is the input symbol and q2 is the output symbol. The state- transition is designated by virtue of the arrow going from one node to another. (4) = () Figure 1.6: Transducer tran: jon from q to q,, based on input 6, ing output 2 In the case of an acceptor, instead of labeling the states with ¢ategories 0 and 1, we sometimes use 2 double-lined node for an accepting state and a single-lined node for a rejecting state. Figure 1.7: Acceptor, an accepting state Acceptor Example Let us give an acceptor that accepts those strings with exactly one edge. We can use the state transitions from the previous classifier. We need only designate those states that categorize there being one edge as accepting states and the others as rejecting states. Figure 1.8: Acceptor for strings with exactly one edge. Accepting states are d and e. Examples for Practice Problem-01: Draw a DFA for the language accepting strings starting with ‘ab’ over input alphabets 5 = {a, b} Solution-Regular expression for the given language = ab (a +b)* Step-O1: All strings of the language start with substring “ab”. So, length of substring = 2. Thus, Minimum number of states required in the DFA = 242 = 4It suggests that minimized DFA will have 4 states Step-02: We will construct DFA for the following strings- ‘Ab, aba, abab Step-03: The required DFA is- <>. ate DFA Figure 1.9: Transition Graph Problem-02: Draw a DFA for the language accepting strings starting with ‘a’ over input alphabets 5 = (a, b} Solution-Regular expression for the given language = afa + b)* Step-O1: All strings of the language starts with substring “a’’ So, length of substring = 1 Thus, Minimum number of states required in the DFA = It suggests that minimized DFA will have 3 states. Step-02: We will construct DFA for the following strings- Aca ‘Step-03: The required OFA is- 4253, DFA Figure 1.10: Transition Graph Problem 3: Construct a minimal DFA, which accepts set of all strings over {0, 1}, which when interpreted as binary number is divisible by ‘3'.Means 110 in binary is equivalent to 6 in decimal and 6 is divisible by 3. ‘Answer So if you think in the way of considering remainders if you divide by 3 that is {0, 1, 2}a0 mt 1000 Figure 1.11: Transition Graph ‘As you can see that binary number which is divisible by 2 is appearing on left state. Short Trick to create such DFAS Create Transition Table as below Table creation rules State 0 1 qo 90 cy a 2 90 2 a 2 a Ag 9 First write the input alphabets, example, 1 There will n states for given nutiber which is divisor. Start writing states/as for n=3°q0 under 0, q1 under 1 2 under 0 and dOunder 1 Qlunder O and q2 under 1 If the input alphabets are 0, 1, 2°then table will expand accordingly with same rules above. Example For ternary pattern and n=4, table will be as follows; yvvvy State oO 1 2 @ wo gt a Bo @ a 2 2 9 B a a2 @B Mealy and Moore Machine: These machines are modeled to show transition and output symbol. These machines do not define a language by accepting or rejecting input string, so there is no existence of final state. Finite automata generate outputs related to each act. While two types of finite state machines create output - . Mealy Machine . Moore machine ~Wealy Machine:‘A Mealy Machine is considered as an FSM, the output will be based on the present state and the present input. ‘Mealy machine is explained as a 6 tuple (Q, 5, 0, 6, X, q0) where — Qis a finite set of states. isa finite set of symbols called the input alphabet. isa finite set of symbols called the output alphabet. 6 is the input transition function where 6: Qx5>Q Xi the output transition function where X:Qx 50 Dis the initial state from where any input is processed (q0 € Q). The state table of a Mealy Machine is mentioned below ~ Present state Next state | input =0 jinput=2 | State Output | State Output Fa | b x | © x b | b % | d % © | d x | c x | x Figure 1.12: Transition Graph «Moore Machine Moore machine is also considered as an FSM and the outputs depend on the present state. ‘A Moore machine is also explained by a 6 tuple (Q, 5, 0,8, X, a0) where ~ isa finite set of states. isa finite set of symbols called the input alphabet. isa finite set of symbols called the output alphabet. 5 is the input transition function where 5: Qx5 > Q Xis the output transition function where X: > 0. * qQis the initial state from where any input is processed (q0 € Q). The state table of a Moore Machine is shown below ~ Present state Next State OutputInput = 0 Input = 1 Figure 1.13: Transition Graph Composite finite-state machines: A finite state machine, FSM, is a box with C input/output channels, and S states, and a fixed map f:SxC->SxCLDF:SxC->SxCUD. If a state (ci,s)) (ci,s)) is mapped to the 0 element it means it enters a loop and can’t exit. if we join the channels of several FSM's pair wise, we obtain a new FSM, i.e. we get a system with some number of un-joined channels, C, and internal states given by the product of the number of internal states of each component FSM, S.A composite FSM is allowed to have internal loops, i.e. we may never exit through an un-joined channel. Conversion from Moore Machine to Mealy Machine Algorithm Input - Moore Machine Output - Mealy Machine Step 1 - Take a blank Mealy Machine transition table format. Step 2 - Copy all the Moore Machine transition states into this table format. Step 3 - Now check the present states and their corresponding outputs in the Moore Machine state table; if for a state Qi output is m, copy it into the output columns of the Mealy Machine state table wherever Qi appears in the next state, Example Let's see the following Moore machine ~ | Present State Next State ‘Output | | a=0 a=l | d b a hea[* [° Ee | © | © © | 0 | I? [* 2 | Now we apply Algorithm to convert it to Mealy Machine. Step1&2- Present State | Next State | a=0 az1 | | State Output State Output | Da | d b | b | a d | © © c | d | b \2 Po | Step 3- a. Present State Next State a=0 (State | Output | State | Output =a Fa 1 | b 0 b ya 1 | d 1 € c 0 | © 0 d b 0 | a 1 Conversion from Mealy Machine to Moore Machine Algorithm Input ~ Mealy Machine Output ~ Moore Machine Step 1—Here measure the number of different outputs for each state (ii) that are available in the state table of the Mealy machine. Step 2 — Incase if all the outputs of Qi are same, copy state Qi. If it has n distinct outputs, break Qi into n states as Qin where n=0, 1, 2. Step 3 - If the output of the initial state is 1, insert a new initial state at the beginning which gives 0 output. Example Let's see the following Mealy Machine ~ [Presentstate_[NewtstateSSSSOS~SYazo aaa ] Next State Output Next State Output Sa d ° b 1 b a 1 d oO . A 1 G O | d b 0 a 1 | While the states ‘a’ and ‘d’ provide only 1 and 0 outputs respectively, so we create states ‘a’ and ‘b’ and ‘c’ delivers different outputs (1 and 0). So, we divide b into bO, b1 and cinto 0, cl. - But states Present State | Next State | Output ] a=0 ae | Da id b, la | bo a d oO | bi a d 1 0 e Ca ° & G Ca 1 d be. a 0 Siteerce between Mealy and Moore Machine: Output depends both upon ~ | Output depends only — upon the present state. fous and present input Generally, it has more states than Mealy Machine. Generally, it figs fewerestates than Ivoore Machine, Input change can cause change in] Outputchanged ae cock eds tn org acon {leet i done. In Moore machines, more logic is needed to decode the outputs since it hay more circuit delays. Mealy machines react faster to inputs. Figure 1.12: Difference between Mealy & Moore Machine