Formal Definition of a Regular Expression
Languages Associated with Regular Expressions
3.2 Connection Between Regular Expressions and Regular Languages
Regular Expressions Denote Regular Languages
Regular Expressions for Regular Languages
Regular Expressions for Describing Simple Patterns
3.3 Regular Grammars
Right-and Left-Linear Grammars
Right-Linear Grammars Generate Regular Languages
Right-Linear Grammars for Regular Languages
Equivalence of Regular Languages and Regular Grammars
4 Properties of Regular Languages
4.1 Closure Properties of Regular Languages
Closure under Simple Set Operations
Closure under Other Operations
4.2 Elementary Questions about Regular Languages
4.3 Identifying Nonregular Languages
Using the Pigeonhole Principle
A Pumping Lemma
5 Context-Free Languages
5.1 Context-Free Grammars
Examples of Context-Free Languages
Leftmost and Rightmost Derivations
Derivation Trees
Relation Between Sentential Forms and Derivation Trees
5.2 Parsing and Ambiguity
Parsing and Membership
Ambiguity in Grammars and Languages
5.3 Context-Free Grammars and Programming Languages