COMP2270 Theory of Computation Notes - Week 5

Theory of Computation

Week 5 Overview

  • Non Regular Languages

    • Introduction to pumping lemma.

    • Closure properties of languages.

Important Dates

  • Assignment 1 Due: 30/03/2025 (Sunday)

  • Midterm Exam: Week 8 on 29/04/2025 from 14:00 to 15:00 in MS202 STHG01.

    • Content covered in Lectures 2 to 5 and Tutorials 1 to 4.

Weekly Program Overview

  1. Week 1: Logic, sets, proof techniques

  2. Week 2: Languages, strings, hierarchies, computation, closure properties

  3. Week 3: Finite state machines - non-determinism vs. determinism

  4. Week 4: Regular languages - expressions and grammars

  5. Week 5: Non-regular languages - pumping lemma, closure properties

  6. Week 6: Context-free languages - grammars and parse trees

  7. Week 7: Pushdown automata

  8. Week 8: Non-context-free languages - pumping lemma and decidability, closure properties

  9. Week 9: Decidable languages - Turing machines

  10. Week 10: Church-Turing thesis and the unsolvability of the Halting Problem

  11. Week 11: Decidable, semi-decidable and undecidable languages (and proofs)

  12. Week 12: Revision of the hierarchy, safety-critical systems

  13. Week 13: Extra revision if needed.

Key Concepts from Previous Week

  • Regular Expressions (REs):

    • Useful for defining language patterns.

    • For every RE, an equivalent finite state machine (FSM) exists.

    • A language is regular if, and only if, it can be defined by a regular expression.

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

    • V: Variables (non-terminals and terminals)

    • Σ: Input symbols
      o R: Production rules
      o S: Start symbol

  • There are algorithms to convert a DFSM to a regular expression and vice versa (FSM).

Week 05 Lecture Outline

  • Number of regular and non-regular languages.

  • Proving a language L is regular.

  • Closure properties of regular languages.

  • Proving a language is non-regular using the pumping lemma.

The Pumping Lemma

  • Definition: A property that states if a language is regular, then there exists an integer p such that any string of length at least p can be divided into three parts x, y, z, satisfying:

    • Condition 1: |xy| ≤ p

    • Condition 2: |y| > 0

    • Condition 3: For all n ≥ 0, the string xy^nz is in the language.

  • Example: Proving that language L = {anbn: n ≥ 0} is not regular by selecting suitable strings and demonstrating the failure of the pumping lemma conditions.

Countability of Languages

  • Countably Infinite Languages:

    • Regular languages can be countably infinite. For example: L = {a}, {aa}, …, {a(n), n ≥ 0}.

  • Uncountably Infinite Languages: There exists an uncountable number of languages over any non-empty alphabet Σ.

  • Example: The set of languages defined on Σ is P(Σ), and since Σ is countably infinite, P(Σ*) is uncountably infinite.

Closure Properties of Regular Languages

  • Closure under operations:

    • Union: L1 ∪ L2 is regular if L1 and L2 are regular.

    • Intersection: L1 ∩ L2 is regular if L1 and L2 are regular.

    • Complementation: If L is regular, then ¬L (complement of L) is also regular.

    • Kleene Star: If L is regular, then L* is also regular.

    • Difference: L1 - L2 = L1 ∩ ¬L2 is regular if L1 and L2 are regular.

    • Reverse and Letter Substitution are also properties that can be proven for regular languages.

Examples

  • Showing Regular Languages:

    • L = {a, b, c} is regular as it can be represented by regular expressions and FSM.

    • Example languages: L1 = {a^n b^n | n ≥ 0} is not regular.

  • Showing Non-Regular Languages using the Pumping Lemma:

    • For any assumed regular string w = a^k b^k, if we apply the pumping lemma, it leads to contradictions regarding membership in the language.

Practical Implications

  • Understanding regular and non-regular languages is critical in computer science, especially in compiler design, parsing, and regular expression implementations in programming languages.

Conclusion

  • The theory of computation covers foundational topics that are essential for computer science.

  • Students should understand how to apply theorems like the pumping lemma to various problems to determine the regularity or non-regularity of languages.

WEEK 4

