CMSC 208: Grammars, Languages, Automata
(Spring 2019)

TuTh 9:30-10:45am Ruffner 354

Course Information Handout/Syllabus

Academic Honesty in Programming
Linz text
Scott McElfresh
x2249       Ruffner 346
ProfScottMcElfresh @

Office Hours:
(no appointment needed,
just drop by during these times)

yellow divider
Mon, Jan 14

Tue, Jan 15

  • Introduction
  • Review of Sets and Logic
Assigned for Thursday Jan 17:
Watch the following videos for review:
Finish the review sheet handed out in class:
Wed, Jan 16

Thu, Jan 17
Daily assignment due:  
  • Watch the videos assigned Tuesday
  • Finish the review sheet handed out in class on Tuesday.

  • Sets and Logic review
  • Summation notation
  • Mod arithmetic

Daily assignment for Tue, Jan 22:
Graded Homework due Tue, Jan 22:
Fri, Jan 18

yellow divider
Mon, Jan 21

Tue, Jan 22
Daily assignment due:  the reading and videos assigned
Graded Homework due:  Review HW

  • Sums Programming  (due Tue, Jan 29)
  • Daily assignment for Th, Jan 24  
    • Mathematical induction example in section 1.1 of the book
    • watch these videos about mathematial induction examples
Wed, Jan 23

Thu, Jan 24
Daily assignment due:  videos and reading from Tuesday

  • mathematical induction

Daily Assignment for Tue, Jan 29:
Do as much as you can on the 15 induction problems on the worksheet given in class.    Be prepared to discuss and present what you have.
Fri, Jan 25

yellow divider
Mon, Jan 28

Tue, Jan 29
Daily Assignment due:   induction problems frmo Th
Also due at beginning of class:  Sums Programming

  • induction examples

Computer Science internship presentations
3:30pm Ruffner 350
Wed, Jan 30

Thu, Jan 31

  • induction wrapup and structural induction
Fri, Feb 1

yellow divider
Mon, Feb 4

Tue, Feb 5

  • intro to DFAs
Wed, Feb 6

Thu, Feb 7

  • DFAs
Assigned for Tue, Feb 12:

1) Get the JFLAP software. It is on the CD that comes with the textbook, but you can also download it for free from this site. I am using the version May 15, 2011 - JFLAP Version 7. Explore what you are able to do after you click on the Finite Automaton button.   Try to create one of the pictures from the reading in Section 2.1.

2) Read Section 2.1 of the textbook.

3) Come to class with your solutions to the following problems on pages 48 and 49:  (on paper or in JFLAP, your choice)

  • 3 (all parts)
  • 4 (a, b, and c)
  • 5 (a, b, and c)
  • 6
  • 7 (a, b, and c)    Note that the notation na (w)   means the number of a's in the string w.
  • 8 (a and b)
  • 11 a
Fri, Feb 8

yellow divider
Mon, Feb 11

Tue, Feb 12
DUE:  Take home quiz handed out on Th, Feb 5
DUE: homeworks assigned on Th, Feb 5

  • DFAs, continued
Assigned for Thu, Feb 14:

Download Racket to your laptop. Bringyour laptop to class Thursday if convenient.

Assigned for Tue, Feb 19:

DFA worksheet


Wed, Feb 13
Thu, Feb 14
  • Limits of DFAs
  • Prefix notation
  • Racket


Code from class:

Fri, Feb 15

yellow divider
Mon, Feb 18

Tue, Feb 19

  • more with functional programming in Racket

Assigned: for Th, Feb 21:
Exploratory worksheet
Wed, Feb 20

Thu, Feb 21

  • Racket wrap-up
  • intro to non-determinism
  • For Tue, Feb 26:
    • Read section 2.2 of the book on non-determinism
    • Come to class with your attempts to exercises 5-13 on page 57.
  • For Th, Feb 28:  (beginning of class)
    • Consider problem 11d on page 49.
    • Create a JFlap file that has an automaton that  accepts that language.
    • Create a text file with at least 20 reasonable test cases for your automaton (including strings that should be accepted and some that should not be accepted).
    • Submit the JFlap file and the text file to the appropriate places in Canvas.
  • For Fri, March 1:
Fri, Feb 22

yellow divider
Mon, Feb 25

Tue, Feb 26
Due:  non-determinism reading and exercises
Wed, Feb 27

Thu, Feb 28
Due:  problem 11d on page 49. (beginning of class)

Inclass Exam
Fri, March 1
Due 5pm:  Racket HW

yellow divider
Mon, March 4 - Friday, March 8

Spring Break   No Classes

yellow divider
Mon, March 11

Tue, March 12

Topics: Assigned:
For Th, March 14:  
  • Read Sections 3.1 and 3.2 of the text.
  • Come to class with your attempts at the following problems from the book:
    • pgs 78-79: 1, 3,4, 7, 8, 9, 11, 13,14, 16-21
    • page 90:  problem 6
Wed, March 13

Thu, March 14
Due: Daily assignment from Tue.

Work on regular expressions
Fri, March 15

yellow divider
Mon, March 18

Tue, March 19

  • more complicated regular expressions
  • English ambiguities
Assigned for Thurs:
  • Read about Grammars:  section 3.3 of the text
  • Be prepared to discuss exercises 1-10 on page 99
Wed, March 20

Thu, March 21
Daily assingment from Tue

  • grammars
  • Problems 1-14 on pages 99 and 100
Fri, March 22

yellow divider
Mon, March 25

Tue, March 26
DUE: daily assignment from Th

  • grammars
Wed, March 27

Thu, March 28

  • grammars:
Assigned:  due Tue April 2
Problem 14c on page 100.   An automaton AND a grammar.  (handin details in Canvas)
Fri, March 29

yellow divider
Mon, April 1

Tue, April 2
DUE:  14c on page 100 (slightly modified)

  • pumping lemma
  • context free grammars and pushdown automata

Read Section 7.1 of the book


  • the notation is slightly different than in JFlap and what I did in class, but hopefully understandable.
  • The reading contains examples where something is popped from the stack to look at it, but then must be put back on the stack.

Come to class with:

  • attempts at problems 1, 6a, 6b, 6d, and 6e on page 189, ready for discussion and presentation.


Wed, April 3

Thu, April 4
Due: daily assignment from Tuesday

  • pushdown automata
  • Take home quiz (due Tu, April 9)
Fri, April 5

yellow divider
Mon, April 8

Tue, April 9
DUE: take home quiz

  • working with PDAs
problems 4, 6, 7, and 8 on the inclass handout
come to class prepared to discuss and present
Wed, April 10

Thu, April 11
DUE:  problems assigned on Tuesday

  • PDA work
  • intro to Turing machines
Fri, April 12

yellow divider
Mon, April 15

Tue, April 16

  • turing machines, functions
Come to class on Thursday with attempts at these problems on pg  248:
  • 8 :  e-h
  • 10
  • 13 a and b
Try to do at least one of these in Jflap
Wed, April 17

Thu, April 18
Due:  daili assignment from Tuesday.
  • turing machines examples

Turing Machines in JFLap
Fri, April 19

yellow divider
Mon, April 22

Tue, April 23

Campus-wide Research Day
No classes
Wed, April 24

Thu, April 25
DUE: Turing Machines in JFlap
Fri, April 26

yellow divider
Mon, April 29

Tue, April 30

Wed, May 1

Thu, May 2

Fri, May 3

yellow divider
Mon, May 6

Tue, May 7

Final Exam
Details TBA
Wed, May 8
Thu, May 9

Fri, May 10

yellow divider