✞ JMJ ✞

ad majorem Dei gloriam

CPS 482/582: Automata Theory

Department of Computer Science, University of Dayton

Spring 2020

Table of Contents (TOC)

Course Description

CPS 482/582 (3 hours) Formal languages (regular, context-free, recursive, and recursively enumerable), machine models (deterministic and non-deterministic finite automata, push down automata, Turing machines), grammars (regular, context-free, and unrestricted), interplay among these concepts, Church-Turing thesis, and undecidability. Prerequisite(s): CPS 341.

Course Details

Pre-requisite:
CPS 341: Discrete Structures.
Meeting times:
Mon Wed Fri 11:15am-12:05pm, Fitz Hall Room 650.
Instructor:
Dr. Perugini, e-mail id: sperugini1, tel: 229-4079, office: AN 145
OHs:
    T9:45am-12:15pm;
    Th 9:45am-12:15pm (only when classes are in session); & by appointment.

TOC

Required Textbook(s)

    [FLPI] Formal Languages: A Practical Introduction by A.B. Webber. (2008). Wilsonville, OR: Franklin, Beedle and Associates, Inc. ISBN: 9-781590-281970.

    [PLCI] Programming Languages: Concepts and Implementation by S. Perugini. 2020. Draft (Available as a Resource in Isidore; only ``Chapter 2: Formal Languages and Grammars'' needed for this course.).

TOC

Course Wordle

CPS 482/582: Automata Theory/Spring 2020

TOC

Learning Outcomes

TOC

Course Outline

(required reading assignments, & course notes)

(unless otherwise specified, all textbook references below are to [FLPI])

(All slides in third column below provided courtesy Adam Brooks Webber & Franklin, Beedle, & Associates, Inc.)

(All source code in the fourth column below provided courtesy Adam Brooks Webber & Franklin, Beedle, & Associates, Inc.)

(All slides in fourth column below provided courtesy David Bunde, Professor, Department of Computer Science, Knox College)

Class Meeting Topics (to be) Covered Required Reading & Slides Helpful Materials
13 Jan Introduction & learning outcomes Preface (pp. viii-xii)  
15 Jan Alphabets, strings, & languages Chapters 1
17 Jan Alphabets, strings, & languages exercises Chapters 1
22 Jan DFAs; Creating DFAs; formal definition Chapter 2
24 Jan DFA closure under complement, intersection, and union §§ 3.1-3.3 DFA slides (part i)
27 Jan Mystery DFAs & invariants § 3.5 DFA slides (part ii)
29 Jan Homework I solutions Chapter 2
31 Jan Applications of DFAs; implementing DFAs (state- and table-based approaches) Chapter 4 Mod3.java & Mod3Filter.java (state-based approach) source code files
3 Feb Non-determinism; NFAs; (1/2)L Chapter 5 NFA slides
5 Feb NFAs; Equivalence of DFAs & NFAs Chapter 6 NFA slides ii
7 Feb Applications of NFAs; implementing NFAs (backtracking search and bit-mapped parallel search approaches) §§ 6.1-6.2 NFA1.java & NFA1Filter.java (backtracking search approach) and NFA2.java & NFA2Filter.java (bit-mapped parallel search approach)
10 Feb Regular expressions Chapter 7 essential REs
12 Feb HW2 solutions; Regular expression practice Chapter 7
14 Feb Regular expression practice; regular expression tools ([e]grep and f?lex) Chapter 8 comprehensive REs e?grep REs Linux REs (grep) & full REs (egrep); RE exercises i & ii; exercise in writing REs; more REs; & lex; & [f]lex review
17 Feb EXAM I (coverage: Chapters 1-8)
19 Feb Regular expression practice; regular expression tools ([e]grep and f?lex) Chapter 8
21 Feb Regular expression practice; regular expression tools ([e]grep and f?lex) Chapter 8
24 Feb Exam I solutions; Regular expression practice; regular expression tools ([e]grep and f?lex) Chapter 8
26 Feb Equivalence of regular expressions & NFAs Chapter 7 slides
28 Feb Introduction to Grammars §§ 10.1-10.3 grammars
2 Mar Grammars §§ 10.1-10.3 grammars
4 Mar Grammars §§ 10.4-10.6 grammars
6 Mar Precursor proofs to the pumping lemma for regular languages §§ 11.1-11.2
9 Mar Pumping lemma for regular languages; Pumping lemma examples; using closure to prove non-regularity §§ 11.3-11.4 slides
11 Mar Homework IV solutions (classes cancelled by University) Chapter 10
13 Mar EXAM II (coverage: Chapters 1-11, focusing on Chapters 10 & 11) (classes cancelled by University)
16 Mar Spring Break
18 Mar Spring Break
20 Mar Spring Break
Due to the COVID-19 pandemic, this course is conducted as a distance learning (online) course from this point forward.
23 Mar EXAM II (coverage: Chapters 1-11, focusing on Chapters 10 & 11)
25 Mar Exam II solutions Chapters 10 & 11; [PLCI] §§ 2.1-2.4
27 Mar Exam II solutions Chapters 10 & 11; [PLCI] §§ 2.1-2.4
30 Mar Homework IV solutions and context-free grammars Chapters 10 & 11, & §§ 12.1-12.4; [PLCI] §§ 2.5-2.10 CFG slides
1 Apr Ambiguity; operator precedence and associativity §§ 12.5-12.7; & [PLCI] §§ 2.5-2.10 CFG slides ii
3 Apr Homework V solutions; Introduce stack machines §§ 13.1-13.4 Stack machine slides
6 Apr Stack machines §§ 13.5-13.8 Stack machine slides
8 Apr Equivalence of stack machines & CFG §§13.4-13.8 Stack machine slides ii; Stack machines and CFGs slides
10 Apr Good Friday (no class)
13 Apr Easter Monday (no class)
15 Apr EXAM III
class cancelled
17 Apr Homework VI solutions; Pumping parse trees §§ 14.1-14.2 Pumping parse tree slides
20 Apr Closure properties for CFLs §§ 14.3-14.4 Closure property for CFLs slides
22 Apr Bro. Joseph W. Stander Symposium—Alternate Day of Learning (no class)
24 Apr Pumping lemma for CFL §§ 14.5-14.7 Pumping lemma for CFL slides
27 Apr Pumping lemma for CFL §§ 14.5-14.7 Pumping lemma for CFL slides
29 Apr Parsing; parser generators Chapter 15 & [PLCI] Chapter 3 Parsing slides; code
1 May Language classifications and the Chomsky hierarchy §§ 18.10-18.11 & [PLCI] § 2.11 Chomsky hierarchy notes in Isidore
7 May FINAL EXAM (2:30pm-4:20pm); Fitz Hall Room 650 online on Isidore

