TOC Notes PDF

Video chapters Chapter-1 (Basic Concepts and Automata Theory): Introduction to Theory of Computation- Automata, Computability and Complexity, Alphabet, Symbol, String, Formal Languages, Deterministic Finite Automaton (DFA)- Definition, Representation, Acceptability of a String and Lan...

Video chapters Chapter-1 (Basic Concepts and Automata Theory): Introduction to Theory of Computation- Automata, Computability and Complexity, Alphabet, Symbol, String, Formal Languages, Deterministic Finite Automaton (DFA)- Definition, Representation, Acceptability of a String and Language, Non Deterministic Finite Automaton (NFA), Equivalence of DFA and NFA, NFA with ε- Transition, Equivalence of NFA’s with and without ε-Transition, Finite Automata with output- Moore Machine, Mealy Machine, Equivalence of Moore and Mealy Machine, Minimization of Finite Automata. Chapter-2 (Regular Expressions and Languages): Regular Expressions, Transition Graph, Kleen’s Theorem, Finite Automata and Regular Expression- Arden’s theorem, Algebraic Method Using Arden’s Theorem, Regular and Non-Regular Languages- Closure properties of Regular Languages, Pigeonhole Principle, Pumping Lemma, Application of Pumping Lemma, Decidability- Decision properties, Finite Automata and Regular Languages Chapter-3 (Regular and Non-Regular Grammars): Context Free Grammar(CFG)-Definition, Derivations, Languages, Derivation Trees and Ambiguity, Regular Grammars-Right Linear and Left Linear grammars, Conversion of FA into CFG and Regular grammar into FA, Simplification of CFG, Normal Forms- Chomsky Normal Form(CNF), Greibach Normal Form (GNF), Chomsky Hierarchy, Programming problems based on the properties of CFGs. Chapter-4 (Push Down Automata and Properties of Context Free Languages): Nondeterministic Pushdown Automata (NPDA)- Definition, Moves, A Language Accepted by NPDA, Deterministic Pushdown Automata(DPDA) and Deterministic Context free Languages(DCFL), Pushdown Automata for Context Free Languages, Context Free grammars for Pushdown Automata, Two stack Pushdown Automata, Pumping Lemma for CFL, Closure properties of CFL, Decision Problems of CFL, Programming problems based on the properties of CFLs. Chapter-5 (Turing Machines and Recursive Function Theory): Basic Turing Machine Model, Representation of Turing Machines, Language Acceptability of Turing Machines, Techniques for Turing Machine Construction, Modifications of Turing Machine, Turing Machine as Computer of Integer Functions, Universal Turing machine, Linear Bounded Automata, Church’s http://www.knowledgegate.in/gate Thesis, Recursive and Recursively Enumerable language, Halting Problem, Post’s Correspondance Problem, Introduction to Recursive Function Theory.  Chapter-1 (Basic Concepts and Automata Theory): Introduction to Theory of Computation- Automata, Computability and Complexity, Alphabet, Symbol, String, Formal Languages, Deterministic Finite Automaton (DFA)- Definition, Representation, Acceptability of a String and Language, Non Deterministic Finite Automaton (NFA), Equivalence of DFA and NFA, NFA with ε-Transition, Equivalence of NFA’s with and without ε-Transition, Finite Automata with output- Moore Machine, Mealy Machine, Equivalence of Moore and Mealy Machine, Minimization of Finite Automata. http://www.knowledgegate.in/gate  INTRODUCTION TO THEORY OF COMPUTATIONS The theory of computation is a branch of theoretical computer science that deals with the study of algorithms and computational complexity. It aims to answer fundamental questions about what can be computed how efficiently it can be done and what limitations exist in terms of computational power. http://www.knowledgegate.in/gate  As word suggests ‘TOC’ is the study of 'mathematical' machines or systems called automata. Theory of computation can be considered as the study of all kinds of computational model in the field of computer science and it also considers how efficiently the problem can be solved (but not is depth). http://www.knowledgegate.in/gate  PROBLEM Now a day’s machines (digital, analog, mechanical) play a very important role in the development of human, we need some mechanism (language) to communicate with the machines. http://www.knowledgegate.in/gate  SOLUTION We need a language for communication with machines. But we do not require natural languages to communicate with the machines, as natural languages are very complex and machine interaction require very fewer complex languages compare to natural languages. http://www.knowledgegate.in/gate  Languages can be of two types formal languages and informal languages, here in this subject we will only discuss formal languages. Dictionary defines the term informally as ‘a system suitable for the expression of certain ideas, facts or concepts including a set of symbols for their manipulation’. http://www.knowledgegate.in/gate  METHODS TO DEFINE LANGUAGE In natural language we define the list of words in a dictionary because they are finite and predefined, but we cannot list all the sentence which can be formed using these words as they are infinite. So, we have a mechanism called grammar/rules using which we can decide which sentence is valid and which is invalid. http://www.knowledgegate.in/gate  MATHEMATICL DEFINATION OF LANGUAGE SYMBOL- Symbols are the basic building blocks, which can be any character/token. (cow, sheep, , white flag, , , etc.) (in English we called them as letters). http://www.knowledgegate.in/gate  ALPHABET- An alphabet is a finite non empty set of symbols, (every language has its own alphabet). here in toc, we use symbol Σ for depicting alphabet. e.g. Σ = {0,1}. for English Σ = {a, b, c, …., z} (in English also alphabet is a set of letters, thought in general we called them as alphabet). http://www.knowledgegate.in/gate  STRING - It is a finite sequence of symbols (which are the member of set alphabet). E.g. Σ = {a, b} String- aabb, aa, b, so on. (in English we called them as words). http://www.knowledgegate.in/gate  LANGUAGE - A language is defined as a set of strings. (in natural language (set of words(predefined) and grammar) we apply this model from words to sentence). In the next level we consider programs as a string and programming constructs/tokens like int, floats as letters/symbols. http://www.knowledgegate.in/gate  Similarly, in our system we have finite number of symbols/letters but using those letters we can generate infinite strings/words. So, we may have languages that have infinite number of words, so it is not possible for us to list them, we have to use some framework, which can somehow represent the same language. There are mainly two methods to represent a language by a grammar that generates a language [RG generate RL] by a machine that accepts a language [FA accept RL language] http://www.knowledgegate.in/gate Machine Grammar http://www.knowledgegate.in/gate  The Theory of Formal Languages is a branch of theoretical computer science that deals with the study of formal languages and their properties. The theory of formal languages includes the study of formal grammars, which are used to define the syntax of formal languages, and automata theory, which deals with the study of abstract machines used to recognize, generate, or process formal languages. Some of the key concepts studied in the theory of formal languages include regular languages, context-free languages, context-sensitive languages, recursively enumerable languages, and the Chomsky hierarchy. The theory of formal languages has important applications in areas such as compilers, parsers, and other software engineering tools, as well as in the design of programming languages and the study of natural language processing. http://www.knowledgegate.in/gate Q if ∑ = {a, b} then, find the following? ∑0 = ∑1 = ∑2 = ∑3 = http://www.knowledgegate.in/gate  ∑K is the set of all the strings from the alphabet ∑ of length exactly K. ∑k = {W | |W| = K} (using the symbols from the alphabet ∑) http://www.knowledgegate.in/gate Kleene closure- If ∑ is a set of symbols, then we use ∑* to denote the set of strings obtained by concatenating zero or more symbols from ∑ of any length, in general any string of any length which can have only symbols specified in ∑. ∑* = ⋃!"$ !"# 𝑤 𝑤 = 𝑖} (using the symbols from the alphabet ∑) http://www.knowledgegate.in/gate Positive closure – If ∑ is a set of symbols, then we use ∑+ to denote the set of strings obtained by concatenating one or more symbols from ∑ of any length, in general any string of any length which can have only symbols specified in ∑ (except ∈). ∑+ = ⋃!"$ !"% 𝑤 𝑤 = 𝑖} (using the symbols from the alphabet ∑) http://www.knowledgegate.in/gate  Automaton An automaton is defined as a self-operating system where energy, materials and information are transformed, transmitted and used for performing some functions without direct participation of man. The term is often used to describe a theoretical machine that operates according to a set of rules and is capable of carrying out complex operations without human intervention. Example: automatic machine tools, automatic packing machines, and automatic photo printing machines. http://www.knowledgegate.in/gate  FINITE AUTOMATA A Finite automaton is a model that has a finite set of states (represented in the figure by circles) and its control moves from one state to another state in response to external inputs (represented by arrows). It is an abstract machine that is used to recognize patterns in strings of symbols. Finite automata are widely used in computer science for pattern matching, lexical analysis, and parsing, among other applications. http://www.knowledgegate.in/gate  Finite automata can be broadly classified into two types- 1. Finite automata without output 1. Deterministic finite automata. 2. Non deterministic finite automata. 3. Non deterministic finite automata with ∈ 2. Finite automata with output 1. Moore machine 2. Mealy machine http://www.knowledgegate.in/gate  In general, this type of automata is characterized by machine having no temporary storage, as it is severely limited in its capacity to remember things during the computation. Only finite amount of information can be in the control unit by placing the unit into a specific state but since the number of states is finite, a finite automaton can only deal with situation in which the information to be stored at any time is strictly bounded. http://www.knowledgegate.in/gate  DETERMINISTIC FINITE AUTOMATA A deterministic finite automaton (DFA) is defined by 5-tuple (Q,S,d,S,F) where: Q is a finite and non-empty set of states S is a finite non-empty set of finite input alphabet d is a transition function, ( d: Q × S à Q) S is initial state (always one) (SÎ Q) F is a set of final states (F Í Q) (0 Q× ℾ × (L/R/S). TM with one way infinite tape (Semi infinite tape) http://www.knowledgegate.in/gate  Offline TM, this TM have a restriction that input can not be changed Jumping TM, where it is allowed to take more that one moves in one transaction d: Q ×ℾ -> Q× ℾ × (L/R) ×{n}. Non erasing TM, (where input can not be converted to blank) Always writing TM, (after reading a symbol from tape it must be replaced with other symbol) Multidimensional TM d: Q ×ℾ -> Q× ℾ × (L/R/U/D) Multi-head TM FA with a Queue TM with only 3 states Multi-tape Turing Machine with stay option and at most 2 states. Non-Deterministic TM d: Q ×ℾ -> 2 Q× ℾ × (L/R) A NPDA with two independent stacks d: Q ×(S U Î) × ℾ × ℾ -> 2 Q× ℾ* × ℾ* http://www.knowledgegate.in/gate Q Consider the Turing machine M defined below 0 1 B Choose the false statement ® Q0 (Q0, 0, R) (Q2, 1, L) (Qf, -, -) a) The machine loops on 01 Q1 (Q2, 1, L) (Q1, 1, R) (Qf, -, -) Q2 (Q2, 1, L) (Q2, 0, L) (Qf, -, -) b) The machine does not accept 0000 *Qf --- --- --- c) The machine accepts strings ending with a 1 d) The machine accepts strings ending with 10 http://www.knowledgegate.in/gate  Halt The state of Turing machine, where no transition is defined or required is known as Halt. There are two types of Halt- Final Halt- Machine has been halted on final state, then it is known as Final halt and hence it depicts that machine is accepted. Non-Final Halt-Machine has been halted on non- final state, then it is known as non- final halt and hence the string is rejected. After taking an input string, there are three possibilities for Turing Machine It may go to Final halt. It may go to Non- Final halt. It may go into Infinite loop. Final Halt and Non- Final Halt have been described above. After taking an input string, if the machine goes to infinite loop, then we can’t say whether the string is Accepted/Rejected. http://www.knowledgegate.in/gate  So, broadly Recursively Enumerable Languages are categorized as- Recursive Set- The Language L, which is accepted by Turing Machine, is said to be recursive set, where for all, ‘w’ that belongs to L, machine will go to final halt, and for all ‘w’ that does not belongs to L, machine will go to non-final halt. Hence, membership property is defined here. Recursively Enumerable Set- The language L, which is accepted by Turing Machine is said to be REL, where for all, ‘w’ that belongs to L, machine will go to final halt, and for all ‘w’ that does not belongs to L, machine will either go to non-final halt or infinite loop. Hence, membership property is not defined here. If a set and its complement both are recognizable, then the set is decidable. There are some sets which are not recognizable (even members can’t be identified) because there are more languages than programs. http://www.knowledgegate.in/gate Universal Turing Machine http://www.knowledgegate.in/gate  Universal Turing Machine In computer science, a universal Turing machine (UTM) is a Turing machine that simulates an arbitrary Turing machine on arbitrary input. The universal machine essentially achieves this by reading both the description of the machine to be simulated as well as the input to that machine from its own tape. http://www.knowledgegate.in/gate  Every Turing machine computes a certain fixed partial computable function from the input strings over its alphabet. In that sense it behaves like a computer with a fixed program. However, we can encode the action table of any Turing machine in a string. Thus we can construct a Turing machine that expects on its tape a string describing an action table followed by a string describing the input tape, and computes the tape that the encoded Turing machine would have computed. Turing described such a construction in complete detail in his 1936 paper: "It is possible to invent a single machine which can be used to compute any computable sequence. If this machine U is supplied with a tape on the beginning of which is written the S.D ["standard description" of an action table] of some computing machine M, then U will compute the same sequence as M. http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate Linear Bounded Automata http://www.knowledgegate.in/gate A Linear Bounded Automaton (LBA) is similar to Turing Machine with property stated below: Turing Machine with a bounded finite length of the tape. http://www.knowledgegate.in/gate  Turing-Church Thesis Concept Origin: Independently developed by Alan Turing and Alonzo Church in the 1930s, establishing a fundamental principle in computer science about computable functions. http://www.knowledgegate.in/gate 1.Turing Machines: Turing proposed the concept of a 'Turing machine', a theoretical computing machine that can simulate any algorithm's logic. 2.Church's Lambda Calculus: Church introduced lambda calculus, a formal system for expressing computation based on function abstraction and application. 3.Equivalent Models: The thesis states that what can be computed on a Turing machine can also be computed in Church's lambda calculus, implying both models are equivalent in their computational power. http://www.knowledgegate.in/gate  The Post Correspondence Problem (PCP) is a significant problem in the field of theoretical computer science. It was introduced by Emil Post in 1946 and is known for its undecidability. Here are the main points: Basic Concept: The problem involves two lists of words (strings of symbols) over a common alphabet. The challenge is to find a sequence of indices where the concatenation of the words in the first list, in that sequence, is equal to the concatenation of the words in the second list in the same sequence. A = {1, 110, 0111} B = {111, 001, 11} http://www.knowledgegate.in/gate  Undecidability: The Post Correspondence Problem is known to be undecidable, meaning there is no algorithm that can determine for every instance of the problem whether or not a solution exists. This undecidability is a crucial aspect in the theory of computation, particularly in understanding the limits of algorithmic solvability. A = {b, babbb, ba} B = {bbb, ba, a} http://www.knowledgegate.in/gate  Decision properties Following properties are decidable in case a RS. Membership All properties are undecidable in case of a REL. http://www.knowledgegate.in/gate  RL DCFL CFL CSL RS RES Emptiness Y Y Y X N N Non- Y Y Y X N N Emptiness Finiteness Y Y Y X N N Infiniteness Y Y Y X N N Membershi Y Y Y X Y N p Equality Y N N X N N Ambiguity Y N N X N N ∑* Y N N X N N Halting Y Y Y X Y N http://www.knowledgegate.in/gate  Closure Properties of Recursive Set Recursive languages are closed under following operations Union Concatenation Intersection Reverse Complement Inverse homomorphism Intersection with regular set Set Difference Recursive languages are not closed under following operations Kleen closure Homomorphism Substitution http://www.knowledgegate.in/gate  Closure Properties of Recursive Enumerable Set Recursive Enumerable are closed under following operations Union Concatenation Kleen Closure Intersection Substitution Homomorphism Inverse Homomorphism Intersection with regular set Reverse operation Recursive Enumerable are not closed under following operations Compliment Set Difference http://www.knowledgegate.in/gate  RL DCFL CFL CSL RS RES Union Y N Y Y Y Y Intersection Y N N Y Y Y Complement Y Y N Y Y N Set Difference Y N N Y Y N Kleene Closure Y N Y Y Y Y Positive Closure Y N Y Y Y Y Concatenation Y N Y Y Y Y Intersection with Y Y Y Y Y Y regular set Reverse Y Y Y Y Y Y Subset N http://www.knowledgegate.in/gate N N N N N  RL DCFL CFL CSL RS RES Homomorphism Y N Y N N Y ∈ Free Homomorphism Y N Y Y Y Y Inverse Homomorphism Y Y Y Y Y Y Substitution Y N Y N N Y ∈ Free Substitution Y N Y Y Y Y Quotient with regular set Y Y Y N Y Y http://www.knowledgegate.in/gate