Fall 2010: Formal Methods and Models [CS330]

Professor:
Carlotta Domeniconi, Rm 4404 ENG, carlotta\AT\cs.gmu.edu

Prerequisites:
CS211 and Math125 (C or better in both).
Exposure to Discrete Mathematics (as in MATH125) is important for success in this course.

Location and Time:
We meet in IH 134, TR 3:00pm  4:15pm

Textbook:
H. Hamburger and D. Richards, Logic and Language Models for Computer Science,
Prentice Hall, 2002.

Course Web Page
General Description and Preliminary List of Topics
This course is an introduction to two kinds of formal systems—languages and logics—that are crucial to large numbers of areas in computer science. The study of formal languages underlies important aspects of compilers and other language processing systems, software engineering, agents and multiagent systems, game development, robotics, and networking. Formal logics and automatic reasoning are put to use in artificial intelligence, database theory, and software engineering. The course gives students practice in precise thinking and proof methods that play a role in the analysis of algorithms. Programming assignments in Prolog and other programming languages provide practical experience with these theoretical topics.
Topics include:
Propositional Logic and Proofs; Predicate Logic and Proofs; Program Verification; Prolog; Finite Automata, Regular Expressions; ContextFree Grammars; Turing Machines and Solvability.
Outcomes
 Students will understand the concepts and relevance of logic, formal languages and automata theory, and computability.
 Students will be able to do mechanical formal proofs, program correctness proofs and solve problems in firstorder logic.
 Students will be able to solve problems in elementary machine models: designing finitestate, pushdown and turing machines.
 Students will be able to solve problems in formal languages: writing regular expressions, regular grammars, and contextfree grammars.
Grading
Quizzes: 20%
Programming Assignments: 20%
Exams: 60%
Quizzes and exams are closed book. The lowest quiz grade will be dropped. Programming assignments must be performed individually. Group work is NOT allowed. Any deviation from this policy will be considered a violation of the
GMU Honor Code
In order to receive a passing grade in this class, each student will also meet at least once with their academic advisor during the semester.