SYLLABUS for GATE CS&IT
Regular Expressions and Finite automata. Context-free grammers and push-down automata.
Regular and context-free Languages, pumping lemma. Turing Machines and Undecidability.
Last 5 years's Analysis
What TOC is about?
It is mainly about what kind of things can you really compute mechanically, how fast and how much space does it take.
Will help you understand how people have thought about computer science as a science in the past 50 years.
Theory Of Computation(TOC) is the branch that deals with how efficiently problems can be solved on a model of computation using an algorithm.
The field is divided into three major branches
- Automata Theory and language
- Computability Theory
- Computational Complexity Theory
Automata Theory:
It is the study of Abstract Machines and Self Acting machines
Formal Language:
Recognized by an automation.
Different kinds of Automata
Automata are distinguished by the temporary memory
- Finite Automata: no temporary memory
- Pushdown Automata: stack
- Turing Machines: random access memory
Objective of Automata Theory:
Determine the power of different computational models, or which model can solve more problems than the other.
