From Finite Automata to Fractal Automata - The Power of Recursion

Abstract

In procedural programming languages the order of executing the statements may follow a regular pattern, including sequence 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 (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, special infinite state automata, namely the fractal automata are established to characterize the class of context-free languages. A transformation between the pushdown automata and fractal automata is also shown. The proposed model gives some new insight and a new view of context-free languages.