THEORY OF COMPUTATION LECTURE NOTES

what is theory of computation and theory of computation objective type questions with answers pdf free download
FrankRoberts Profile Pic
FrankRoberts,France,Researcher
Published Date:11-07-2017
Your Website URL(Optional)
Comment
THEORY OF COMPUTATION LECTURE NOTES (Subject Code: BCS-303) for Bachelor of Technology in Computer Science and Engineering & Information Technology Department of Computer Science and Engineering & Information Technology Veer Surendra Sai University of Technology (Formerly UCE, Burla) Burla, Sambalpur, Odisha Lecture Note Prepared by: Prof. D. Chandrasekhar Rao Prof. Kishore Kumar Sahu Prof. Pradipta Kumar Das BCS 303 THEORY OF COMPUTATION (3-1-0) Cr.-4 Module – I (10 Lectures) Introduction to Automata: The Methods Introduction to Finite Automata, Structural Representations, Automata and Complexity. Proving Equivalences about Sets, The Contrapositive, Proof by Contradiction, Inductive Proofs: General Concepts of Automata Theory: Alphabets Strings, Languages, Applications of Automata Theory. Finite Automata: The Ground Rules, The Protocol, Deterministic Finite Automata: Definition of a Deterministic Finite Automata, How a DFA Processes Strings, Simpler Notations for DFA’s, Extending the Transition Function to Strings, The Language of a DFA Nondeterministic Finite Automata: An Informal View. The Extended Transition Function, The Languages of an NFA, Equivalence of Deterministic and Nondeterministic Finite Automata. Finite Automata With Epsilon-Transitions: Uses of ∈-Transitions, The Formal Notation for an ∈-NFA, Epsilon-Closures, Extended Transitions and Languages for ∈-NFA’s, Eliminating ∈- Transitions. Module – II (10 Lectures) Regular Expressions and Languages: Regular Expressions: The Operators of regular Expressions, Building Regular Expressions, Precedence of Regular-Expression Operators, Precedence of Regular-Expression Operators Finite Automata and Regular Expressions: From DFA’s to Regular Expressions, Converting DFA’s to Regular Expressions, Converting DFA’s to Regular Expressions by Eliminating States, Converting Regular Expressions to Automata. Algebraic Laws for Regular Expressions: Properties of Regular Languages: The Pumping Lemma for Regular Languages, Applications of the Pumping Lemma Closure Properties of Regular Languages, Decision Properties of Regular Languages, Equivalence and Minimization of Automata, Context-Free Grammars and Languages: Definition of Context-Free Grammars, Derivations Using a Grammars Leftmost and Rightmost Derivations, The Languages of a Grammar, Parse Trees: Constructing Parse Trees, The Yield of a Parse Tree, Inference Derivations, and Parse Trees, From Inferences to Trees, From Trees to Derivations, From Derivation to Recursive Inferences, Applications of Context-Free Grammars: Parsers, Ambiguity in Grammars and Languages: Ambiguous Grammars, Removing Ambiguity From Grammars, Leftmost Derivations as a Way to Express Ambiguity, Inherent Anbiguity Module – III (10 Lectures) Pushdown Automata: Definition Formal Definition of Pushdown Automata, A Graphical Notation for PDA’s, Instantaneous Descriptions of a PDA, Languages of PDA: Acceptance by Final State, Acceptance by Empty Stack, From Empty Stack to Final State, From Final State to Empty Stack Equivalence of PDA’s and CFG’s: From Grammars to Pushdown Automata, From PDA’s to Grammars Deterministic Pushdown Automata: Definition of a Deterministic PDA, Regular Languages and Deterministic PDA’s, DPDA’s and Context-Free Languages, DPDA’s and Ambiguous Grammars Properties of Context-Free Languages: Normal Forms for Context-Free Grammars, The Pumping Lemma for Context-Free Languages, Closure Properties of Context-Free Languages, Decision Properties of CFL’s Module –IV (10 Lectures) Introduction to Turing Machines: The Turing Machine: The Instantaneous Descriptions for Turing Machines, Transition Diagrams for Turing Machines, The Language of a Turing Machine, Turing Machines and Halting Programming Techniques for Turing Machines, Extensions to the Basic Turing Machine, Restricted Turing Machines, Turing Machines and Computers, Undecidability: A Language That is Not Recursively Enumerable, Enumerating the Binary Strings, Codes for Turing Machines, The Diagonalization Language An Undecidable Problem That Is RE: Recursive Languages, Complements of Recursive and RE languages, The Universal Languages, Undecidability of the Universal Language Undecidable Problems About Turing Machines: Reductions, Turing Machines That Accept the Empty Language. Post’s Correspondence Problem: Definition of Post’s Correspondence Problem, The “Modified” PCP, Other Undecidable Problems: Undecidability of Ambiguity for CFG’s Text Book: 1. Introduction to Automata Theory Languages, and Computation, by J.E.Hopcroft, rd R.Motwani & J.D.Ullman (3 Edition) – Pearson Education 2. Theory of Computer Science (Automata Language & Computations), by K.L.Mishra & N. Chandrashekhar, PHI MODULE-I W W What is TOC? ? ? In theoretical computer science, the theory of computation is the branch that deals with whether and how efficiently problems can be solved on a model of computation, using an algorithm. The field is divided into three major branches: automata theory, computability theory and computational complexity theory. In order to perform a rigorous study of computation, computer scientists work with a mathematical abstraction of computers called a model of computation. There are several models in use, but the most commonly examined is the Turing machine. Automata theory In theoretical computer science, automata theory is the study of abstract machines (or more appropriately, abstract 'mathematical' machines or systems) and the computational problems that can be solved using these machines. These abstract machines are called automata. This automaton consists of • states (represented in the figure by circles), • and transitions (represented by arrows). As the automaton sees a symbol of input, it makes a transition (or jump) to another state, according to its transition function (which takes the current state and the recent symbol as its inputs). Uses of Automata: compiler design and parsing. Introduction to formal proof: Basic Symbols used : U – Union ∩- Conjunction ϵ - Empty String Φ – NULL set 7- negation ‘ – compliment = implies Additive inverse: a+(-a)=0 Multiplicative inverse: a1/a=1 Universal set U=1,2,3,4,5 Subset A=1,3 A’ =2,4,5 Absorption law: AU(A ∩B) = A, A∩(AUB) = A De Morgan’s Law: (AUB)’ =A’ ∩ B’ (A∩B)’ = A’ U B’ Double compliment (A’)’ =A A ∩ A’ = Φ Logic relations: a  b = 7a U b 7(a∩b)=7a U 7b Relations: Let a and b be two sets a relation R contains aXb. Relations used in TOC: Reflexive: a = a Symmetric: aRb = bRa Transition: aRb, bRc = aRc If a given relation is reflexive, symmentric and transitive then the relation is called equivalence relation. Deductive proof: Consists of sequence of statements whose truth lead us from some initial statement called the hypothesis or the give statement to a conclusion statement. Additional forms of proof: Proof of sets Proof by contradiction Proof by counter example Direct proof (AKA) Constructive proof: If p is true then q is true Eg: if a and b are odd numbers then product is also an odd number. Odd number can be represented as 2n+1 a=2x+1, b=2y+1 product of a X b = (2x+1) X (2y+1) = 2(2xy+x+y)+1 = 2z+1 (odd number) Proof by contrapositive: Proof by Contradiction: H and not C implies falsehood. Be regarded as an observation than a theorem. For any sets a,b,c if a∩b = Φ and c is a subset of b the prove that a∩c =Φ Given : a∩b=Φ and c subset b Assume: a∩c Φ Then = a∩b Φ = a∩c=Φ(i.e., the assumption is wrong) Proof by mathematical Induction: Languages : The languages we consider for our discussion is an abstraction of natural languages. That is, our focus here is on formal languages that need precise and formal definitions. Programming languages belong to this category. Symbols : Symbols are indivisible objects or entity that cannot be defined. That is, symbols are the atoms of the world of languages. A symbol is any single object such as , a, 0, 1, , begin, or do. Alphabets : An alphabet is a finite, nonempty set of symbols. The alphabet of a language is normally denoted by . When more than one alphabets are considered for discussion, then subscripts may be used (e.g. etc) or sometimes other symbol like G may also be introduced. Example : Strings or Words over Alphabet : A string or word over an alphabet is a finite sequence of concatenated symbols of . Example : 0110, 11, 001 are three strings over the binary alphabet 0, 1 . aab, abcb, b, cc are four strings over the alphabet a, b, c . It is not the case that a string over some alphabet should contain all the symbols from the alpha- bet. For example, the string cc over the alphabet a, b, c does not contain the symbols a and b. Hence, it is true that a string over an alphabet is also a string over any superset of that alphabet. Length of a string : The number of symbols in a string w is called its length, denoted by w. Example : 011 = 4, 11 = 2, b = 1 Convention : We will use small case letters towards the beginning of the English alphabet to denote symbols of an alphabet and small case letters towards the end to denote strings over an alphabet. That is, (symbols) and are strings. Some String Operations : Let and be two strings. The concatenation of x and y denoted by xy, is the string . That is, the concatenation of x and y denoted by xy is the string that has a copy of x followed by a copy of y without any intervening space between them. Example : Consider the string 011 over the binary alphabet. All the prefixes, suffixes and substrings of this string are listed below. Prefixes: 㤴� , 0, 01, 011. Suffixes: 㤴� , 1, 11, 011. Substrings: 㤴� , 0, 1, 01, 11, 011. Note that x is a prefix (suffix or substring) to x, for any string x and 㤴� is a prefix (suffix or substring) to any string. A string x is a proper prefix (suffix) of string y if x is a prefix (suffix) of y and x 㠸〰 y. In the above example, all prefixes except 011 are proper prefixes. Powers of Strings : For any string x and integer , we use to denote the string formed by sequentially concatenating n copies of x. We can also give an inductive definition of as follows: = e, if n = 0 ; otherwise Example : If x = 011, then = 011011011, = 011 and Powers of Alphabets : We write (for some integer k) to denote the set of strings of length k with symbols from . In other words, = w w is a string over and w = k. Hence, for any alphabet, denotes the set of all strings of length zero. That is, = e . For the binary alphabet 0, 1 we have the following. The set of all strings over an alphabet is denoted by . That is, The set contains all the strings that can be generated by iteratively concatenating sym- bols from any number of times. Example : If = a, b , then = 㤴� , a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, …. Please note that if , then that is . It may look odd that one can proceed from the empty set to a non-empty set by iterated concatenation. But there is a reason for this and we accept this convention The set of all nonempty strings over an alphabet is denoted by . That is, Note that is infinite. It contains no infinite strings but strings of arbitrary lengths. Reversal : For any string the reversal of the string is . An inductive definition of reversal can be given as follows: Languages : A language over an alphabet is a set of strings over that alphabet. Therefore, a language L is any subset of . That is, any is a language. Example : 1. F is the empty language. 2. is a language for any . 3. e is a language for any . Note that, . Because the language F does not contain any string but e contains one string of length zero. 4. The set of all strings over 0, 1 containing equal number of 0's and 1's. 5. The set of all strings over a, b, c that starts with a. Convention : Capital letters A, B, C, L, etc. with or without subscripts are normally used to denote languages. Set operations on languages : Since languages are set of strings we can apply set operations to languages. Here are some simple examples (though there is nothing new in it). Union : A string iff or Example : 0, 11, 01, 011 1, 01, 110 = 0, 11, 01, 011, 111 Intersection : A string, xϵ L ∩L iff x ϵ L and x ϵ L . 1 2 1 2 Example : 0, 11, 01, 011 1, 01, 110 = 01 Complement : Usually, is the universe that a complement is taken with respect to. Thus for a language L, the complement is L(bar) = . Example : Let L = x x is even . Then its complement is the language x is odd . Similarly we can define other usual set operations on languages like relative com- plement, symmetric difference, etc. Reversal of a language : The reversal of a language L, denoted as , is defined as: . Example : 1. Let L = 0, 11, 01, 011 . Then = 0, 11, 10, 110 . 2. Let L = n is an integer . Then = n is an integer . Language concatenation : The concatenation of languages and is defined as = xy and . Example : a, ab b, ba = ab, aba, abb, abba . Note that , 1. in general. 2. 3. Iterated concatenation of languages : Since we can concatenate two languages, we also repeat this to concatenate any number of languages. Or we can concatenate a language with itself any number of times. The operation denotes the concatenation of L with itself n times. This is defined formally as follows: Example : Let L = a, ab . Then according to the definition, we have and so on. Kleene's Star operation : The Kleene star operation on a language L, denoted as is defined as follows : = ( Union n in N ) = = x x is the concatenation of zero or more strings from L Thus is the set of all strings derivable by any number of concatenations of strings in L. It is also useful to define = , i.e., all strings derivable by one or more concatenations of strings in L. That is = (Union n in N and n 0) = Example : Let L = a, ab . Then we have, = = e a, ab aa, aab, aba, abab … = = a, ab aa, aab, aba, abab … , for every language L, including . Note : 㤴� is in The previously introduced definition of is an instance of Kleene star. (Generates) (Recognizes) Grammar Language Automata Automata: A algorithm or program that automatically recognizes if a particular string belongs to the language or not, by checking the grammar of the string. An automata is an abstract computing device (or machine). There are different varities of such abstract machines (also called models of computation) which can be defined mathematically. Every Automaton fulfills the three basic requirements. • Every automaton consists of some essential features as in real computers. It has a mech- anism for reading input. The input is assumed to be a sequence of symbols over a given alphabet and is placed on an input tape(or written on an input file). The simpler automata can only read the input one symbol at a time from left to right but not change. Powerful versions can both read (from left to right or right to left) and change the input. • The automaton can produce output of some form. If the output in response to an input string is binary (say, accept or reject), then it is called an accepter. If it produces an out- put sequence in response to an input sequence, then it is called a transducer(or automaton with output). • The automaton may have a temporary storage, consisting of an unlimited number of cells, each capable of holding a symbol from an alphabet ( whcih may be different from the input alphabet). The automaton can both read and change the contents of the storage cells in the temporary storage. The accusing capability of this storage varies depending on the type of the storage. • The most important feature of the automaton is its control unit, which can be in any one of a finite number of interval states at any point. It can change state in some de- fined manner determined by a transition function. Figure 1: The figure above shows a diagrammatic representation of a generic automa- tion. Operation of the automation is defined as follows. At any point of time the automaton is in some integral state and is reading a particular symbol from the input tape by using the mechanism for reading input. In the next time step the automa- ton then moves to some other integral (or remain in the same state) as defined by the transition function. The transition function is based on the current state, input symbol read, and the content of the temporary storage. At the same time the content of the storage may be changed and the input read may be modifed. The automation may also produce some output during this transition. The internal state, input and the content of storage at any point defines the configuration of the automaton at that point. The transition from one configuration to the next ( as defined by the transition function) is called a move. Finite state machine or Finite Automation is the simplest type of abstract machine we consider. Any system that is at any point of time in one of a finite number of interval state and moves among these states in a defined manner in response to some input, can be modeled by a finite automaton. It doesnot have any temporary storage and hence a restricted model of computation. Finite Automata Automata (singular : automation) are a particularly simple, but useful, model of compu- tation. They were initially proposed as a simple model for the behavior of neurons. States, Transitions and Finite-State Transition System : Let us first give some intuitive idea about a state of a system and state transitions before describing finite automata. Informally, a state of a system is an instantaneous description of that system which gives all relevant information necessary to determine how the system can evolve from that point on. Transitions are changes of states that can occur spontaneously or in response to inputs to the states. Though transitions usually take time, we assume that state transitions are instantaneous (which is an abstraction). Some examples of state transition systems are: digital systems, vending machines, etc. A system containing only a finite number of states and transitions among them is called a finite-state transition system. Finite-state transition systems can be modeled abstractly by a mathematical model called finite automation Deterministic Finite (-state) Automata Informally, a DFA (Deterministic Finite State Automaton) is a simple machine that reads an in- put string one symbol at a time and then, after the input has been completely read, decides whether to accept or reject the input. As the symbols are read from the tape, the automaton can change its state, to reflect how it reacts to what it has seen so far. A machine for which a deter- ministic code can be formulated, and if there is only one unique way to formulate the code, then the machine is called deterministic finite automata. Thus, a DFA conceptually consists of 3 parts: 1. A tape to hold the input string. The tape is divided into a finite number of cells. Each . cell holds a symbol from 2. A tape head for reading symbols from the tape 3. A control , which itself consists of 3 things: o finite number of states that the machine is allowed to be in (zero or more states are designated as accept or final states), o a current state, initially set to a start state, o a state transition function for changing the current state. An automaton processes a string on the tape by repeating the following actions until the tape head has traversed the entire string: 1. The tape head reads the current tape cell and sends the symbol s found there to the control. Then the tape head moves to the next cell. 2. he control takes s and the current state and consults the state transition function to get the next state, which becomes the new current state. Once the entire string has been processed, the state in which the automation enters is examined. If it is an accept state , the input string is accepted ; otherwise, the string is rejected . Summariz- ing all the above we can formulate the following formal definition: Deterministic Finite State Automaton : A Deterministic Finite State Automaton (DFA) is a 5-tuple : • Q is a finite set of states. • is a finite set of input symbols or alphabet is the “next state” transition function (which is total ). Intuitively, is a • function that tells which state to move to in response to an input, i.e., if M is in state q and sees input a, it moves to state . • is the start state. • is the set of accept or final states. Acceptance of Strings : A DFA accepts a string if there is a sequence of states in Q such that 1. is the start state. 2. for all . 3. Language Accepted or Recognized by a DFA : The language accepted or recognized by a DFA M is the set of all strings accepted by M , and is denoted by i.e. The notion of acceptance can also be made more precise by extending the transition function . Extended transition function : Extend (which is function on symbols) to a function on strings, i.e. . That is, is the state the automation reaches when it starts from the state q and finish processing the string w. Formally, we can give an inductive definition as follows: The language of the DFA M is the set of strings that can take the start state to one of the accepting states i.e. L(M) = M accepts w = Example 1 : is the start state It is a formal description of a DFA. But it is hard to comprehend. For ex. The language of the DFA is any string over 0, 1 having at least one 1 We can describe the same DFA by transition table or state transition diagram as follow- ing: Transition Table : 0 1 It is easy to comprehend the transition diagram. Explanation : We cannot reach find state w/0 or in the i/p string. There can be any no. of 0's at the beginning. ( The self-loop at on label 0 indicates it ). Similarly there can be any no. of 0's & 1's in any order at the end of the string. Transition table : It is basically a tabular representation of the transition function that takes two arguments (a state and a symbol) and returns a value (the “next state”). • Rows correspond to states, • Columns correspond to input symbols, • Entries correspond to next states • The start state is marked with an arrow • The accept states are marked with a star (). 0 1 (State) Transition diagram : A state transition diagram or simply a transition diagram is a directed graph which can be constructed as follows: 1. For each state in Q there is a node. 2. There is a directed edge from node q to node p labeled a iff . (If there are several input symbols that cause a transition, the edge is labeled by the list of these symbols.) 3. There is an arrow with no source into the start state. 4. Accepting states are indicated by double circle. 5. 6. Here is an informal description how a DFA operates. An input to a DFA can be any . st ring Put a pointer to the start state q. Read the input string w from left to right, one symbol at a time, moving the pointer according to the transition function, . If the next symbol of w is a and the pointer is on state p, move the pointer to . When the end of the input string w is encountered, the pointer is on some state, r. The string is said to be accepted by the DFA if and rejected if . Note that there is no formal mechanism for moving the pointer. 7. A language is said to be regular if L = L(M) for some DFA M. Regular Expressions: Formal Definition We construct REs from primitive constituents (basic elements) by repeatedly applying certain recursive rules as given below. (In the definition) Definition : Let S be an alphabet. The regular expressions are defined recursively as follows. Basis : i) is a RE ii) is a RE iii) , a is RE. These are called primitive regular expression i.e. Primitive Constituents Recursive Step : If and are REs over, then so are i) ii) iii) iv) Closure : r is RE over only if it can be obtained from the basis elements (Primitive REs) by a finite no of applications of the recursive step (given in 2). Example : Let = 0,1,2 . Then (0+21)(1+ F ) is a RE, because we can construct this expression by applying the above rules as given in the following step. Steps RE Constructed Rule Used 1 1 Rule 1(iii) 2 Rule 1(i) 3 Rule 2(i) & Results of Step 1, 2 1+ 4 Rule 2(iv) & Step 3 (1+ ) 5 2 1(iii) 6 1 1(iii) 7 21 2(ii), 5, 6 8 0 1(iii) 9 0+21 2(i), 7, 8 10 (0+21) 2(iv), 9 11 (0+21) 2(iii), 10 12 (0+21) 2(ii), 4, 11 Language described by REs : Each describes a language (or a language is associated with every RE). We will see later that REs are used to attribute regular languages. Notation : If r is a RE over some alphabet then L(r) is the language associate with r . We can define the language L(r) associated with (or described by) a REs as follows. 1. is the RE describing the empty language i.e. L( ) = . 2. is a RE describing the language i.e. L( ) = . 3. , a is a RE denoting the language a i.e . L(a) = a . 4. If and are REs denoting language L( ) and L( ) respectively, then i) is a regular expression denoting the language L( ) = L( ) ∪ L( )

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.