Fractal Automata: Recursion in Context-Free and in Deterministic and Linear Context-Free Languages

Abstract

In procedural programming languages, the order of executing the statements may follow a regular pattern, including sequences of statements, conditional and branching statements and loops. On the other hand, regular languages can be represented by finite state acceptors (finite automata), by regular expressions and by (a special form of) railroad diagrams (syntax diagrams) allowing alternatives, option, concatenation and iteration. Context-free languages can also be described by (the general form of) railroad diagrams allowing also recursion. Based on the analogy of finite automata and railroad diagrams, the transformation between node-labelled and edge-labelled graphs, special infinite state automata, namely the fractal automata, are established to characterize the class of context-free languages. Deterministic and linear variants are also investigated. To establish these connections, we also define such variants of pushdown automata that accept the deterministic context-free and linear languages by empty stack. A transformation between the pushdown automata and fractal automata is also shown. The proposed model gives some new insights and a new view of context-free languages, deterministic context-free languages, linear context-free and deterministic linear context-free languages.