M. Tomko: Multi-Island Finite Automata and Their Even Computation, R. Kocman: Advanced LL parsing techniques

The seminar is organized by the Formal Model Research Group at the Department of Information Systems, Faculty of Information Technology, Brno University of Technology. As its central scientific topic, it discusses formal models and their applications. Recent presentations are to be found at http://www.fit.vutbr.cz/~meduna/work/doku.php?id=talks:seminar.

Author: Martin Tomko, FIT BUT
Title: Multi-Island Finite Automata and Their Even Computation
Abstract: This talk concerns the topic of a paper of the same name which discusses n-island finite automata whose transition graphs can be expressed as n-member sequences of islands i_1, i_2, ..., i_n, where there is a bridge leaving i_j and entering i_j+1 for each 1<= j<=n-1. It concentrates its attention on even computation defined as any sequence of moves during which these automata make the same number of moves in each of the islands. Under the assumption that these automata work only in an evenly computational way, the paper proves that the language family defined by m-island finite automata is properly contained in that defined by (m + 1)-island finite automata, for all m >= 0. This infinite hierarchy occurs between the family of regular languages and that of context-sensitive languages, and it represents an automaton-based counterpart to the grammar-based hierarchy resulting from n-parallel right-linear grammars. Open questions are formulated in the conclusion.

Author: Radim Kocman, PhD., FIT BUT
Title: Advanced LL parsing techniques
Abstract: LL parsing is usually one of the first techniques of syntactic analysis introduced during the basic study of compilers and formal languages. However, advanced courses often switch their attention solely to LR parsing and its variants, such as LALR and SLR parsing. The focus of this presentation is on advanced LL parsing techniques that push further the initial LL idea. These advanced techniques introduce some new beneficial properties for syntactic analysis and increase the power of the resulting parser to handle more complex constructions of programming languages. We will talk about full LL(1) parsing, general LL(k) parsing, and modified LL(k) parsing for an automaton with a one-symbol reading head.