ITEC 420 - Section 1.3 - Regular Expressions



Regular Expressions - Lecture Topics


Review: Our Objects so Far


Review: Types


Closure of Regular Languages


How to Specify a Language


Regular Expressions: Components


Regular Expressions: Alphabet Symbols


Language Described by a Regular Expressions



Regular Expressions: ∪



Regular Expressions: Star



Regular Expressions: Concatenation



Regular Expressions: Precedence and Parentheses



Regular Expressions: R+



Regular Expressions: ε and ∅



Symbols, Strings, and Regular Expressions



Σ*


Regular Expressions: Identities



Regular Expressions: Formal Defintion



Regular Expressions: More Examples



Regular Expressions: Example Application



Regular Expressions as a Type



Regular Expressions Describe Regular Languages



Part 1: Languages Described by RE Are Regular



Part 2: Each Regular Language Can be Described by a RE



Part 2: GNFA Transitions



Part 2: Simple Examples Modifying GNFA



GNFA - Compared to NFA



GNFA - Special Form and Computation



How to Convert an NFA to an Equivalent GNFA



GNFA: Formal Definition



GNFA: Removing States



Removing States: Notes on Modifying Delta


  • Example 1: Figure 1.67, pg. 75
  • Example 2: Figure 1.69, pg. 76


  • GNFA: Procedure Convert



    Proof of Claim 1.65



    Conclusion: RE ↔ RL




    ITEC 420 Course Page,
    Last modified on