GLOBAL ACADEMY OF TECHNOLOGY ra Au Autonomous Insitute, Afliiated to VIU Belagavi, Approved by AICTE, Accredited by NAAC,'A° Grade, Lae {deal Homes Township, Rajarajeshwari Nager, Bengaluru ~ 560 098 ae Tet +91 8028603158 Ext 300), Ena: hodese@gatacan Web: waviantacin SEACH Department of Computer Science and Engineering (Aceredited by NBA 2022-2025) eee eens V Semester Theory of Computation (22CSES5C) Module 1 Finite Automata Theory of Automata is a theoretical branch of Computer Science and Mathematics Itis the study of abstract machines and the computation problems that can be solved using these machines, The abstract machine is called the automata An automaton with a finite mmmber of states is called a Finite Automaton. Automata Applications Design of Digital Circuits Compiler Construction String matching String processing Traflic signal ‘Computer system security, cryptography, hackers and viruses ‘Compntational biology Natural Language Processing Artificial Intelligence and Computational Reasoning |. Interactive video games Finite Automata It is a mathematical model used to study the abstract machines with the inputs chosen from x. Abstract Machine is a Conceptual or theoretical model of a computer Hardware OR Software system which really does not exist.+ © is a set of alphabets (Ex : a,b,0.1 ete) using which any string can be obtained. (Ex : 00100, aababb) + Onrreading the string, the machine may accept the string or reject the string. Symbols used in Finite Automata A cirele is used to represent a state. Here, qo is a state of the machine. A circle with > which is not originating from any node represents start state of the machine. A concentric (double) circle is used to represent the finat state. There is a transition (change of state) from state qo on input symbol 1 to state qi Representation : 5(qp,1) = q) The machine isin state q,, on reading 0, remains in the same state q,, Representation : 6(q,,0 QO OeThe machine is in state q,, on reading 0 OR 1, enters into state q, Representation: 6(q,.0)=4, 84,4, Terms used in Finite Automata 1. Alphabet ©. ‘eae les: ~ E={0, 1} > Binary alphabets E= fa, b,c, .....2} — Set of lower case letters == {a.b,....z, A,B, ...Z,0, 1, ....9, #,(,), {, }, [], -....}=9 Alphabets of C Language 2. Power of an alphabet Example : TEE = (0, 1} then £9 = {c} denotes set of words of length 0 X= (0, 1} denotes set of words of length 1 :? = {00, 01, 10, 11} denotes set of words of length 2 3. String (w) byw. Example : Let Z= {0,1} is a set of alphabets. Different strings {0,1,00,01,10,11,01001,011101} Notations: cis for empty string Lowercase letters such as u, v, W, X, Y, z are normally used to indicate strings, Ex: w=100101Functions of Strings 1. Length of a string Itis the ‘number of symbols in the string w and denoted by jw The length of an empty string-O. 2. Concatenation of two strings 3. Reversal of a string | Relations on Strings 1. substias Examples : aaa isasubstingof —_abaaabbaa aba isasubstingof ——_ababbb gu renee substring Examples : Note :ix oftisxe D* (3 Example = The suffix of abba are é, a, ba, bba, a 5. Language A language isa subset of E* denoted by Lc 5* Examples : + A language containing empty string is denoted by { ¢ } + A language of strings consisting of equal number of 0’s and I°s L= {e, 01,10,0011,1100,0101,1010,..} + A language of strings consisting of n no, of 0's followed by n no. of 1's L={e, 01, 0011,000111,..} + Anempty language L={ } or 6 Funetions of a language Since langnages are sets, all standard operations are well defined on languages. 1. Union E= {a,b} L1= { €, 2a, abbaaa, baaaaaabbh, .. 12={a,ea, ana, anna, .....} LIUL2= {¢,a, aa, aaa, abbaaa, baaaaaabbb, .....} 2. Intersection LIAL2= { 2a, aaa, .... } 3. Difference L1—L2={é, aa, aaa, .... } L2—L1={a, aaa, aaaaa, .....}4. Concatenation Let L1 and L2 be two languages defined over the alphabets ©. LIL2 = { weE*| seL1, teL2 then w-st} Example : L1= {chair, table, desk} L2 = {book, paper} L1L2 = {chairbook, tablebook, deskbook, chairpaper, tablepaper, deskpaper} Finite Automata (FA) + FAis a computational device whose input is a set of strings and output is one of the two values — accept or reject. + IfMisan FA, an input string is fed to M—one character at a time, left to right, each time it receives a character, M considers its current state and new character, and then chooses the next state, + One or more states of M can be marked as final states. Types of Finite Automata (FA) 1. Deterministic FA (DFA) Non-detemministic FA (NFA) Deterministic Finite Automata (DFA) In DPA, there is always exactly one move that can be made at each state This move is determined by the curent state and next input character. Formal Definition : Assume M is a DFA M is aquintuple (Q, 5,8 qo, F) where Q= Finite no. of states = input alphabets Start state only one start state et of Final states, 6 = transition function x = to (current state) (input symbol) (next state) Consider pictorial representation of DFA oOComponents of DEA States Input alphabets Transitions 1, States The circles are called vertices/nodes/states. Each state is identified by a name qo.qu, ete Start state : go with an arrow labelled start. Final state : qo with two concenttic circles. Intermediate state : q: is neither start state nor accepting state. ‘This DFA has three states qo,q: and q2 Representation : Q = { qo, qi, 42} Note: + ADFA can have one or more final states. + If there is no final state in DPA, it accepts empty language. 2. Input alphabets + Bach edge is labelled with 0 or 1 + They represent input alphabets. + Denoted as B= {0,1} Transitions + Change of state after consuming an input symbol + [there is a change of state from q; to q, onan input symbol a, itis written as 5(qua)=q Examples : 8(q0.0)=qo 5(q,0)=a 5(q2,0)=q2 8(q0,1)-a1 Aaa OM. =a Designing of Deterministic Finite Automata (DFA) Identify the minimum string. Identify the alphabets, Construct a skeleton DFA. Identify other transitions not defined in step 3, Complete the DEA. 1 2. 3 4, 3.