In Week 4, the focus was on Regular Languages, exploring their definitions, properties, and how they are implemented in computation. Key Topics Covered:

  1. Definition of Regular Languages:

    • Regular languages are those that can be expressed using regular expressions. They are closed under various operations.

    • For every regular expression (RE), an equivalent finite state machine (FSM) exists.

  2. Kleene's Theorem is a fundamental result in the theory of computation, establishing a relationship between regular languages, regular expressions (REs), and finite state machines (FSMs). The theorem states that:

    • Equivalence of Regular Expressions and Finite State Machines: For every regular expression, there exists an equivalent finite state machine that recognizes the same language. Conversely, for every finite state machine, there exists a corresponding regular expression that describes the language it recognizes.

    • Closure Properties: Regular languages are closed under several operations, meaning if you perform these operations on regular languages, the result is also a regular language. These operations include:

      • Union: If both L1 and L2 are regular, then their union L1 ∪ L2 is also regular.

      • Intersection: If both L1 and L2 are regular, then their intersection L1 ∩ L2 is regular.

      • Complementation: If L is regular, then its complement ¬L is also regular.

      • Kleene Star: If L is regular, then L*, the Kleene star of L, is also regular. This operation represents the language formed by concatenating zero or more strings from L.

    • Implications: The theorem highlights the power and flexibility of regular expressions and FSMs in defining and manipulating regular languages, which are crucial in many areas of computer science, including compiler design and programming language development. The ability to switch between regular expressions and FSMs provides a robust framework for analyzing and implementing computational processes.

  3. Expression and Grammar for Regular Languages:

    • Regular languages can be defined by regular grammars, which are structured as quadruples (V, Σ, R, S).

      • V: Variables (non-terminals and terminals)

      • Σ: Input symbols

      • R: Production rules

      • S: Start symbol

  4. Finite State Machines (FSM):

    • A finite state machine is a computational model that recognizes regular languages by transitioning between states based on input symbols. There are two types of FSMs: deterministic and non-deterministic.

  5. Closure Properties of Regular Languages:

    • Regular languages are closed under certain operations, including:

      • Union: If L1 and L2 are regular, then L1 ∪ L2 is also regular.

      • Intersection: If L1 and L2 are regular, then L1 ∩ L2 is also regular.

      • Complementation: If L is regular, ¬L (the complement of L) is also regular.

      • Kleene Star: If L is regular, then L* is also regular.

      • Difference: L1 - L2 = L1 ∩ ¬L2 is regular if L1 and L2 are regular.

  6. Practical Implications of Regular Languages:

    • Understanding regular languages is crucial in computer science fields such as compiler design and programming language development, where regular expressions are widely utilised for pattern matching and parsing.
      Conclusion:
      Regular languages form a foundational aspect of formal language theory and understanding their properties, expressions, and implementations is vital for advancements in computational theory and practice.

WEEK 3

Finite state machines (FSMs) are a foundational concept in the theory of computation, essential for understanding how certain languages and computations can be represented and processed. In this week, we explored the following key aspects of FSMs:

  1. Definition and Components

    • States: A finite set of conditions or configurations the machine can be in.

    • Input Alphabet: A finite set of symbols that the machine reads as input.

    • Transition Function: A mapping that determines how the machine transitions from one state to another based on the input symbol read. It defines the next state for each combination of current state and input symbol.

    • Start State: The state in which the machine begins its operation.

    • Accept States: A set of states where the machine will accept the input string if it ends in one of these states.

  2. Deterministic vs. Non-deterministic FSMs (DFSMs vs. NFSMs)

    • Deterministic Finite State Machine (DFSM): In a DFSM, for every current state and input symbol, there is exactly one transition to the next state. This means that the machine's behavior is predictable.

    • Non-deterministic Finite State Machine (NFSM): In an NFSM, for a given current state and input symbol, there can be multiple possible next states or even none at all. An NFSM can also have ε-transitions (transitions without consuming any input symbol).

    • While DFSMs and NFSMs might seem different, they are equivalent in terms of their computational power; any NFSM can be converted into an equivalent DFSM that recognizes the same language.

  3. Language Recognition

    • A finite state machine recognizes a language if it can process input strings and determine whether they belong to that language based on transitions leading to accept states. The important aspect is that the language recognized by a finite state machine is a regular language, represented by regular expressions.

  4. Examples of FSMs

    • Example of DFSM: A machine that accepts the language of all strings over {0, 1} that contain an even number of 0s.

    • Example of NFSM: A machine that accepts strings containing ‘ab’ can be constructed non-deterministically, where the machine branches into different paths upon reading characters.

  5. Applications

    • Finite state machines are widely used in various fields, including

      • Compiler Design: For lexical analysis, where tokens in source code are identified.

      • Network Protocols: For managing state transitions in communication protocols.

      • Control Systems: For modeling and controlling systems based on discrete states.

In conclusion, understanding both deterministic and non-deterministic finite state machines, their definitions, construction, and applications is vital for further studies in automata theory and computational models. Mastery of this topic sets the stage for understanding regular languages and their associated properties.