Languages & Machines
25420/01 Fall 1999
01: Aug. 30, 1999

Class 01, Aug. 30:

• Course requirements
• Mathematical preliminaries, pages 3 - 8.
  • Sets
  • Functions
  • Relations
  • Graphs and trees
• Languages, pages 14 - 18.
  • alphabet
  • string
  • concatenation
  • reverse
  • length
  • empty string
  • prefix and suffix
  • language
  • sentence
  • star-closure
  • positive-closure
• Grammars, pages 19 - 25.
  • variables
  • terminal symbol
  • start symbol
  • production
  • derivation
  • sentential form
  • equivalent grammars
• Problems, pages 27 - 28. Bring your solutions to the next class.
  • 8 (a), (b), (c)
  • 9
  • 14(a)
• For next time, read sections 2.1 and 2.2