Moodle#
Access to the course’s Moodle at Enseeiht, for those with the right registration.
Tools and API#
VCSN: a platform dedicated to the computation of finite state machines. (C++, Python)
available as a Docker image, with Jupyter:
docker run -d -p 8888:8888 lrde/vcsn:2.8couchbase/vellum: A Go library implementing an FST (finite state transducer)
BurntSushi/fst: Represent large sets and maps compactly with finite state transducers. (Rust)
JFLAP is software for experimenting with formal languages topics including nondeterministic finite automata, nondeterministic pushdown automata, multi-tape Turing machines, several types of grammars, parsing, and L-systems.
Bookmarks and such#
Regex golf, and an article you can follow to understand the gist of the rules.
References#
Introduction to Automata Theory, Languages and Computation. J. Hopcroft, R. Motwani, J. Ullman. Addison-Wesley, 2001
The Theory of Parsing, Translation, and Compiling. Aho-Ullman. Prentice-Hall, 1972.
Automata and Computability. Kozen. Springer 1997.
Le labyrinthe des automates. Malika More, Tangente éducation, N°42 : L’informatique débranchée.
Checking NFA equivalence with bisimulations up to congruence. Filippo Bonchi, Damien Pous. POPL 2013.
Regular Expression Matching Can Be Simple And Fast, Russ Cox, 2007. (Blog)
Index 1,600,000,000 Keys with Automata and Rust, Andrew Gallant, 2015. (Blog)
On The Intersection of Finite Automata, Dick Lipton, 2009. (Blog) Is it possible to check the emptiness of the intersection of two FSA in sub-quadratic time ?
The Exact String Matching Problem: a Comprehensive Experimental Evaluation Simone Faro, Thierry Lecroq, 2010.
Antichains:A new algorithm for checking universality of finite automata M. D. Wulf, L. Doyen, T. A. Henzinger, and J.-F. Raskin. CAV, vol. 4144 of LNCS, 2006.
Parser Generators#
ANTLR, or Another Tool For Language Recognition is a parser generator for LL(*). Based on an EBNF syntax.
Yacc, the “original” Compiler Compiler for UNIX. It is a Look Ahead Left-to-Right (LALR) parser generator. For modern usage, look at Bison, the GNU version of Yacc, or the pair camllex and camlyacc. Yacc is based on attribute grammars, mixing C code with rules definitions, and a separate program for the lexical analyzer part (e.g. flex).
Menhir, another parser generator for OCaml, that supports LR(1) grammar specifications.
Packrat Parsing an alternative to the use of context-free grammars based on the idea of ordered choice operator, which removes the problems related with ambiguities.
Parser Combinators provide another way to build parsers from specifications; see e.g. Higher-order functions for parsing. G. Hutton. Journal of Functional Programming. 2(3). 1992.
Everything is on Wikipedia#
Synchronizing word related to Černý’s conjecture: if a synchronizing word exists, can we always find one of size at most \((n-2)^2\)
Applications of Formal Language Theory#
- Building Blocks: Artist Driven Procedural Buildings; use grammars to help generate detailed and realistic buildings to use in vide games.