Grammars with Context Conditions and Their Applications
ALEXANDER MEDUNA
http://www.fit.vutbr.cz/~meduna

meduna@fit.vutbr.cz
Department of Information Systems
Faculty of Information Technology
Brno University of Technology, Czech Republic, Europe
Talk Duration: 50 minutes.
Abstract: In the classical formal language theory, we can divide grammatical productions into
context-dependent and context-independent productions, and based on this division, we cannaturally distinct context-dependent grammars, such as phrase-structure grammars, fromcontext-independent grammars, such as context-free grammars. Making a derivation step
according to context-dependent productions depends on rather strict conditions satisfied by thecontext surrounding the rewritten symbol while making a step according to context-independent
productions does not, so from this point of view, we obviously always prefer using contextindependent grammars to the others. Unfortunately, compared to context-dependent grammars,
context-independent grammars are significantly less powerful; in fact, most of them areincapable to grasp some aspects of quite common programming languages. On the other hand,most context-dependent grammars are equivalent to the Turing machines, and this remarkablepower represents their indisputable advantage. These pros and cons inspired the modern
language theory to introducing some new grammars that simultaneously satisfy theseproperties⎯(1) they are based on context-independent productions, (2) their context conditions
are significantly simpler than the strict conditions of classical context-dependent productions,and (3) they are as powerful as classical context-dependent grammars.
In the present talk, we overview the most essential types of these grammars, whosealternative context conditions can be classical into these three categories⎯(A) context
conditions placed on derivation domains, (B) context conditions placed on the use ofproductions, (C) context conditions placed on the neighborhood of the rewritten symbols.
As already pointed out, we want the context conditions as small as possible. Therefore, weconcentrate the investigation on the reduction of context conditions. Specifically, it reduces thenumber of some of their components, such as nonterminals or productions. It studies how toachieve this reduction without any decrease in this generative power, which coincides with thepower of the Turing machines. By achieving this reduction, it actually makes the partiallyparallel rewriting more succinct and economical, and this economization is obviously highly
appreciated both from a practical and theoretical standpoint. Regarding each of the discussed
grammars, we introduce and study their parallel and sequential versions, which represent twobasic approaches to grammatical rewriting in today’s formal language theory. That is, during
a sequential derivation step, a grammar rewrites a single symbol in the current sentential form
while during a parallel derivation step, a grammar rewrites all symbols. As context-free andE0L grammars represent perhaps the most fundamental sequential and parallel grammars,
respectively, we usually base the discussion of sequential and parallel rewriting upon them.
In the conclusion of this talk, we illustrate the applications of grammars with context
conditions by several biologically oriented examples.

The talk is based upon the author’s latest book Handbook of Mathematical Models for Languages
and Computation (written along with his PhD students Petr Horáček and Martin Tomko), The
Institution of Engineering and Technology, 2020.

Keywords: formal grammars; context conditions; basic properties; language families; reduction;
simplification; descriptional complexity; applications; perspectives.
Author: Prof. Alexander Meduna (born 1957 in Olomouc, Czech Republic ) is a theoreticalcomputer scientist and expert on compiler design, formal languages and automata. He is a full
professor of Computer Science at the Brno University of Technology. Formerly, he taught
theoretical computer science at various European and American universities, including theUniversity of Missouri, where he spent a decade teaching advanced topics of formal language
theory. He wrote over ninety papers related to theoretical computer scientist. His booksinclude••••••••

Meduna, Alexander (2000). Automata and Languages: Theory and Applications.
Springer Science & Business Media. ISBN 9781852330743.
Meduna, Alexander (2007). Elements of Compiler Design. CRC
Press. ISBN 9781420063233.
Meduna, Alexander (2014). Formal Languages and Computation: Models and TheirApplications. CRC Press. ISBN 9781466513457.
Meduna, Alexander; Švec, Martin (2005). Grammars with Context Conditions andTheir Applications. John Wiley & Sons. ISBN 9780471736554.
Meduna, Alexander; Techet, Jiří (2010). Scattered Context Grammars and TheirApplications. WIT Press. ISBN 9781845644260.
Meduna, Alexander; Zemek, Petr (2014). Regulated Grammars and Automata.
Springer. ISBN 9781493903696.
Meduna, Alexander; Soukup, Ondřej (2017). Modern Language Models andComputation: Theory with Applications. Springer. ISBN 9783319630991.
Meduna, Alexander; Horáček, Petr; Tomko, Martin (2020): Handbook of Mathematical
Models for Languages and Computation, The Institution of Engineering and Technology.

ISBN 978-1-78561-660-0.