PAIS Lab seminar: Formal grammars after the Cuban missile crisis

At the session of our seminar,  Alexander Okhotin (University of Turku, Finnland) delivered a report "Formal grammars after the Cuban missile crisis"

Abstract:
Formal grammar appeared in the late 50s. of XX century, when the development of computer technologies required to strictly define the syntax of programming language, as well as natural languages. By October 1962, the basic concepts of the new theory were developed, and some results, which determined the initial views of formal grammars, were achieved. These views are still presented in modern textbooks on computer science.

Research in the field of grammar continued and afterThe Cuban missile crisis, and in the past half a century the views of formal grammars have changed. Erroneous concepts (such as context-sensitive grammars) gradually disappeared, and the principles of their classification also outdated. New types of grammars brought an understanding of formal grammars as a specialized logic for description of the syntax and syntax analysis as a way of aproving theorems in this logic; important role was played by Rounds's (1988), who described the various types of grammars as first-order logic fragments in a string. The purpose of this report is to describe how the concept of formal grammars has changed,what types of grammars are known today and how they relate to each other.