Chapter 0 Week 1¶
- 0.1. Formal Languages Course Introduction
- 0.1.1. Introduction
- 0.1.2. Administration stuff
- 0.1.3. Course Mechanics: Canvas
- 0.1.4. Course Mechanics: OpenDSA
- 0.1.5. What you should already know
- 0.1.6. Process
- 0.1.7. What this course is about
- 0.1.8. Outcomes (1)
- 0.1.9. Outcomes (2)
- 0.1.10. Outcomes (3)
- 0.1.11. Outcomes (4)
- 0.1.12. Language Hierarchy
- 0.1.13. Models of Computation, Languages, Machines
- 0.1.14. Power of Machines
- 0.1.15. Application: Compilers
- 0.1.16. To do by next class
- 0.2. Key Concepts
- 0.3. Deterministic Finite Acceptors
- 0.3.1. Deterministic Finite Acceptors
- 0.3.1.1. Introduction: Terminology
- 0.3.1.2. Deterministic Finite Acceptor
- 0.3.1.3. DFA: Formal Definition
- 0.3.1.4. Concept: Accepting a String
- 0.3.1.5. Formal Definition
- 0.3.1.6. Example
- 0.3.1.7. .
- 0.3.1.8. Concept: Power of DFAs
- 0.3.1.9. Algorithm for DFA
- 0.3.1.10. Trace
- 0.3.1.11. Definitions
- 0.3.1.12. Incomplete DFA
- 0.3.1.13. Trap State
- 0.3.1.14. Regular Languages
- 0.3.1. Deterministic Finite Acceptors
Chapter 1 Week 2¶
- 1.1. Non-Deterministic Finite Acceptor
- 1.1.1. Non-Deterministic Finite Acceptor (1)
- 1.1.2. Non-Deterministic Finite Acceptor (2)
- 1.1.3. NFA Example 1
- 1.1.4. NFA Example 2
- 1.1.5. Accepting a String
- 1.1.6. Why nondeterminism?
- 1.1.7. Which is more powerful?
- 1.1.8. Key Question
- 1.1.9. Key Theorem
- 1.1.10. Class(DFA) == Class(NFA) Proof
- 1.1.11. Algorithm to construct \(M_D\) (1)
- 1.1.12. Algorithm to construct \(M_D\) (2)
- 1.1.13. Example: NFA to DFA
- 1.1.14. So, why NFA?
- 1.2. Minimizing the Number of States in a DFA
- 1.3. Traditional Branches of Theory in CS
Chapter 2 Week 3¶
- 2.1. Regular Languages and Expressions
- 2.1.1. Regular Expressions
- 2.1.2. Examples
- 2.1.3. Definition for Regular Expression
- 2.1.4. Definition for Regular Language
- 2.1.5. Precedence Rules
- 2.1.6. Examples of Regular Languages
- 2.1.7. Regular Expressions vs. Regular Languages
- 2.1.8. Regular Expression \(\rightarrow\) NFA (1)
- 2.1.9. Regular Expression \(\rightarrow\) NFA (1a)
- 2.1.10. Regular Expression \(\rightarrow\) NFA (1b)
- 2.1.11. Regular Expression \(\rightarrow\) NFA (2)
- 2.1.12. Regular Expression \(\rightarrow\) NFA: Schematic
- 2.1.13. Regular Expression \(\rightarrow\) NFA: Or
- 2.1.14. .
- 2.1.15. Regular Expression \(\rightarrow\) NFA: Concatenation
- 2.1.16. Regular Expression \(\rightarrow\) NFA: Star
- 2.1.17. NFA \(\rightarrow\) Regular Expression
- 2.1.18. Generalized Transition Graph (GTG)
- 2.1.19. Proof (1)
- 2.1.20. Proof (2)
- 2.1.21. Proof (3)
- 2.1.22. Proof (4)
- 2.1.23. Proof (5)
- 2.1.24. Example
- 2.1.25. Conclusion
- 2.2. Regular Grammars
- 2.2.1. Regular Grammars
- 2.2.2. Right-linear grammar
- 2.2.3. Left-linear grammar
- 2.2.4. Example 1
- 2.2.5. Example 1
- 2.2.6. Example 2
- 2.2.7. Example 2
- 2.2.8. Our Next Step
- 2.2.9. Proof: NFA from Regular Grammar
- 2.2.10. RRG to NFA Example
- 2.2.11. Proof: RR Grammar from DFA
- 2.2.12. NFA to RRG Example
- 2.2.13. Something to Think About
- 2.3. Closure Properties of Regular Languages
- 2.3.1. Closure Properties
- 2.3.2. Closure of Regular Languages (1)
- 2.3.3. Proof: Complementation
- 2.3.4. Proof: Intersection
- 2.3.5. More Closure Properties (1)
- 2.3.6. Right Quotient (1)
- 2.3.7. Right Quotient (2)
- 2.3.8. Homomorphism
- 2.3.9. Questions about Reg Languages (1)
- 2.3.10. Questions about Reg Languages (2)
Chapter 3 Week 4¶
- 3.1. Identifying Non-regular Languages
- 3.1.1. Review
- 3.1.2. How do we know if a language is non-regular?
- 3.1.3. Cycles
- 3.1.4. Something to Think About, Revisited
- 3.1.5. Our First Non-regular Language (1)
- 3.1.6. Our First Non-regular Language (2)
- 3.1.7. Pigeonhole Principle
- 3.1.8. Pumping Concept (1)
- 3.1.9. Pumping Concept (2)
- 3.1.10. Pumping Lemma
- 3.1.11. P.L. Proof Template
- 3.1.12. Example Proof
- 3.1.13. Harder version (1)
- 3.1.14. Harder version (2)
- 3.1.15. Observations
- 3.1.16. More Observations
- 3.1.17. Can View as Adversary Argument
- 3.1.18. Example
- 3.1.19. Example: Failure (as expected)
- 3.1.20. Example: Failure (as expected)
- 3.1.21. Adversary Argument Explained (1)
- 3.1.22. Adversary Argument Explained (2)
- 3.1.23. Example
- 3.1.24. Another Example
- 3.2. Using Closure Properties to Prove a Language Non-Regular
Chapter 4 Week 5¶
- 4.1. Context-Free Languages
- 4.1.1. Programming Languages
- 4.1.2. Context Free Languages
- 4.1.3. Example
- 4.1.4. Linear Grammars
- 4.1.5. Example
- 4.1.6. Example (cont)
- 4.1.7. Derivations
- 4.1.8. Example
- 4.1.9. Example
- 4.1.10. Derivation Example
- 4.1.11. More on derivations
- 4.1.12. Examples
- 4.1.13. Membership problem (1)
- 4.1.14. Example
- 4.1.15. Example of Derivation (1)
- 4.1.16. Example of Derivation (2)
- 4.1.17. Derivation: Strings Not in Language
- 4.1.18. CFG Theorem (1)
- 4.1.19. CFG Theorem (2)
- 4.1.20. Example (1)
- 4.1.21. Example (2)
- 4.1.22. Example (3)
- 4.1.23. Example (4)
- 4.1.24. Not all grammars considered equal
- 4.1.25. Ambiguity
- 4.1.26. Ambiguity Example (1)
- 4.1.27. Ambiguity Example (2)
- 4.1.28. Ambiguity Example (3)
- 4.1.29. Ambiguity Example (3)
- 4.1.30. Rewriting the Grammar (1)
- 4.1.31. Rewriting the Grammar (2)
- 4.1.32. .
- 4.1.33. Rewriting the Grammar (3)
- 4.1.34. Unambiguous Grammars
- 4.1.35. Backus-Naur Form of a grammar:
- 4.1.36. Programming Language (1)
- 4.1.37. Programming Language (2)
- 4.1.38. Limits to CFG
Chapter 5 Week 7¶
- 5.1. Simplifying CFGs and Normal Forms
- 5.1.1. Transforming CFGs (1)
- 5.1.2. Transforming CFGs (2)
- 5.1.3. Substitution Theorem (1)
- 5.1.4. Substitution Theorem (2)
- 5.1.5. Substitution Theorem Example
- 5.1.6. Substitution Theorem Example
- 5.1.7. Useless Productions (1)
- 5.1.8. Theorem: (useless productions)
- 5.1.9. Process (1)
- 5.1.10. Example (1)
- 5.1.11. Process (2)
- 5.1.12. Example (2)
- 5.1.13. Example (3)
- 5.1.14. Removing \(\lambda\) Productions
- 5.1.15. Process: Removing \(\lambda\) Productions
- 5.1.16. Example: Step 2
- 5.1.17. Example: Step 3
- 5.1.18. Unit Productions
- 5.1.19. Unit Productions (2)
- 5.1.20. Removing Unit Productions
- 5.1.21. Process
- 5.1.22. Example (1)
- 5.1.23. Example (2)
- 5.1.24. Theorem
- 5.1.25. Chomsky Normal Form (CNF)
- 5.1.26. Theorem:
- 5.1.27. Example (1)
- 5.1.28. Example (2)
- 5.1.29. Greibach Normal Form (GNF)
- 5.1.30. GNF Theorem
- 5.1.31. What You Should Know
Chapter 6 Week 9.1¶
- 6.1. Pushdown Automata
- 6.1.1. Our Current Model of the FL Universe
- 6.1.2. DFA Review
- 6.1.3. Pushdown Automata
- 6.1.4. Non-deterministic PDA (1)
- 6.1.5. Non-deterministic PDA (2)
- 6.1.6. Example of Transitions (1)
- 6.1.7. Example of Transitions (2)
- 6.1.8. Instantaneous Descriptions
- 6.1.9. Definition for Language Acceptance
- 6.1.10. Example
- 6.1.11. .
- 6.1.12. Language Acceptance in PDA
- 6.1.13. Example
- 6.1.14. Example
- 6.1.15. Two Acceptance Definitions
- 6.2. Equivalence of NPDA and CFG
- 6.2.1. Equivalence of NPDA and CFG
- 6.2.2. Any CFG has a NPDA
- 6.2.3. Proof Idea
- 6.2.4. Proof Example (1)
- 6.2.5. Proof Example (2)
- 6.2.6. Proof Example (3)
- 6.2.7. Another Example
- 6.2.8. Any NPDA has a CFG (1)
- 6.2.9. Simplifying Assumptions (1)
- 6.2.10. Simplifying Assumptions (2)
- 6.2.11. Any NPDA has a CFG (2)
- 6.3. Deterministic Pushdown Automata
- 6.4. Grammars for Deterministic Context-free Languages
Chapter 7 Week 9.2¶
- 7.1. Pumping Lemma for CFL
- 7.1.1. Which of these is a CFL?
- 7.1.2. Pumping Lemma: Regular Languages
- 7.1.3. Pumping Lemma for CFLs: Intuition
- 7.1.4. Pumping Lemma for CFLs
- 7.1.5. Proof Sketch (1)
- 7.1.6. Proof Sketch (2)
- 7.1.7. Proof Example Problem
- 7.1.8. Proof (1)
- 7.1.9. Proof (2)
- 7.1.10. Proof (3)
- 7.1.11. Adversary Version (1)
- 7.1.12. Adversary Version (2)
- 7.1.13. (Try to) Prove a CFL not a CFL
- 7.1.14. Example
- 7.1.15. Example
- 7.2. Closure Properties for CFLs
Chapter 8 Week 10¶
- 8.1. Turing Machines
- 8.1.1. A General Model of Computation
- 8.1.2. Turing Machines (1)
- 8.1.3. Turing Machines (2)
- 8.1.4. Formal definition of Turing Machine
- 8.1.5. Formal definition of Turing Machine
- 8.1.6. Formal definition of Turing Machine
- 8.1.7. Turing Machine Example 1
- 8.1.8. Turing Machine Example 1
- 8.1.9. Turing Machine Example 2
- 8.1.10. Notation
- 8.1.11. Notation
- 8.1.12. Notation
- 8.1.13. Hanging
- 8.1.14. Acceptors and Transducers
- 8.1.15. Transducers
- 8.1.16. Multiple Parameters
- 8.1.17. Numbers
- 8.2. Decideability vs. Acceptability
- 8.3. Combining Turing Machines
- 8.4. Turing Machine Extensions
Chapter 9 Extra¶
- 9.1. Parsing
- 9.1.1. Parsing Introduction
- 9.1.2. Introduction Example (2)
- 9.1.3. Introduction Example (3)
- 9.1.4. Top-down Parser
- 9.1.5. Bottom-up Parser
- 9.1.6. Making Parse Tables
- 9.1.7. The function FIRST
- 9.1.8. To compute FIRST (1)
- 9.1.9. To compute FIRST (2)
- 9.1.10. To compute FIRST (3)
- 9.1.11. Example (1)
- 9.1.12. Example (2a)
- 9.1.13. Example (2b)
- 9.1.14. The function FOLLOW
- 9.1.15. Computing FOLLOW
- 9.1.16. Example (1)
- 9.1.17. Example (2a)
- 9.1.18. Example (2b)
- 9.1.19. LL(k) Parsing
- 9.1.20. LL parsing process
- 9.1.21. Parsing routine (for this grammar)
- 9.1.22. LL Parse Table
- 9.1.23. Parse Table Example
- 9.1.24. A generic parsing routine
- 9.1.25. Example
- 9.1.26. Example
- 9.1.27. Constructing an LL parse table
- 9.1.28. Example (1): Need FIRST and FOLLOW
- 9.1.29. Example (2): Compute Parse Table
- 9.1.30. Example (3): Sample Trace
- 9.1.31. Example (4): Sample Trace
- 9.1.32. LL(k) Can’t Parse All CFGs
- 9.1.33. Conclusion
- 9.2. Properties Stuff
