Formal Methods and Models -Section 002 - Spring 2013


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 in Lex and Prolog provide practical experience with some theoretical topics.

Course Outcomes


Class Details



Teaching Assistant


, , \hline\hline \hline
TopicWeekChapter/ Parts
Introduction 1 1
Propositional Logic and Proofs 1-2 2-3
Predicate Logic and Proofs 3-4 4-5
Applications: Prolog and Verification 5-6 6-7
Exam #1 6 1-7
Finite Automata, Regular Expressios 7-9 8-10
Lex: a Regular Expression Language 10 11
Context-Free Grammars & Applications 11-12 12-13
Turing Machines & Solvability 13-14 14


Quizzes 20%
Programs 20%
Exams 60%

The two exams, including the final, each cover about a half of the semester; the final is not cumulative. Of these exams the highest score will count 35%, and the lowest 25%.