TOC

Evaluation Criteria

(all figures below are approximate, and subject to change within the first few weeks of the course)
Component Quantity Points per Total points
Homeworks ~9 varies 250 (+ 10 EC)
Exams (and ~daily quizzes) 3 2 ~150 450 300 (+ 33 EC)
(comprehensive) Final exam and/or final project 1 300 300
Total:1,000 850(+ 43 EC)

Homeworks involves mostly analytical and theoretical exercises. There may be some programming exercises. To prepare students for the realities of computer science problems in industry and graduate school (and beyond) this course encourages (and rewards) self-reliance and independent, self-directed work. Handwritten assignments are not accepted. Assignments are due at 11:15am in class. Late assignments are not accepted. No exceptions. All exams are in-class, closed-book, and closed-notes. Attendance is mandatory at all examinations; make-ups are not given. Any missed examination will result in a zero. Make no assumptions about anything; always consult the instructor first. Final letter grades of A, A-, B+, B, B-, C+, C, C-, and D start approximately at 93, 90, 87, 83, 80, 77, 73, 70, and 60 percent, respectively.

TOC

Workload

CPS 482/582 is a challenging course and moves at a very fast pace. Spending a minimum of five hours outside of class each week reading, studying, and programming is required. I advise you to see me to discuss any problems you may have before you are evaluated.

TOC

Classsroom & Course Policies

Students are expected to conduct themselves with respect, integrity, and virtue. Keep phones and similar devices in a silent mode and put away during class (i.e., out of sight). The use of laptop computers and similar devices is not permitted in class. Audio or video recording of any kind in class is strictly prohibited.

TOC

Academic Integrity

To achieve the course objectives, homework assignments must be a sole result of your team's work, not be shared with other teams, and prepared in accordance with the University Honor Pledge (see below). Moreover, you may not plagiarize code from any, cited or uncited, textbooks, online resources, or other authors. Discussions among classmates must never include pending assignments. No exemptions. All questions and comments about a pending assignment must only be directed to the instructor. Evidence indicating a violation of this policy will be handled according to the University Academic Honor Code and result in a doubly-weighted zero which will not be dropped (e.g., if the assignment is worth 100 points, you receive a 0/200) or a zero on the next exam. Make no assumptions about this policy; always consult the instructor first. No student should ever feel that they must resort to academic dishonesty. You are encouraged to consult the instructor if you are struggling with the course or an assignment. No grade is worth your integrity. Honesty in your academic work will develop into professional integrity. The faculty and students of the University of Dayton will not tolerate any form of academic dishonesty.

The Honor Pledge as listed in the Academic Honor Code section of the Undergraduate Catalog applies in full to CPS 482.

The Honor Pledge as listed in the Academic Honor Code section of the Graduate Catalog applies in full to CPS 582.

Honor code FAQ

TOC

Homeworks

Homework Assigned Due Total points
Homework #1 Jan 23 Jan 29 30
Homework #2 Feb 5 Feb 12 50
Homework #3 Feb 24 March 2 30
Homework #4 Mar 4 Mar 11 23 50
Homework #5 Mar 25 Apr 3 60
Homework #6 Apr 3 Apr 15 40
Total Homework Points: 250 (+10 EC)

TOC

Exams

(all exams are closed book, closed notes)

TOC

Homework Support Tools

Quick Reference Sheets

TOC

Other Helpful ...

Programming style guide


Grades:
available in Isidore

Computer accounts:
UDit | A beginner's guide to effective e-mail

Helpful links:
academic calendar (PDF) | student handbook | UDit FERPA policies

Feedback:
Dr. Perugini welcomes any feedback you may have on the course motif and approach, style of the lectures, the concepts presented in class, the course webpage, homeworks, deadlines, exams, course and grading policies, or your general experience in the course.

TOC

Last modified:
ad majorem Dei gloriam

✞ JMJ ✞