Theory of Computation

Syllabus

UNIT I

1. Mathematical Preliminaries.2. Why Study Theory of computations and Key Ideas, 3. Finite State Machines & its Model. 4. Finite Automata (Deterministic and Nondeterministic): Notations, Languages, String acceptance/processing, 5. Equivalence of DFA’s and NDFA’s, conversion, automata with transition, 6. minimization of Finite Automata. 7. Moore and Mealy machines.

UNIT II

1. The idea of Formal languages, 2. Languages& Grammars: definitions, relations, operations. 3. Chomsky Hierarchy. 4. Languages of Automata: Regular Language, Regular Expression, Constructing Regular Expressions, Converting Regular Expressions to Automata, Equivalence of Regular Expressions, Method for Constructing Regular Expressions, Regular Expressions in Practice Regular Grammar and Finite Automata, Pumping Lemma.

UNIT III

1. Context-free Languages and Grammars. 2. Pushdown Automata: Definition, Model, Language, 3. Notation, Deterministic & Nondeterministic PDA, 4. Constructing PDAs, Constructing CFGs to PDAs, Converting PDAs to CFGs, 5. Parsing & PDA, 6. Pumping Lemma for CFLs.

UNIT IV 

1. Turing machines and its variants, 2. CT thesis, 3. Recursive and Recursively enumerable languages. 4. TM & Type – O grammar, Decidable and undecidable problems. 5. Turing machines as a recognizer and acceptors. 6. Turing machines as a transducer.

UNIT V 

1. Undecidability & Computability: Undecidable problems, 2. Computability: Recursive function. 3. Complexity: Time complexity, 4. NP Completeness, 5. Complexity classes P& NP.

What is TOC ?

Theory of Computation (TOC) is a branch of computer science and mathematics that studies how machine compute functions and solve problems. It also works on understanding the fundamental principal of computation. It tells about how a machine processes and solve the problem.

What are the basic terminologies used in TOC ?

The basic terminologies used in TOC are :
  1. Symbols
  2. Alphabets
  3. Strings
  4. Language
1. Symbol : A symbol is a smallest building blocks, which can be any alphabet, letter or character.
eg: 1,2,3,4,a,b,c,@,&,* etc.

2. Alphabet (Σ) : Alphabets are the finite set of symbols.
eg: Σ(a,b)

3. String (w) : Collection or sequence of alphabets. It tells about the quantity of the word or symbols that can be included in the string. (The length of the string is denoted by |w|).
eg:  let Σ(a,b) be the alphabets given , then the possible strings are {a,b,aa,ab,bb,ba.......}.
 
4. Language : The language is a set or a collection of strings. Multiple strings together makes a language. A language can be of 2 types :
            1. Finite (fixed no. of strings)
            2. Infinite (infinite no. of strings)

Σ represents alphabets 

Kleene Closure Σ* :The Kleene Closure (Kleene Star) is the set of all the strings with all possible length. 
Positive Closure Σ+ : The Positive Closure (Kleene Plus) is the set of all string excluding the null set (set of empty string(Σ0 or ε or λ ))


What is the use of Kleene Star in the study of formal language ? 


A Kleene Star is a mathematical operation used in automata theory and formal languages which allows for the construction of sets containing any number or repetition of a specific symbol or set of symbols.

What is Grammar in TOC?


Grammar is a standard way of representing a language. A grammar is defined as a quadruple, i.e G = {V,T,P,S} where, 

V : Variable (upper case)
T : Terminal (lower case)
P : Production rule
S : Start symbol

What is automata ?


Automata is a branch of computer science and mathematics that is the study of abstract machine and the computation problem that can be solved using these machines. These abstract machine is called automata.

There are 4 types of automata (machine) :
  1. FA (Finite Automata)
  2. PDA (Push Down Automata)
  3. LBA (Lower Bound Automata) 
  4. TM (Turing Machine)
1. Finite Automata (FA): FA is an imaginary machine which takes input as a string and generate output as string accepted or string rejected. It is also known as Discrete automata. It has finite no. of state.

FA is represented by 5 tuple.

F : {Q,Σ, δ,q0,F} where,
  1. Q : non empty finite set of states.
  2. Σ : finite and non empty set of symbols
  3. δ : transition Function
  4. q0 : start (without reading the input symbol, the machine is at 0 (initial state)). 
  5. F : set of finite final state.
There are 2 types of automata :
  1. DFA (Deterministic Finite Automata)  
  2. NDFA (Non-Deterministic Finite Automata)

1.DFA (Deterministic finite Automata): 

The FA are called DFA if the machine read an input string 1 symbol at a time. There is only one path for specific input from the current state to the next state. DFA cannot change state without any input character.                

δ: Q x ∑→Q  

2.NDFA (Non-Deterministic Finite Automata): 

Non-Deterministic Finite Automata is also known as NFA, the NFA is easier to construct than DFA. Every NFA is not a DFA, but each NFA can be translated into DFA. It contains multiple next state and contains null transition

δ: Q x ∑ →2^Q

Difference between DFA & NFA

DFA (Deterministic Finite Automaton)

  1. Determinism: Exactly one transition is defined for each state and input symbol.
  2. Transition Function: δ:Q×Σ→Q\delta: Q \times \Sigma \to Q (maps a state and input symbol to a single state).
  3. Empty String Transitions (ε): Not allowed.
  4. Execution: Processes input by following a single, well-defined path.
  5. Acceptance of Input: Accepts an input string if it ends in an accepting state.
  6. Ease of Implementation: Easier to implement due to its deterministic nature.
  7. Expressive Power: Recognizes regular languages.
  8. State Complexity: May require more states than an equivalent NFA.
  9. Conversion: Cannot be directly converted to an NFA but can simulate one.

NFA (Nondeterministic Finite Automaton)

  1. Determinism: Allows multiple or no transitions for a given state and input symbol.
  2. Transition Function: δ:Q×Σ→2Q\delta: Q \times \Sigma \to 2^Q (maps a state and input symbol to a set of states).
  3. Empty String Transitions (ε): Allowed; transitions can occur without consuming input.
  4. Execution: Simultaneously explores multiple paths or branches in the computation.
  5. Acceptance of Input: Accepts an input string if at least one computational path ends in an accepting state.
  6. Ease of Implementation: More complex to implement due to handling nondeterminism.
  7. Expressive Power: Recognizes regular languages, equivalent in power to DFA.
  8. State Complexity: Typically requires fewer states than an equivalent DFA.
  9. Conversion: Can be converted to an equivalent DFA, though the DFA may have exponentially more states.

















Comments

Post a Comment