Theory of automata and formal languages


Aim of the course

The aim of the course is to introduce the theory of automata and formal languages. There are presented basic concepts, classification of formal languages, building of automata that accept languages and their use.

Lecture programme

Natural language and formal language. Definition of formal language. Concepts and basic operations. Chomsky’s classification. Context-free grammar, unambiguity of grammar. Grammar analysis. Nondeterministic and deterministic stack-based automaton. Stack-based automaton and context-free grammar. From context-free grammar to stack-based automaton. Closeness property of context-free languages. Cocke-Younger-Kasami’s Algorithm. Regular expressions, regular languages. Deterministic (DFA) and nonderministic (NFA) finite automaton. Regular grammar. From regular expression to DFA. Myhill-Nerode Theorem. Minimization of finite automaton. From DFA to regular expression and regular grammar. Closeness property regular languages. Contextual languages and linear-bounded automata. Nondeterministic and deterministic Turing machines. Recursive and recursively enumerable languages. Unsolvable problems. Languages that are not recursively enumerable.

Overview of the course elements

The course comprises classes in auditorium. The content of the classes consolidates and extends the knowledge taught during the lectures. There are tasks to be solved, some theoretical results are to be proven.

Reading list

1. A. V. Aho, Sethi R., Ullman J.D.: Compilers. Principles, techniques, and tools, Addison, 2006
2. Homenda W.: Elements of mathematical linguistics and automata theory, Publishing House of Warsaw University of Technology, 2005
3. Hopcroft J. E., Motwani R., Ullman J.D.: Introduction to automata theory, languages, and computation, Addison Wesley, 2006
4. KA Ross, CRB Wright: Discrete Mathematics, PWN, 1996
5. M. Sipser: Introduction to the theory of computation, WNT, 2009

Copyright © 2010 Department of Computer Science   |   AGH University of Science and Technology   |   Created by Creative Bastards