Theory of Computation (TOC) Study Material
Theory of Computation (TOC) is a foundational subject in computer science that deals with the
mathematical
properties of computational models. The main topics of TOC include automata theory, formal
languages,
computability, and complexity theory. This material covers the essential concepts of TOC in an
easily
understandable way, with examples, definitions, and exercises to help reinforce your learning.
The material is structured as follows:
1. Basics of TOC
2. Regular Languages and Automata
3. Context-Free Grammars (CFG)
4. Pushdown Automata (PDA)
5. Turing Machines (TM)
6. Decidability and Undecidability
7. Complexity Theory
Each section includes theoretical explanations followed by solved problems and practice exercises.
1. Basics of Theory of Computation
The Theory of Computation (TOC) is concerned with understanding the nature of computation,
defining problems that can be solved by algorithms, and categorizing those problems based on
complexity and solvability. Below are the basic elements of TOC:
1. **Alphabets**: A set of symbols used to construct strings. Example: {a, b} is an alphabet.
2. **Strings**: A sequence of symbols from an alphabet. Example: "abab" is a string over the
alphabet {a, b}.
3. **Languages**: A set of strings over a given alphabet. Example: L = {a, ab, baa} is a language
over {a, b}.
4. **Operations on Strings and Languages**:
- Union, intersection, concatenation, and Kleene star are some fundamental operations.
**Important Concepts**:
- **Set Theory**: Set operations and their application in defining languages and problems.
- **Formal Language**: A set of strings that are generated based on specific rules or patterns.
2. Regular Languages and Automata
Regular languages are the simplest class of languages that can be recognized by finite automata.
These languages can be described using regular expressions.
### Regular Expressions (RE):
A regular expression is a sequence of characters that defines a search pattern. Example:
- The regular expression 'a*b' matches strings containing any number of 'a's followed by 'b'
(including "b", "ab", "aaab").
### Finite Automata (FA):
Finite automata are abstract machines that accept or reject strings based on the states they
traverse.
They can be classified as:
- **Deterministic Finite Automata (DFA)**: Every state has exactly one transition for each input
symbol.
- **Non-deterministic Finite Automata (NFA)**: States can have multiple transitions for a given input
symbol.
**Conversion from NFA to DFA**:
The process of converting a Non-deterministic Finite Automaton (NFA) to a Deterministic Finite
Automaton (DFA) is essential for simplifying automata.
### Pumping Lemma for Regular Languages:
The Pumping Lemma is used to prove that certain languages are not regular. It states that for any
regular language,
there exists a "pumping length" such that any string longer than this length can be decomposed into
substrings,
which can be "pumped" (repeated) to generate new strings that still belong to the language.
**Exercise**:
1. Convert the NFA for recognizing binary strings divisible by 3 into an equivalent DFA.
