Invited Plenary Talk (Computer Science)

Formal grammars: a mathematical model of syntax

doc. Alexander Okhotin, PhD. Department of Mathematics,
University of Turku, Finland


Languages, both natural and artificial, represent structured information as sequences of symbols. Every language has its own way of encoding structure, known as its syntax. Formal grammars are mathematical models of definitions of syntax: a grammar defines the set of well-formed sentences in a language, as well as the structure of these sentences. The formal definitions serve as a basis for automated language processing, such as understanding a sentence in a natural language, or translating a computer program to machine code.

This lecture will present the basics of formal grammars and give an overview of the research on this topic. First, some simple examples of syntactical definitions will be transcribed as formal grammars, showing that the basic mathematical model of syntax -- a context-free grammar -- is consistent with the way people define syntax. Several variants of this model will be described, and their suitability for representing syntax assessed. The rest of the lecture will cover the basic mathematical properties of the important families of grammars, and demonstrate an algorithm for parsing a given string according to a grammar.