jeffgerickson / algorithms

Bug-tracking for Jeff's algorithms book, notes, etc.
7.92k stars 1.02k forks source link

[Oops.] Type error for production rule for CFG #177

Closed plin25 closed 5 years ago

plin25 commented 5 years ago

Chapter number or note title: Models of Computation Lecture 5: Context-Free Languages and Grammars

Page number: 1

Error description: The third bullet explaining CFG states

which does not include the possibility of w = ε, as seen a few lines later in the example production rule C → ε

Suggested fix (if any): Replace w ∈ (Σ ∪ Γ) with w ∈ (Σ ∪ Γ) ∪ {ε}

echuber2 commented 5 years ago

Couldn't (Σ ∪ Γ)* already imply ε because of the Kleene star?

plin25 commented 5 years ago

I'm an idiot