Theory of computation notes

 THEORY OF COMPUTATION LECTURE NOTES

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

Automata theory (also known as Theory Of Computation) is a theoretical branch of Computer Science and Mathematics, which mainly deals with the logic of computation with respect to simple machines, referred to as automata. 

Automata* enables scientists to understand how machines compute the functions and solve problems. The main motivation behind developing Automata Theory was to develop methods to describe and analyze the dynamic behavior of discrete systems. 

Automata originated from the word “Automaton” which is closely related to “Automation”.

Basic Terminologies of Theory of Computation:

Now, let’s understand the basic terminologies, which are important and frequently used in the Theory of Computation. 

Symbol: 

A symbol (often also called a character) is the smallest building block, which can be any alphabet, letter, or picture. 

Alphabets (Σ): 

Alphabets are a set of symbols, which are always finite. 

String: 

A string is a finite sequence of symbols from some alphabet. A string is generally denoted as w and the length of a string is denoted as |w|. 

Empty string is the string with 
zero occurrence of symbols, 
represented as ε.

Number of Strings (of length 2) 
that can be generated over the alphabet {a, b}:
                     -   -
                     a   a
                     a   b
                     b   a
                     b   b

Length of String |w| = 2
Number of Strings = 4


Conclusion:
For alphabet {a, b} with length n, number of 
strings can be generated = 2n.

Note: If the number of symbols in the alphabet Σ is represented by |Σ|, then a number of strings of length n, possible over Σ is |Σ|n.

Closure Representation in TOC:

L+: It is a Positive Closure that represents a set of all strings except Null or ε-strings.

L*: It is “Kleene Closure“, that represents the occurrence of certain alphabets for given language alphabets from zero to the infinite number of times. In which ε-string is also included.

From the above two statements, it can be concluded that:

L* = εL+

Example:
(a) Regular expression for language accepting all combination of g's over Σ={g}:
                                         R = g*
                               R={ε,g,gg,ggg,gggg,ggggg,...}
                               
(b) Regular Expression for language accepting all combination of g's over Σ={g} :
                                         R = g+
                               R={g,gg,ggg,gggg,ggggg,gggggg,...}

Note: Σ* is a set of all possible strings(often power set(need not be unique here or we can say multiset) of string) So this implies that language is a subset of Σ*.This is also called a “Kleene Star”.

Kleene Star is also called a “Kleene Operator” or “Kleene Closure”. Engineers and IT professionals make use of Kleene Star to achieve all set of strings which is to be included from a given set of characters or symbols. It is one kind of Unary operator. In Kleene Star methodology all individual elements of a given string must be present but additional elements or combinations of these alphabets can be included to any extent.

Example:
Input String: "GFG".
Σ* = { ε,"GFG","GGFG","GGFG","GFGGGGGGGG","GGGGGGGGFFFFFFFFFGGGGGGGG",...}  
(Kleene Star is an infinite set but if we provide any grammar rules then it can work as a finite set.
Please note that we can include ε string also in given Kleene star representation.)

Language: 

A language is a set of strings, chosen from some Σ* or we can say- ‘A language is a subset of Σ* ‘. A language that can be formed over ‘ Σ ‘ can be Finite or Infinite.

Example of Finite Language: 
          L1 = { set of string of 2 }
         L1 = { xy, yx, xx, yy }

Example of Infinite Language:
         L1 = { set of all strings starts with 'b' }
         L1 = { babb, baa, ba, bbb, baab, ....... }