Notes on Theory of Computation

Theory of Computation

  • Theoretical computer science branch: study of algorithms, computational complexity.
  • Fundamental questions aimed to answer:
    • What can be computed?
    • How efficiently can it be done?
    • What limitations exist?

Basic Concepts and Automata Theory

  • Automata: Mathematical model for computation, system of rules.
  • Alphabet (Σ): Finite non-empty set of symbols, e.g., Σ = {0,1}.
  • String: Finite sequence of symbols from the alphabet, e.g., "aabb".
  • Language: Set of strings formed from an alphabet.
Finite Automata
  • Deterministic Finite Automaton (DFA): Defined by 5-tuples
    • (Q, S, d, S0, F)
    • Q: finite set of states.
    • S: finite input alphabet.
    • d: transition function.
    • S0: initial state.
    • F: final (accepting) states.
  • Nondeterministic Finite Automaton (NFA): Allows multiple next states.
  • Equivalence between DFA and NFA: Both recognize regular languages.
    • Subset Construction for conversion from NFA to DFA.
Formal Language
  • Study of formal languages, grammars, and their properties.
  • Regular Languages: Described by regular expressions.
  • Closure Properties: Regular languages closed under union, concatenation, and Kleene star.
Context-Free Grammars (CFG)
  • Definition: A set of rules describing exactly how strings can be formed.
  • Ambiguity & Derivation: Different rules leading to the same string are ambiguous.
  • Chomsky Normal Form (CNF): A grammar where every rule is transformed.
  • Greibach Normal Form (GNF): Every rule has a terminal followed by non-terminals.
Pushdown Automata (PDA)
  • Mechanisms to handle context-free languages using stacks.
  • Acceptance: By empty stack or final state.
  • Deterministic vs Nondeterministic PDA: DPDA can do less than NPDA.
  • Context-Free Pumping Lemma: For proving non-regularity of languages.
Turing Machines
  • Basic Model of computation, simulates any algorithm.
  • Defined by 7-tuple: (Q, Σ, Γ, δ, q0, b, F).
    • Q: states.
    • Σ: input symbols.
    • Γ: tape symbols.
    • b: blank symbol.
    • δ: transition function.
    • q0: initial state.
    • F: set of final states.
  • Key concepts: Simulates any algorithm, recognizes recursively enumerable languages.
Recursive and Recursively Enumerable Languages
  • Recursive: Halts on all inputs, decision properties decidable.
  • Recursively Enumerable: Halts on some inputs, undecidable membership.
Post's Correspondence Problem (PCP) & Halting Problem
  • PCP: Undecidable problem establishing language equivalence.
  • Halting Problem: Shows limits of what can be computed.