Automata Theory Tutorial - RxJS, Ggplot2, Python Data .
Automata TheoryAbout this TutorialAutomata Theory is a branch of computer science that deals with designing abstract selfpropelled computing devices that follow a predetermined sequence of operationsautomatically. An automaton with a finite number of states is called a Finite Automaton.This is a brief and concise tutorial that introduces the fundamental concepts of FiniteAutomata, Regular Languages, and Pushdown Automata before moving onto Turingmachines and Decidability.AudienceThis tutorial has been prepared for students pursuing a degree in any informationtechnology or computer science related field. It attempts to help students grasp theessential concepts involved in automata theory.PrerequisitesThis tutorial has a good balance between theory and mathematical rigor. The readers areexpected to have a basic understanding of discrete mathematical structures.Copyright & Disclaimer Copyright 2016 by Tutorials Point (I) Pvt. Ltd.All the content and graphics published in this e-book are the property of Tutorials Point (I)Pvt. Ltd. The user of this e-book is prohibited to reuse, retain, copy, distribute or republishany contents or a part of contents of this e-book in any manner without written consentof the publisher.We strive to update the contents of our website and tutorials as timely and as precisely aspossible, however, the contents may contain inaccuracies or errors. Tutorials Point (I) Pvt.Ltd. provides no guarantee regarding the accuracy, timeliness or completeness of ourwebsite or its contents including this tutorial. If you discover any errors on our website orin this tutorial, please notify us at contact@tutorialspoint.comi
Automata TheoryTable of ContentsAbout this Tutorial . iAudience . iPrerequisites . iCopyright & Disclaimer . iTable of Contents . ii1.Introduction . 1Automata – What is it? . 1Related Terminologies . 12.Deterministic Finite Automaton . 33.Non-deterministic Finite Automaton . 5DFA vs NDFA . 6Acceptors, Classifiers, and Transducers . 7Acceptability by DFA and NDFA . 74.NDFA to DFA Conversion. 95.DFA Minimization . 11DFA Minimization using Myphill-Nerode Theorem . 11DFA Minimization using Equivalence Theorem . 136.Moore and Mealy Machines . 15Moore Machine to Mealy Machine . 17Mealy Machine to Moore Machine . 19CLASSIFICATION OF GRAMMARS . 207.Introduction to Grammars . 21Grammar . 21Derivations from a Grammar . 228.Language Generated by a Grammar . 23Construction of a Grammar Generating a Language . 239.Chomsky Classification of Grammars . 25REGULAR GRAMMAR . 2810. Regular Expressions . 2911. Regular Sets . 31Identities Related to Regular Expressions . 3312. Arden’s Theorem . 35ii
Automata Theory13. Construction of an FA from an RE . 38Finite Automata with Null Moves (NFA-ε) . 40Removal of Null Moves from Finite Automata . 4014. Pumping Lemma for Regular Languages. 4315. DFA Complement . 45CONTEXT-FREE GRAMMARS . 4716. Context-Free Grammar Introduction . 48Generation of Derivation Tree . 48Left and Right Recursive Grammars . 5217. Ambiguity in Context-Free Grammars . 5318. CFL Closure Property . 5519. CFG Simplification . 5620. Chomsky Normal Form . 6021. Greibach Normal Form . 6322. Pumping Lemma for CFG . 65PUSHDOWN AUTOMATA . 6623. Pushdown Automata Introduction . 67Basic Structure of PDA . 67Terminologies Related to PDA . 6824. Pushdown Automata Acceptance . 7025. PDA & Context-Free Grammar . 7226. Pushdown Automata and Parsing . 74TURING MACHINE . 7627. Turing Machine Introduction . 77Definition . 77Time and Space Complexity of a Turing Machine . 7828. Accepted Language & Decided Language . 7929. Multi-tape Turing Machine . 8130. Multi-track Turing Machine . 82iii
Automata Theory31. Non-Deterministic Turing machine . 8332. Semi-infinite Tape Turing Machine . 8433. Linear Bounded Automata . 85DECIDABILITY . 8634. Language Decidability . 8735. Undecidable Languages . 8936. Turing Machine Halting Problem . 9037. Rice Theorem . 9138. Post Correspondence Problem . 92iv
1. IntroductionAutomata TheoryAutomata – What is it?The term "Automata" is derived from the Greek word "αὐτόματα" which means "selfacting". An automaton (Automata in plural) is an abstract self-propelled computing devicewhich follows a predetermined sequence of operations automatically.An automaton with a finite number of states is called a Finite Automaton (FA) or FiniteState Machine (FSM).Formal definition of a Finite AutomatonAn automaton can be represented by a 5-tuple (Q, Σ, δ, q0, F), where: Q is a finite set of states. Σ is a finite set of symbols, called the alphabet of the automaton. δ is the transition function. q0 is the initial state from where any input is processed (q 0 Q). F is a set of final state/states of Q (F Q).Related TerminologiesAlphabet Definition: An alphabet is any finite set of symbols. Example: Σ {a, b, c, d} is an alphabet set where ‘a’, ‘b’, ‘c’, and ‘d’ aresymbols.String Definition: A string is a finite sequence of symbols taken from Σ. Example: ‘cabcad’ is a valid string on the alphabet set Σ {a, b, c, d}Length of a String Definition : It is the number of symbols present in a string. (Denoted by S ). Examples:oIf S ‘cabcad’, S 6oIf S 0, it is called an empty string (Denoted by λ or ε)1
Automata TheoryKleene Star Definition: The Kleene star, Σ*, is a unary operator on a set of symbols or strings,Σ, that gives the infinite set of all possible strings of all possible lengths over Σincluding λ. Representation: Σ* Σ0 U Σ1 U Σ2 U . where Σp is the set of all possible stringsof length p. Example: If Σ {a, b}, Σ* {λ, a, b, aa, ab, ba, bb, .}Kleene Closure / Plus Definition: The set Σ is the infinite set of all possible strings of all possible lengthsover Σ excluding λ. Representation: Example: If Σ { a, b } , Σ { a, b, aa, ab, ba, bb, .}Σ Σ1 U Σ2 U Σ3 U .Σ Σ* { λ }Language Definition : A language is a subset of Σ* for some alphabet Σ. It can be finite orinfinite. Example : If the language takes all possible strings of length 2 over Σ {a, b},then L { ab, bb, ba, bb}2
2. Deterministic Finite AutomatonAutomata TheoryFinite Automaton can be classified into two types: Deterministic Finite Automaton (DFA) Non-deterministic Finite Automaton (NDFA / NFA)Deterministic Finite Automaton (DFA)In DFA, for each input symbol, one can determine the state to which the machine willmove. Hence, it is called Deterministic Automaton. As it has a finite number of states,the machine is called Deterministic Finite Machine or Deterministic FiniteAutomaton.Formal Definition of a DFAA DFA can be represented by a 5-tuple (Q, Σ, δ, q0, F) where: Q is a finite set of states. Σ is a finite set of symbols called the alphabet. δ is the transition function where δ: Q Σ Q q0 is the initial state from where any input is processed (q 0 Q). F is a set of final state/states of Q (F Q).Graphical Representation of a DFAA DFA is represented by digraphs called state diagram. The vertices represent the states. The arcs labeled with an input alphabet show the transitions. The initial state is denoted by an empty single incoming arc. The final state is indicated by double circles.ExampleLet a deterministic finite automaton be Q {a, b, c}, Σ {0, 1}, q0 {a}, F {c}, and3
Automata TheoryTransition function δ as shown by the following table:Present StateNext State forInput 0Next State forInput 1abacbacbcIts graphical representation would be as follows:10ab10c10DFA – Graphical Representation4
3. Non-deterministic Finite AutomatonAutomata TheoryIn NDFA, for a particular input symbol, the machine can move to any combination of thestates in the machine. In other words, the exact state to which the machine moves cannotbe determined. Hence, it is called Non-deterministic Automaton. As it has finite numberof states, the machine is called Non-deterministic Finite Machine or Nondeterministic Finite Automaton.Formal Definition of an NDFAAn NDFA can be represented by a 5-tuple (Q, Σ, δ, q0, F) where: Q is a finite set of states. Σ is a finite set of symbols called the alphabets. δ is the transition function where δ: Q Σ 2Q(Here the power set of Q (2Q) has been taken because in case of NDFA, from astate, transition can occur to any combination of Q states) q0 is the initial state from where any input is processed (q 0 Q). F is a set of final state/states of Q (F Q).Graphical Representation of an NDFA: (same as DFA)An NDFA is represented by digraphs called state diagram. The vertices represent the states. The arcs labeled with an input alphabet show the transitions. The initial state is denoted by an empty single incoming arc. The final state is indicated by double circles.ExampleLet a non-deterministic finite automaton be Q {a, b, c} Σ {0, 1} q0 {a} F {c}5
Automata TheoryThe transition function as shown below:Present StateNext State forInput 0a, bNext State forInput 1bbca, ccb, ccaIts graphical representation would be as follows:10ab0, 10, 10c0, 1NDFA – Graphical RepresentationDFA vs NDFAThe following table lists the differences between DFA and NDFA.DFANDFAThe transition from a state is to a singleparticular next state for each inputsymbol. Hence it is called deterministic.The transition from a state can be tomultiple next states for each input symbol.Hence it is called non-deterministic.Empty string transitions are not seen inDFA.NDFA permits empty string transitions.Backtracking is allowed in DFAIn NDFA, backtracking is not alwayspossible.Requires more space.Requires less space.A string is accepted by a DFA, if it transitsto a final state.A string is accepted by a NDFA, if at leastone of all possible transitions ends in afinal state.6
Automata TheoryAcceptors, Classifiers, and TransducersAcceptor (Recognizer)An automaton that computes a Boolean function is called an acceptor. All the states ofan acceptor is either accepting or rejecting the inputs given to it.ClassifierA classifier has more than two final states and it gives a single output when it terminates.TransducerAn automaton that produces outputs based on current input and/or previous state is calleda transducer. Transducers can be of two types: Mealy Machineinput.The output depends both on the current state and the current Moore MachineThe output depends only on the current state.Acceptability by DFA and NDFAA string is accepted by a DFA/NDFA iff the DFA/NDFA starting at the initial state ends inan accepting state (any of the final states) after reading the string wholly.A string S is accepted by a DFA/NDFA (Q, Σ, δ, q0, F), iffδ*(q0, S) FThe language L accepted by DFA/NDFA is{S S Σ* and δ*(q0, S) F}A string S′ is not accepted by a DFA/NDFA (Q, Σ, δ, q0, F), iffδ*(q0, S′) FThe language L′ not accepted by DFA/NDFA (Complement of accepted language L) is {S S Σ* and δ*(q0, S) F}7
Automata TheoryExampleLet us consider the DFA shown in Figure 1.3. From the DFA, the acceptable strings can bederived.01ac011d0Acceptability of strings by DFAStrings accepted by the above DFA: {0, 00, 11, 010, 101, .}Strings not accepted by the above DFA: {1, 011, 111, .}8
4. NDFA to DFA ConversionAutomata TheoryProblem StatementLet X (Qx, Σ, δx, q0, Fx) be an NDFA which accepts the language L(X). We have todesign an equivalent DFA Y (Qy, Σ, δy, q0, Fy) such that L(Y) L(X). The followingprocedure converts the NDFA to its equivalent DFA:AlgorithmInput:An NDFAOutput:An equivalent DFAStep 1Create state table from the given NDFA.Step 2Create a blank state table under possible input alphabets for the equivalentDFA.Step 3Mark the start state of the DFA by q0 (Same as the NDFA).Step 4Find out the combination of States {Q 0, Q1,. , Qn} for each possible inputalphabet.Step 5Each time we generate a new DFA state under the input alphabet columns,we have to apply step 4 again, otherwise go to step 6.Step 6The states which contain any of the final states of the NDFA are the finalstates of the equivalent DFA.ExampleLet us consider the NDFA shown in the figure below.qδ(q,0)δ(q,1)a{a,b,c,d,e}{d,e}b{c}{e}c {b}d{e} e 9
Automata TheoryUsing the above algorithm, we find its equivalent DFA. The state table of the DFA is shownin ][a,b,c,d,e][b,d,e][d,e][e] [b,d,e][c,e][e][e] [c,e] [b][b][c][e][c] [b]State table of DFA equivalent to NDFAThe state diagram of the DFA is as ,e][e][c]State diagram of DFA10
5. DFA MinimizationAutomata TheoryDFA Minimization using Myphill-Nerode TheoremAlgorithmInputDFAOutputMinimized DFAStep 1Draw a table for all pairs of states (Qi, Qj) not necessarily connected directly[All are unmarked initially]Step 2Consider every state pair (Qi, Qj) in the DFA where Qi F and Qj F or viceversa and mark them. [Here F is the set of final states]Step 3Repeat this step until we cannot mark anymore states:If there is an unmarked pair (Qi, Qj), mark it if the pair {δ(Qi, A), δ (Qi, A)}is marked for some input alphabet.Step 4Combine all the unmarked pair (Qi, Qj) and make them a single state in thereduced DFA.ExampleLet us use Algorithm 2 to minimize the DFA shown below.0, 11b1f00011a10e0State Diagram of DFA11
Automata TheoryStep 1 : We draw a table for all pair of states.abcdefcdefabcdefStep 2 : We mark the state pairs:aabcdef b Step 3 : We will try to mark the state pairs, with green colored check mark, transitively.If we input 1 to state ‘a’ and ‘f’, it will go to state ‘c’ and ‘f’ respectively. (c, f) is alreadymarked, hence we will mark pair (a, f). Now, we input 1 to state ‘b’ and ‘f’; it will go tostate ‘d’ and ‘f’ respectively. (d, f) is already marked, hence we will mark pair (b, f).aabcdef b c d ef After step 3, we have got state combinations {a, b} {c, d} {c, e} {d, e} that areunmarked.We can recombine {c, d} {c, e} {d, e} into {c, d, e}Hence we got two combined states as: {a, b} and {c, d, e}12
Automata TheorySo the final minimized DFA will contain three states {f}, {a, b} and {c, d, e}0, 10(a,b)1(c, d, e)1(f)0, 1State diagram of reduced DFADFA Minimization using Equivalence TheoremIf X and Y are two states in a DFA, we can combine these two states into {X, Y} if theyare not distinguishable. Two states are distinguishable, if there is at least one string S,such that one of δ (X, S) and δ (Y, S) is accepting and another is not accepting. Hence, aDFA is minimal if and only if all the states are distinguishable.Algorithm 3Step 1:All the states Q are divided in two partitions: final states and non-finalstates and are denoted by P0. All the states in a partition are 0th equivalent.Take a counter k and initialize it with 0.Step 2:Increment k by 1. For each partition in Pk, divide the states in Pk into twopartitions if they are k-distinguishable. Two states within this partition X andY are k-distinguishable if there is an input S such that δ(X, S) and δ(Y, S)are (k-1)-distinguishable.Step 3:If Pk Pk-1, repeat Step 2, otherwise go to Step 4.Step 4:Combine kth equivalent sets and make them the new states of the reducedDFA.13
Automata TheoryExampleLet us consider the following DFA:0, t us apply the above algorithm to the above DFA: P0 {(c,d,e), (a,b,f)} P1 {(c,d,e), (a,b),(f)} P2 {(c,d,e), (a,b),(f)}Hence, P1 P2.There are three states in the reduced DFA. The reduced DFA is as follows:Qδ(q,0)δ(q,1)(a, b)(a, b)(c,d,e)(c,d,e)(c,d,e)(f)(f)(f)(f)00, 1(a,b)1(c, d, e)0,11(f)State Table and State Diagram of Reduced DFA14
6. Moore and Mealy MachinesAutomata TheoryFinite automata may have outputs corresponding to each transition. There are two typesof finite state machines that generate output: Mealy Machine Moore machineMealy MachineA Mealy Machine is an FSM whose output depends on the present state as well as thepresent input.It can be described by a 6 tuple (Q, , O, δ, X, q0) where Q is a finite set of states. is a finite set of symbols called the input alphabet. O is a finite set of symbols called the output alphabet. δ is the input transition function where δ: Q Σ Q X is the output transition function where X: Q Σ O q0 is the initial state from where any input is processed (q0 Q).The state table of a Mealy Machine is shown below –Next statePresentstateinput 0input d𝑥3c𝑥1dd𝑥3d𝑥215
Automata TheoryThe state diagram of the above Mealy Machine is:0/x2b0/x11/x30/x3a1/x10 /x3, 1/x2cd1/x1Moore MachineMoore machine is an FSM whose outputs depend on only the present state.A Moore machine can be described by a 6 tuple (Q, Σ, O, δ, X, q0) where: Q is a finite set of states. Σ is a finite set of symbols called the input alphabet. O is a finite set of symbols called the output alphabet. δ is the input transition function where δ: Q Σ Q X is the output transition function where X: Q O q0 is the initial state from where any input is processed (q0 Q).The state table of a Moore Machine is shown below –Present StateNext StateOutputInput 0Input 1abc𝑥2bbd𝑥1ccd𝑥2ddd𝑥316
Automata TheoryThe state diagram of the above Moore Machine is:00, 1b/x101d/x3a/x21c/x201Mealy Machine vs. Moore MachineThe following table highlights the points that differentiate a Mealy Machine from a MooreMachine.Mealy MachineMoore MachineOutput depends both upon presentstate and present input.Output depends only upon the presentstate.Generally, it has fewer states thanMoore Machine.Generally, it has more states than MealyMachine.Output changes at the clock edges.Input change can cause change in outputchange as soon as logic is done.Mealy machines react faster to inputsIn Moore machines, more logic is needed todecode the outputs since it has more circuitdelays.Moore Machine to Mealy MachineAlgorithm 4Input:Moore MachineOutput:Mealy MachineStep 1Take a blank Mealy Machine transition table format.Step 2Copy all the Moore Machine transition states into this table format.Step 3Check the present states and their corresponding outputs in the MooreMachine state table; if for a state Qi output is m, copy it into the outputcolumns of the Mealy Machine state table wherever Qi appears in the nextstate.17
Automata TheoryExampleLet us consider the following Moore machine:Next StatePresentStatea 0a 1 adb1bad0ccc0dba1OutputState table of a Moore MachineNow we apply Algorithm 4 to convert it to Mealy Machine.Step 1 & 2:Present State aNext Statea 0a 1StateOutputStateOutputdbbadcccdbaThe partial state table after steps 1 and 2Step 3:Next StatePresent State abcda 0State Outputd1a1c0b0a 1State Outputb0d1c0a1State table of an equivalent Mealy Machine18
Automata TheoryMealy Machine to Moore MachineAlgorithm 5:Input:Mealy MachineOutput:Moore MachineStep 1Calculate the number of different outputs for each state (Qi) that areavailable in the state table of the Mealy machine.Step 2If 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 3If the output of the initial state is 1, insert a new initial state at the beginningwhich gives 0 output.ExampleLet us consider the following Mealy Machine:Next StatePresentState abcda 0NextOutputStated0a1c1b0a 1NextOutputStateb1d0c0a1State table of a Mealy MachineHere, states ‘a’ and ‘d’ give only 1 and 0 outputs respectively, so we retain states ‘a’ and‘d’. But states ‘b’ and ‘c’ produce different outputs (1 and 0). So, we divide b into b0, b1and c into c0, c1.PresentState ab0b1c0c1dNext Statea 0 a 1db1adadc1c0c1c0b0aOutput101010State table of equivalent Moore Machine19
Automata TheoryClassification of Grammars20
7. Introduction to GrammarsAutomata TheoryIn the literary sense of the term, grammars denote syntactical rules for conversation innatural languages. Linguistics have attempted to define grammars since the inception ofnatural languages like English, Sanskrit, Mandarin, etc.The theory of formal languages finds its applicability extensively in the fields of ComputerScience. Noam Chomsky gave a mathematical model of grammar in 1956 which iseffective for writing computer languages.GrammarA grammar G can be formally written as a 4-tuple (N, T, S, P) where N or VN is a set of variables or non-terminal symbols T or is a set of Terminal symbols S is a special variable called the Start symbol, S N P is Production rules for Terminals and Non-terminals. A production rule has theform 𝛼 𝛽, where and are strings on 𝑉𝑁 Σ and least one symbol of belongsto VN.ExampleGrammar G1:({S, A, B}, {a, b}, S, {S AB, A a, B b})Here,S, A, and B are Non-terminal symbols;a and b are Terminal symbolsS is the Start symbol, S NProductions, P : S AB, A a, B bExample:Grammar G2:({S, A}, {a, b}, S,{S aAb, aA aaAb, A ε } )Here,S and A are Non-terminal symbols.a and b are Terminal symbols.21
Automata Theoryε is an empty string.S is the Start symbol, S NProduction P : S aAb, aA aaAb, A εDerivations from a GrammarStrings may be derived from other strings using the productions in a grammar. If agrammar G has a production α β, we can say that x α y derives x β y in G. Thisderivation is written as:𝑮𝒙𝜶𝒚 𝒙𝜷𝒚ExampleLet us consider the grammar:G2 ({S, A}, {a, b}, S, {S aAb, aA aaAb, A ε } )Some of the strings that can be derived are:S aAb aaAbbusing production S aAbusing production aA aAb aaaAbbb using production aA aAb aaabbbusing production A ε22
8. Language Generated by a GrammarAutomata TheoryThe set of all strings that can be derived from a grammar is said to be the languagegenerated from that grammar. A language generated by a grammar G is a subset formallydefined by𝐿(𝐺) { 𝑊 𝑊 Σ ,𝐺𝑆 𝑊}If L(G1) L(G2), the Grammar G1 is equivalent to the Grammar G2.ExampleIf there is a grammarG: N {S, A, B}T {a, b}P {S AB, A
An automaton with a finite number of states is called a Finite Automaton (FA) or Finite State Machine (FSM). Formal definition of a Finite Automaton An automaton can be represented by a 5-tuple (Q, Σ, δ, q 0, F), where: Q is a finite set of states. Σ is a finite
Advanced Automata Theory is a lecture which will rst review the basics of formal languages and automata theory and then give insight into speci c topics from wider area of automata theory. In computer science, automata are an important tool for many theoretical results and various types of automata
Automata and Formal Languages II Tree Automata Peter Lammich SS 2015 1/161. Overview by Lecture Apr 14: Slide 3 Apr 21: Slide 2 Apr 28: Slide 4 May 5: Slide 50 . Finite tree automata: Basic theory (TATA Ch. 1) Pumping Lemma, Clo
Complexity, the Central Concepts of Automata Theory - Alphabets, Strings, Languages, Problems. Deterministic Finite Automata, Nondeterministic Finite Automata, an application: Text Search, Finite Automata with Epsilon-Transitions, Finite automata with output - Mealy and Moore machines, Equivalence of Mealy and Moore machines.
properties of bipolar general fuzzy switchboard automata are discussed in term of switching and commutative by proving the theorems that are related into these concepts. . 2.3 Automata theory 18 2.4 Optimisation problems 23 2.4.1 Critical path problem 23 . Deterministic finite automata FSM - Finite state machine FSA - Finite state automata .
Switching and automata theory Language theory and formal semantics Operating Systems Background to Distributed Computing: . Finite automata; Pushdown automata; Linear-bounded automata. PODC 2008, Toronto, Canada, August 20, 2008 Evolution of Distributed Computing Theory. Outline
Deterministic Finite Automata plays a vital role in lexical analysis phase of compiler design, Control Flow graph in software testing, Machine learning [16], etc. Finite state machine or finite automata is classified into two. These are Deterministic Finite Automata (DFA) and non-deterministic Finite Automata(NFA).
The early years of automata theory Kleene’s theorem [68] is usually considered as the starting point of automata theory. It shows that the class of recognisable languages (that is, recognised by finite automata), coincides with the class of rational languages, which are given by rational express
Automata Theory possesses a high degree of permanence and stability, in contrast with the ever-changing paradigms of the technology, development, and management of computer systems. Further, parts of the Automata theory have direct bearing on practice, such as Automata on circuit design, com
