Theory of Computation - Week 5 Notes

Theory of Computation - Week 5 Notes

Announcements
  • Assignment 1 Deadline: 30/03/2025 (Sunday) by 23:59
  • Midterm Exam: 29/04/2025 (Week 8)
    • Venue: MS202 STHG01 (Regular lecture venue)
    • Time: 14:00 - 15:00
    • Lecture Continues: 15:00 - 16:00
    • Content Covered: References from Lectures 2 to 5 and Tutorials 1 to 4.
Weekly Topics Breakdown
  • Week 1: Background knowledge revision (logic, sets, proof techniques)
  • Week 2: Languages, strings, hierarchies, computation, closure properties
  • Week 3: Finite State Machines - non-determinism vs. determinism
  • Week 4: Regular languages - expressions and grammars
  • Week 5: Non-regular languages - pumping lemma, closure properties
  • Week 6: Context-free languages - grammars, parse trees
  • Week 7: Pushdown automata
  • Week 8: Non context-free languages - pumping lemma and decidability, closure properties
  • Week 9: Decidable languages - Turing Machines
  • Week 10: Church-Turing thesis and the unsolvability of the Halting Problem
  • Week 11: Decidable, semi-decidable, and undecidable languages (and proofs)
  • Week 12: Review of the hierarchy, safety-critical systems
  • Week 13: Extra revision (if needed)
Key Concepts from Last Week (Week 4)

  • Regular Expressions (REs): Define patterns for regular languages.

    • For every RE, there exists an equivalent Finite State Machine (FSM).

  • A language is regular if it can be defined with a regular expression.

  • A regular grammar G is defined as a quadruple (V, Σ, R, S).

    • Where:
    • V = variables
    • Σ = terminal symbols
    • R = production rules
    • S = start symbol

  • For any Deterministic Finite State Machine (DFSM) M, there exists an algorithm fsmtoregex that constructs a regular expression recognizing L(M).

  • For any grammar G, an algorithm grammartofsm can construct an FSM that accepts L(G).

  • The class of languages defined by regular grammars, regular expressions, and FSMs is precisely the regular languages.

Week 5 Lecture Outline
  1. Non-Regular Languages: Exploring the pumping lemma and closure properties.
  2. Number of Regular and Non-Regular Languages.
  3. How to Prove a Language L is Regular or Non-Regular.
  4. Closure Properties of Regular Languages:
    • Union
    • Concatenation
    • Kleene star
    • Complement
    • Intersection
    • Difference
    • Reverse
    • Letter substitution
Key Theorems and Proofs

  • Theorem: There is a countably infinite number of regular languages.

    • Proof:
    1. Upper Bound: We can lexicographically enumerate all syntactically legal DFSMs or regular expressions.
    2. There are countably infinite DFSMs, therefore countably infinite regular languages.
    • Lower Bound: Regular sets like {a}, {aa}, {aaa}, etc. show countable infinity as well.

  • Theorem: Every finite language is regular.

    • Proof: Finite languages defined by regular expressions like s1 ∪ s2 ∪ ... ∪ sn are regular.

  • Showing That L is Regular: Options include:

    1. Show L is finite.
    2. Exhibit an FSM for L.
    3. Exhibit a regular expression for L.
    4. Show that the number of equivalence classes of ≈L is finite.
    5. Exhibit a regular grammar for L.
    6. Exploit closure theorems.
Closure Properties of Regular Languages
  • Union: If L1, L2 are regular, then L1 ∪ L2 is regular.
  • Concatenation: If L1, L2 are regular, then L = L1L2 is regular.
  • Kleene Star: If L1 is regular, then L1* is regular.
  • Complement: If L is regular, then ¬L is regular.
  • Intersection: If L1, L2 are regular, then L1 ∩ L2 is regular.
  • Difference: L1 - L2 = L1 ∩ ¬L2 is regular.
  • Reverse: The reverse of a regular language is regular.
  • Letter Substitution: If a letter substitution function where each letter is mapped to a string, then the resulting language from the substitution is regular if the original is.
The Pumping Lemma
  • If a language L is regular, then there exists a pumping length k such that any string w in L with length ≥ k can be divided into xyz where:
    1. |xy| ≤ k
    2. |y| > 0
    3. xy^iz ∈ L for all i ≥ 0 (pumping property).
  • To use the pumping lemma in proof, one must demonstrate a long string that cannot satisfy the pumping conditions, indicating that L is not regular.
Example of Non-Regular Language
  • Language L = {a^nb^n: n ≥ 0} must satisfy the conditions of the Pumping Theorem.
  • Choosing w = a^k b^k shows that for any possible division of w into xyz, one of the pumped results will not belong to L.
Final Notes
  • The Pumping Theorem is crucial in proving that certain languages are not regular through contradiction.
  • Effective strategies for using the theorem include narrowing the choice of w appropriately and considering all cases for y substitution.