Theory of Computation (TOC) Overview

THEORY OF COMPUTATION (TOC)

Introduction of Theory of Computation (TOC)

Automata theory (also identified as Theory Of Computation) is a theoretical department of Computer Science and Mathematics, which mostly concerned with the good judgment of computation with respect to straight forward machines, generally known as automata.

The key motivation in the back of constructing the Automata idea was to describe and analyze the dynamic behavior of discrete systems.

The word “Automata” is obtained from the Greek word “αὐτόματα” which signifies “self-acting”. which is firmly identified with “Automation”.

An automaton is used for performing some functions without direct participation of man.

Example = automatic machine tools, automatic packing machines, and automatic photo printing machines, etc.

Types Of Automata

Automation without a memory: output depends only on the input
Automaton with a finite memory: output depends not only depends on the input as well as output too
Moore machine: the output depends only on the states of the machine
Mealy machine.: the output depends on the state as well as on the input at any instant of time

DFA	NDFA
Deterministic Finite Automata (DFA)	Non-deterministic Finite Automata (NFA)
Null (or ε) move is not allowed	Null (or ε) move is allowed
Q: set of all states.	Q: set of all states.
∑: set of input symbols. ( Symbols which machine takes as input)	∑: set of input symbols. ( Symbols which machine takes as input)
q: Initial state F: set of final state. δ Transition Function δ: Q X Σ → Q	q: Initial state F: set of final state. NFA Transition Function: δ: Q X ( Σ U ε ) → 2^Q

Some Important terminology used in Theory of Computation (TOC)

Here I am writing only Important Terminology of TOC, for Mathematical Terminology you have to visit Mathematical Notions And Terminology post also.

Symbols: Any letter, alphabet, or any picture.
E.g.: a, b, c, 0, 1, 2 ……
Alphabets: Finite set of symbols.
It is denoted by Σ
Σ is a collection of symbols.
E.g.: {a, b}, {0, 1, 2}
String: Sequence of symbols.
E.g.: a, b, 0, 1, aa, bb, ab, 01, …
Language: A Language is a collection of string.
Set of strings.
A language that is formed over Σ, It may be finite and infinite.
E.g.: Σ={0,1}
Automata: For solving the infinite language we used automata
It is a mathematical model or machine
whether the string is a part of language or not
Power of Σ:
Σ = {a,b} then
Σ° = Set of all string over Σ of length 0, {ε}
Σ¹ = Set of all strings over Σ of length 1, {a,b}
Σ² = Set of all strings over Σ of length 2, {aa, ab, bb, ba}
Cardinality: Number of elements in a set
Σ° Cardinality is 1
Σ¹ Cardinality is 2
Σ² Cardinality is 4 so on
ΣⁿCardinality = 2ⁿ
Note: If the alphabet is over two digits
Kleene Star (Σ^*): Σ^* is a unary operator , Σ, that gives the infinite set over Σ including λ.
Kleene Closure/Plus: The set Σ⁺is the infinite set of all possible strings of all possible lengths over Σ excluding λ.
Grammar: A Grammar ‘G’ is defined as quadruple: G = { V, T, P, S }
V = Variable, P = Production rule, T = Terminal, S = Start
Stander way of defining language.
Using grammar and Automata we declared this sentence follows rules of language or not.

Transition Digram

There is a node for the state in Q, which is represented by the circle
There is a directed edge from node q to node p labeled an if δ(q, a) = p.
In the start state, there is an → with no source.
Final states are represented by a double circle

Theory of computation (TOC) Syllabus

If you want to know the full syllabus of TOC for NTA UGC NET click here.

Here I have put some selected area where most of the questions come in NTA UGC NET

Regular Language and finite automata
Context-Free Language and Push down automata
REC, RE and Turing Machine
Closure Properties and Undecidability

REGULAR EXPRESSION
1. Properties of Regular Expression
2. Arden’s Theorem
FINITE AUTOMATA
1. Finding the minimum number of states
2. Minimization of DFA
3. NFA to DFA conversion
4. Pumping Lemma
5. Mealy and Moore machines
LANGUAGE
1. Identifying Regular
2. Identifying CFL
3. Identifying CSL
4. Identifying DCFL
GRAMMARS
1. 4 Types of Grammar
2. Chomsky Normal Form
3. Ambiguity Test
Properties
1. Closure Property
2. Decidable Property

TOC topics in GATE/NTA UGC NET

2019 = REGULAR & NON-REGULAR
2018 = NFA, GRAMMAR, CFL
2017 = REGULAR LANGUAGES, DFA, EPSILON NFA, UNDECIDABILITY, CFL, CFG, REGULAR EXPRESSION, TURING MACHINE
2016 = REGULAR GRAMMAR & EXPRESSION, RECURSIVELY ENUMERABLE, PDA
2015 = REGULAR EXPRESSION & LANGUAGES, PROPERTIES OF CFL, P, NP, NPH, NPC, CFG & CFL, TURING MACHINE