SFU Computing Science 06-1
________________________________________________________________________
MACM 300-3 SECT Intro. to Formal Languages and Automata with
Applications
Instructor: A. Sarkar WHERE
LECTURE TIME TBA ... EXAM TIME TBA
________________________________________________________________________
OBJECTIVE/DESCRIPTION:
The goal of this course is to begin to understand the foundations of
computation. Various models of computation exist, all of which capture
some fundamental aspect of computation. We will concentrate on three
classes of models: models with finite amount of memory (finite-state
automata); models with stack memory (push-down automata); and unrestricted
models (Turing machines). The notion of a formal grammar arises from the
need to formalize the informal notions of grammar and language. Many
formal grammars were invented: right-linear grammars, context-free
grammars and unrestricted grammars. These grammars can be placed in a
natural hierarchy. Surprisingly, there is a deep connection between these
grammars, the strings they generate (their language), and the models of
computation introduced above. This course will also briefly cover the
impact of formal language theory for many computer science applications:
in compilers, natural language processing, and program verification. For
more information go to:
http://www.cs.sfu.ca/ anoop/courses/MACM-300-Spring-2006/index.html
TOPICS:
o Regular Languages and Finite Automata: regular expressions,
deterministic and non-deterministic finite automata, uniqueness of
minimal finite automata, non-regular languages
o Context Free Languages and Pushdown Automata: grammars, derivation
trees, ambiguity, parsing, normalizing context-free grammars, the
hardest context-free language, letter equivalence of context-free
languages with regular languages, deterministic context-free
languages, non-context-free languages
o Turing Machines: equivalence of variants, the Church-Turing thesis,
alternative models of computation
o Hierarchy of Languges and Automata: recursive and recursively
enumerable languages, recognizing versus deciding a language,
context-sensitive grammars and languages
o Applications of Formal Language Theory: compilers, natural language
processing, program verification (automata over infinite strings)
GRADING:
To be announced later.
Students must attain an overall passing grade on the weighted average of
exams in the course in order to obtain a clear pass (C or better).
TEXTBOOKS:
o Introduction to the Theory of Computation, Michael Sipser, Thompson
Course Technology, 2005
REFERENCES:
o Introduction to Automata Theory, Languages, and Computation: 2/e,
John Hopcroft, Rajeev Motwani and Jeffrey Ullman, Addison-Wesley, 2001
o An Introduction to Formal Languages and Automata, Peter Linz, Jones
and Bartlett, 2000
o
PREREQUISITES/COREQUISITES:
MACM 201
Distributed: October 17, 2005
::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
Academic Honesty plays a key role in our efforts to maintain a high
standard of academic excellence and integrity. Students are advised that
ALL acts of intellectual dishonesty are subject to disciplinary action by
the School; serious infractions are dealt with in accordance with the Code
of Academic Honesty (T10.02)
(http://www.sfu.ca/policies/teaching/t10-02.htm). Students are encouraged
to read the School's Statement on Intellectual Honesty
(http://www.cs.sfu.ca/undergrad/Policies/honesty.html).