# Introduction to Formal Language Theory (NASSLLI 2014)

The course provides an introduction to the theory of formal languages, grammars and automatons for participants with no or little prior knowledge of formal systems. It concentrates on the question of "How complex are natural languages?" and introduces formal languages from a linguistic point of view. The following topics will be covered by the course: modeling natural languages as formal languages, the Chomsky hierarchy and the properties of its language classes, grammars and automatons for language generation and acceptance, and decision problems and the notion of reducibility. At the end of the course the participants will know the fundamental concepts of formal language theory, the central results and the basic proof techniques. They will gain the necessary methods to dive deeper into the subject by self-study. The course offers supplementary learning modules, such as short quizzes, take-home exercises and audio-visual material.# LECTURERS

## Wiebke Petersen

is associate professor in mathematical linguistics. She has taught several
courses on the theory of formal languages in German at the University of Düsseldorf, and
two at the University of Riga and at the Latvian National Library in English. website: http://user.phil-fak.uni-duesseldorf.de/~petersen/ |

## Kata Balogh

is postdoctoral fellow in computational linguistics with special interests in
formal and computational semantics, formal languages and other formal approaches of natural
language processing. She is currently teaching regular BA and MA courses
at the University of Düsseldorf. She was also teaching at the ILLC / University of Amsterdam. website: http://user.phil-fak.uni-duesseldorf.de/~balogh/ |

Institute of Linguistics and Information

Department of Computational Linguistics

Heinrich-Heine-Universität Düsseldorf

Universitütsstr. 1, 40225 Düsseldorf

Germany

# LECTURES

## Day 0

notions of basic set theorySLIDES

## Day 1

Introduction: Languages, Grammars and the Chomsky-hierarchySLIDES

Hilbert's Hotel

## Day 2

Regular languagesSLIDES

## Day 3

Context-free languagesSLIDES

## Day 4

Context-sensitive and Mildly context-sensitive languages, Turing-machineSLIDES animated version

(for displaying the animated Turing machines correctly)

SLIDES print version

(to print; without animated Turing machines)

## Day 5

Decision problemsSLIDES animated version

(for displaying the animated PCPs correctly)

SLIDES print version

(to print; without animated PCPs)

# COURSE MATERIALS

Exorciser: exorciser.jarto exercises finite-state machines, CYK parsing etc.

from: http://www.swisseduc.ch/compscience/exorciser/index.html

Turing machine simulator

example inputs for the simulator: TM examples

(copy one of the TMs into the simulator to run)

a "real" Turing Machine by Mike Davey

# EXERCISES

day 1: cross-word puzzleday 2: exercise FSAs with Exorciser; you can create your own exercises for constructing an FSA for a given language, converting regular expression to FSA, converting FSA to regular expression, removing epsilon-transitions and converting a non-deterministic FSA to a deterministic FSA

day 3: exercise minimalizing deterministic finite-state-machines with Exorciser; give a context-free grammar for language L2 and L3 on slide 19 and transform one of these grammars into Chomsky normal form;

day 4: using the Pumping lemma for CF languages prove that a

^{n}b

^{n}c

^{n}is not context-free; create a Turing machine for recognizing a

^{n}b

^{n}c

^{n}and one for generating a

^{n}b

^{n}c

^{n}(use the simulator and the example TMs)

# READINGS

Chomsky, Noam (1956): Three models for the description of language.*IRE Transactions on Information Theory*(2): 113-124. [LINK]

Hopcroft, John E. & Jeffrey D. Ullman (1979):

*Introduction to Automata Theory, Languages, and Computation*(1st ed.). Addison-Wesley.

Hopcroft, John E. & Rajeev Motwani & Jeffrey D. Ullman (2013):

*Introduction to Automata Theory, Languages, and Computation*(3rd ed.). Pearson.

Partee, Barbara H. & Alice ter Meulen & Robert E. Wall (1990):

*Mathematical Methods in Linguistics*. Kluwer Academic Publishers. chapters 16-21.