CS 330: Formal Methods and Models
George Mason University Department of Computer Science
Section 001: Fall 2020 - 1:30-2:45pm Mon/Wed - Online
Section 002: Fall 2020 - 12:00-1:15pm Tue/Thu - Online
Section 003: Fall 2020 - 7:30-8:45am Tue/Thu - Online
Instructor: Ivan Avramovic
Email: iavramo2-at-gmu.edu
Hours: Tuesday/Thursday 10:30-11:30 (see Piazza for the link)

Assistants:
TBA

Prerequisites: CS211 and MATH125 (C or better in both)
Textbook: Hamburger and Richards, Logic and Language Models for Computer Science, Third Edition

Webpage: https://cs.gmu.edu/~iavramo2/classes/cs330f20.html
Piazza: https://piazza.com/ for questions and discussion
Lectures: Lectures will be synchronous via Blackboard Collaborate Ultra within the Blackboard section for this course. Each lecture will be recorded and made available online.
Schedule: see below

Description

This course is an introduction to two kinds of formal systems - languages and logics - with important applications to computer science. The study of formal languages underlies important aspects of compilers and other language processing systems, as well as the theory of computation. Various systems of logic and automatic reasoning are put to use in artificial intelligence, database theory and software engineering. The entire course will give you practice in precise thinking and proof methods that play a role in the analysis of algorithms. The programming assignments provide practical experience with some theoretical topics.

Outcomes

  1. Students will understand the concepts and relevance of logic, formal languages and automata theory, and computability.
  2. Students will be able to do mechanical formal proofs, program correctness proofs and solve problems in first-order logic.
  3. Students will be able to solve problems in elementary machine models: designing finite-state, pushdown and turing machines.
  4. Students will be able to solve problems in formal languages: writing regular expressions, regular grammars, and context-free grammars.
Topics

Grades

Policies

Honor Code

Programming assignments are an individual effort, no group work is allowed. This includes the sharing of test cases. Any direct contribution on a quiz, exam, note sheet or programming assignment will be treated as a violation of George Mason's Honor Code.

Schedule

Week Date Topic Assignments/Notes
week 1 Aug 24,25 Introduction; Mathematical Preliminaries, Sections 1.1-1.6
Aug 26,27 Propositional Logic, Sections 2.1-2.6 HW 2.4, 2.6, 2.7, 2.10a, 2.11
week 2 Aug 31,Sep 1 Quiz 1 (Ch 2), Sep 4-6
Sep 2,3 Proofs by Deduction, Sections 3.1-3.7 HW 3.8, 3.9, 3.11 (2nd-6th)
week 3 Sep 8,9 Quiz 2 (Ch 3), Sep 11-13; (Labor Day: no class Mon Sep 7)
Sep 10,14 Predicate Logic, Sections 4.1-4.5 HW 4.1, 4.3, 4.7, 4.8a,b
week 4 Sep 15,16 Quiz 3 (Ch 4), Sep 18-20
Sep 17,21 Mathematical Induction, Sections 5.1,5.2,5.4,5.5 HW 5.2-5.4, 5.6
week 5 Sep 22,23 Quiz 4 (Ch 5), Sep 25-27
Sep 24,28 Program Verification, Sections 6.1-6.4 HW 6.2-6.6
week 6 Sep 29,30 Quiz 5 (Ch 6), Oct 2-4
Oct 1,5 Midterm review
week 7 Oct 6,7 Midterm covers material from chapters 1-6; Sample midterm Midterm Oct 6-11 (no lecture due to midterm)
Oct 8,13 Language Basics; Regular Languages, Chapter 7 + Sections 8.1-8.4 HW 7.4, 7.5, 7.12, 7.15, 8.2, 8.3, 8.6
week 8 Oct 12 No class (Fall break: Monday class meets Tue Oct 13)
Oct 14,15 Quiz 6 (Langs), Oct 16-18
week 9 Oct 19,20 Regular Expressions; Regular Grammars, Sections 8.4, 8.6, 8.7 HW 8.8, 8.9, 8.11, 8.12
Oct 21,22 Quiz 7 (REs/RGs), Oct 23-25
week 10 Oct 26,27 Regular Grammar Conversions, Sections 8.8,8.9 HW 8.14, 8.15
Oct 28,29 Quiz 8 (RGs), Oct 30-Nov 1
week 11 Nov 2,3 Finite Automata, Sections 9.1-9.4,9.8 HW 9.4, 9.8, 9.16a, 9.17
Nov 4,5 Quiz 9 (DFAs), Nov 6-8
week 12 Nov 9,10 Nondeterministic Finite Automata; Properties of Regular Languages, Sections 9.5-9.7 HW 9.5, 9.6, 9.25
Nov 11,12 Quiz 10 (NFAs), Nov 13-15
week 13 Nov 16,17 Context-Free Grammars, Sections 10.1-10.4 HW 10.1, 10.2, 10.7
Nov 18,19 Quiz 11 (Ch 10), Nov 20-22
week 14 Nov 23,24 Pushdown Automata; Turing Machines, Sections 11.1,11.2, 12.2 HW 11.1, 11.4, 11.6, 11.9a (NPDA are allowed)
Nov 25,26 No class Thanksgiving break
week 15 Nov 30,Dec 1 Quiz 12 (Ch 11), Dec 2-4 (note dates)
Dec 2,3 Final review
exam week Dec 9-16 Final covers material from chapters 7-11; Sample final Section 001: Dec 8-9; Section 002: Dec 9-10; Section 003: Dec 14-15