Introduction to Theory of Computation - GeeksforGeeks

Overview of Theory of Computation (TOC)

• Definition: TOC is a branch of computer science and mathematics that studies abstract machines to understand the capabilities and limitations of computation.
• Fundamental Building Blocks:
  • Symbol: The smallest unit (alphabet, letter, or character).
  • Alphabet (Σ): A finite, non-empty set of symbols.
  • String: A finite sequence of symbols from an alphabet; denoted as w.
  • Empty String (ε): A string with zero occurrences of symbols.
  • String Calculation: For an alphabet of size 2 and length n, the number of possible strings is 2ⁿ.
• Closure Operations:
  • Positive Closure (L+): Set of all strings excluding the empty string (ε).
  • Kleene Closure (L):* Set of all strings including the empty string (ε); represented as L* = ε ∪ L+.
• Language Classification:
  • Regular Languages: Defined by regular expressions or finite automata.
  • Context-Free Languages: Defined by context-free grammars or pushdown automata.
  • Context-Sensitive Languages: Defined by context-sensitive grammars or linear-bounded automata.
  • Recursive/Recursively Enumerable Languages: Defined by Turing machines.
• Core Areas of Study:
  • Automata Theory: Focuses on computational models (Finite Automata, Pushdown Automata, Turing Machines).
  • Formal Languages and Grammars: Examines syntax and structure, categorized by the Chomsky Hierarchy.
  • Computability and Decidability: Determines what problems can be solved by algorithms (e.g., Decidable vs. Undecidable problems like the Halting Problem).
  • Complexity Theory: Analyzes the efficiency of algorithms regarding time and space (P, NP, NP-Complete, and NP-Hard classes).