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)

Bahman Pedrood, bpedrood-at-gmu.edu (GTA, grader for 002), hours 3-5pm Wed
Negar Nejatishahidin, nnejatis-at-gmu.edu (GTA, grader for 003), hours 10-noon Mon
Runyu Ma, rma5-at-gmu.edu (GTA, grader for 001), hours 10-11am Wed / 3-4pm Thu
Prakreet Singh, psingh28-at-gmu.edu (UTA), hours 5-6pm Fri/Sun

Prerequisites: CS211 and MATH125 (C or better in both)
Textbook: Hamburger and Richards, Logic and Language Models for Computer Science, Third Edition
Other requirements:
A computer with reliable Internet, web browser, and audio for use with Blackboard Collaborate Ultra videoconferencing
A scanner, camera, or digital drawing tool to use to prepare digital uploads of quizzes and exams

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 (look in the toolbar on the lefthand side). Each lecture will be recorded and made available online.
Schedule: see below


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.


  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.



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 and will typically result in failing the class.

Some kinds of participation in online study sites violate the GMU Honor code: these include accessing exam or quiz questions for this class; accessing exam, quiz, or assignment answers for this class; uploading of any of the instructor's materials or exams; and uploading any of your own answers or finished work. Always consult your syllabus and your instructor before using these sites.

Privacy statment

All course materials posted to Blackboard or other course site are private to this class; by federal law, any materials that identify specific students (via their name, voice, or image) must not be shared with anyone not enrolled in this class. All of our synchronous meetings in this class will be recorded to provide necessary information for students in this class. Recordings will be stored on Blackboard and will only be accessible to students taking this course during this semester.

Disability accomodations

Disability Services at George Mason University is committed to providing equitable access to learning opportunities for all students by upholding the laws that ensure equal treatment of people with disabilities. Students seeking accommodations for this class, please first visit http://ds.gmu.edu/ (ods@gmu.edu; (703)993-2474) for detailed information about the Disability Services registration process. Then please discuss the approved accommodations with the instructor. The Disability Services office can be found in Student Union Building I (SUB I), Suite 2500.

Diversity and inclusion

George Mason University promotes a diverse, inclusive, and anti-racist environment, under the belief that a just and equitable learning environment is a strong learning environment. Students are valued as individuals, irrespective of differences in race, ethnicity, national origin, first language, economic status, gender, gender expression and identity, sexual orientation, religion, disability, or age. As an important member of the GMU community, the Department of Computer Science is integral to the goal of cultivating an environemnt which is committed to inclusion and anti-racism.

Students who prefer to be addressed by a specific name or gender pronouns should share this information with the instructor (he/him). Additionally, name and pronouns can be changed in the GMU records.

Title IX

As a faculty member and designated "Responsible Employee," the instructor is required to report all disclosures of sexual assault, interpersonal violence, and stalking to Mason's Title IX Coordinator, per university policy 1412. Students who wish to speak with someone confidentially, should contact the Student Support and Advocacy Center (ssac@gmu.edu; (703)993-3686) or Counseling and Psychological Services (caps@gmu.edu; (703)993-2380). Assistance may also be sought from GMU's Title IX Coordinator (titleix@gmu.edu; (703)993-8730).


This class is fully online during the Fall semester, so it is not necessary to be on campus to participate in the class. However, any student who plans to be on campus is required to take the Safe Return to Campus training, found on Blackboard. For information regarding the virus and university policy regarding the virus, consult the Safe Return to Campus FAQ.


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 on the 6th/7th due to midterm)
Oct 8,12 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 13,14 Quiz 6 (Langs), Oct 16-18
Oct 15,19 Regular Expressions; Regular Grammars, Sections 8.4, 8.6, 8.7 HW 8.8, 8.9, 8.11, 8.12
week 9 Oct 20,21 Quiz 7 (REs/RGs), Oct 23-25
Oct 22,26 Regular Grammar Conversions, Sections 8.8,8.9 HW 8.14, 8.15
week 10 Oct 27,28 Quiz 8 (RGs), Oct 30-Nov 1
Oct 29,Nov 2 Finite Automata, Sections 9.1-9.4,9.8 HW 9.4, 9.8, 9.16a, 9.17
week 11 Nov 3 No class Election day
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