Course: TThu 14:00-15:20, SBS N250 (or compling lab)
Instructor: Jeffrey Heinz, jeffrey.heinz@stonybrook.edu
Office Hours: Tuesday 11:30-1pm, Wednesday 2pm-3:30pm and by appointment
Materials
Course Log
13 Feb
- We reviewed some more of plebby’s features pleb.txt.
- We explained how to determinize NFA (powerset construction). For a proof, see pages 54-56 in Chapter 1 of Sipser’s 2012 text. See Kozen1997 Chapter 6 for a more technically complete proof.
- On Tuesday we will discuss how to minimize DFA (identifying distinguishable states) and we will relate this minimal DFA to the Nerode equivalence relation.
11 Feb
- We sketched how to obtain a RE from a NFA. See pages 66-76 in Chapter 1 of Sipser’s 2012 text.
- We showed why NFA are closed under complement, intersection, and difference.
- Using those facts, and the notion of reachable states, we showed we can decide whether one regular language is a subset of another. And then we can decide whether two regular languages are equal.
- We played with plebby. pleb.txt
- For Thursday, see if you can get the visualization (graphviz) installed. Also see if you can write PLEs for #12 and #13 in Example 1 in the course notes.
06 Feb
- We looked at this supplement, which defines NFA and DFA and how they process strings from a non-recursive perspective. (This will change.)
- We discussed how to visualize NFA and DFA as graphs.
- We sketched how any RE can be expressed as a NFA because the base cases correspond to NFA and the inductive cases correspond to particular constructions.
- We demonstrated plebby and its PLEs.
- For Tuesday, please install plebby, and examine its tutorial, especially the section titled “Building a Linguistic Pattern”.
04 Feb
- We defined and discussed CUEs, GREs, and SFEs and stated the facts (without proof) that
- [[GREs]] = [[REs]] ⊃ [[SFEs]] ⊃ [[CUEs]] = FIN
- even-a is a formal language expressible with REs but not SFEs
- Regular languages and SFEs have other characterizations in terms of logic and algebra
- This material is the subject of McNaughton and Papert 1971
- We also defined Dakotah’s Lambert’s Piecewise Local Expressions, which we will study further on Thursday.
- Theorem 6 in this paper establishes that Tier-based Strictly Local languages are a subset of the Star-Free Languages. That they are a proper subset follows from Theorems 4 and 5.
30 Jan 2025
- We discussed concatenation, how to define formal grammars, and REs in Chapter 2.
- For Tuesday, write a RE for the set containing all strings which do not contain the sequence aa (assume the alphabet is {a, b, c}).
28 Jan 2025