Introduction to Theory of Computation

Introduction to Theory of Computation

Theory of Computation studies what problems can be solved by computers and how efficiently.

Automata

Automaton is an abstract model of computation.

Types:

• Finite Automata (FA)
• Pushdown Automata (PDA)
• Turing Machine (TM)

Languages

Language is a set of strings over an alphabet.

Alphabet (Σ): Finite set of symbols

String: Sequence of symbols from alphabet

Language (L): Set of strings

Example:

• Alphabet: {0, 1}
• Language: {ε, 0, 1, 00, 01, 10, 11, ...}

Grammars

Grammar generates strings in a language.

Grammar G = (V, T, P, S):

• V: Variables (non-terminals)
• T: Terminals
• P: Production rules
• S: Start symbol

Chomsky Hierarchy

Type 0: Unrestricted Grammar

• Turing Machine
• Recursively enumerable languages

Type 1: Context-Sensitive Grammar

• Linear Bounded Automaton
• Context-sensitive languages

Type 2: Context-Free Grammar

• Pushdown Automaton
• Context-free languages

Type 3: Regular Grammar

• Finite Automaton
• Regular languages

GATE CS Weightage

Theory of Computation typically accounts for:

• 8-12 marks out of 100 in GATE CS
• Theoretical subject
• Requires understanding of automata and languages

Important Topics for GATE CS

1. Finite Automata (High Priority)

• DFA, NFA
• Regular expressions

1. Context-Free Grammars (High Priority)

• CFG, PDA
• Parsing

1. Turing Machines (Medium Priority)

• Decidability
• Computability

1. Regular Languages (High Priority)

• Closure properties
• Pumping lemma

1. Context-Free Languages (High Priority)

• Closure properties
• Pumping lemma