Computer Laboratory Home Page Search A-Z Directory Help
University of Cambridge Home Computer Laboratory
Computer Science Tripos Syllabus - Regular Languages and Finite Automata (50% option only)
Computer Laboratory > Computer Science Tripos Syllabus - Regular Languages and Finite Automata (50% option only)

Regular Languages and Finite Automata (50% option only) next up previous contents
Next: Software Engineering I (50% Up: Lent Term 2005: Part Previous: Programming in Java   Contents


Regular Languages and Finite Automata (50% option only)

Lecturer: Professor A.M. Pitts

No. of lectures: 6

This course is useful for Compiler Construction (Part IB) and Natural Language Processing (Part II).


Aims


The aim of this short course will be to introduce the mathematical formalisms of finite state machines, regular expressions and grammars, and to explain their applications to computer languages.


Lectures

  • Regular expressions. Specifying sets of strings by pattern-matching.

  • Finite state machines. Deterministic and non-deterministic finite automata and the languages they accept.

  • Regular languages I. The language determined by a regular expression is regular.

  • Regular languages II. Every regular language is determined by some regular expression.

  • The Pumping Lemma. Proof and applications.

  • Grammars. Context-free and regular grammars. The class of regular languages coincides with the class of languages generated by a regular grammar.

Objectives


At the end of the course students should

  • be able to explain how to convert between the three ways of representing regular sets of strings introduced in the course; and be able to carry out such conversions by hand for simple cases

  • be able to prove whether or not a given set of strings is regular

Recommended books


* Hopcroft, J.E., Motwani, R. & Ullman, J.D. (2001). Introduction to automata theory, languages, and computation. Addison-Wesley (2nd ed.).
Kozen, D.C. (1997). Automata and computability. Springer-Verlag.
Sudkamp, T.A. (1988). Languages and machines. Addison-Wesley.



next up previous contents
Next: Software Engineering I (50% Up: Lent Term 2005: Part Previous: Programming in Java   Contents
Christine Northeast
Wed Sep 8 11:57:14 BST 2004