C Language
DSA
Software Engineering
Software Architecture
Operating System
Big Data
Data Mining and Warehousing
TOC
Ada
C++

Topics

  • 1. Why Study Theory of Computation?
  • 2. What is Computation?
  • 3. Subject of TOC
  • 4. Terms Used in Theory of Computation (TOC)
  • 5. Kleene Star, Kleene Plus, and Language
1. Why Study Theory of Computation?

The Theory of Computation (TOC) helps us understand:

  • Capabilities of machines

  • Problems that can be solved

  • Limitations of machines

It focuses on the logic and concepts of machines rather than hardware details.

Purpose:

  • Allows systematic thinking about what machines can do

  • Helps analyze computational tasks mathematically

2. What is Computation?

Computation = Any calculation or task performed by a machine (like a calculator, computer, etc.).

  • Computations are used to represent mathematical models such as:

    • Finite Automata (FA)

    • Pushdown Automata (PDA)

    • Turing Machine (TM)

3. Subject of TOC

TOC studies mathematical models of abstract machines and computational problems that these models can solve.

It is divided into three main branches:

Branch Focus Area
Automata Theory Deals with properties of mathematical models like FA, PDA, etc.
Computability Theory Studies what can and cannot be computed by a machine.
Complexity Theory Analyzes computable problems based on their difficulty (hardness).

 

4. Terms Used in Theory of Computation (TOC)

1. Symbol

  • A symbol is a single unit of input (a character) for a machine.

  • Symbols are used to build languages for machines.

Examples:

  • Digits: 0, 1, 2, 3

  • Alphabets: a, b, c

  • Special symbols: !, $, #, @, <, >, ?

2. Alphabet (Σ)

  • An alphabet is a finite, non-empty set of symbols.

  • Denoted by Σ.

Examples:

  • Σ = {0,1,2}

  • Σ = {a, b, f}

  • Σ = {A, B, C, Z}

3. String

  • A string is a finite sequence of symbols from an alphabet Σ.

  • Length of a string (|w|) = Number of symbols in the string.

Examples:

  • Σ = {0,1}, w = 01101001 → |w| = 8

  • Σ = {a,b}, w = abbaa → |w| = 5

  • w = E (empty string) → |w| = 0

4. Concatenation of Strings

  • Combining two strings x and y to form a new string.

Example:

  • x = abc, y = pqr

  • Concatenation: xy = abcpqr

5. Power of Alphabet (Σ^k)

  • Σ^k = Set of all strings of length k over alphabet Σ.

Examples:

  • Σ = {0,1}, k = 2 → Σ² = {00, 01, 10, 11}

  • Σ = {0,1}, k = 3 → Σ³ = {000, 001, 010, 011, 100, 101, 110, 111}

Notes:

  • Σ⁰ = {ε} → Set containing the empty string ε

  • Cartesian Product: Σ^k can be seen as repeated Cartesian product of Σ with itself k times.

5. Kleene Star, Kleene Plus, and Language

1. Kleene Star (Σ*)

  • Symbol: *

  • Definition: Unary operator on an alphabet Σ that represents the set of all possible strings of any length, including the empty string (ε).

  • Key Points:

    • Includes null (ε).

    • Produces an infinite set of strings.

  • Example:

    • Σ = {5, 6} → Σ* = {ε, 5, 6, 55, 56, 65, 66, 555, …}

    • Σ = {a, b} → Σ* = {ε, a, b, aa, ab, ba, bb, aaa, …}

2. Kleene Plus (Σ⁺)

  • Symbol: +

  • Definition: Unary operator on an alphabet Σ that represents the set of all possible strings of any length, excluding the empty string (ε).

  • Key Points:

    • Does not include ε.

    • Produces an infinite set of strings.

  • Example:

    • Σ = {a, b} → Σ⁺ = {a, b, aa, ab, ba, bb, aaa, …}

    • Σ = {5, 6} → Σ⁺ = {5, 6, 55, 56, 65, 66, …}

3. Language

  • Definition: A language (L) is a collection of strings formed from an alphabet Σ.

  • Types of Language:

    1. Finite Language: Contains a limited number of strings.

      • Example:

        • Σ = {a, b}

        • L = {aa, ab, ba, bb} → Strings of length 2 → finite set

    2. Infinite Language: Contains an infinite number of strings.

      • Example:

        • Σ = {a, b}

        • L = {a, b, aa, ab, ba, bb, aaa, …} → Infinite set

Notes:

  • A language can be finite or infinite.

  • Σ* (Kleene Star) is the parent of all languages over an alphabet Σ.