Describing Formal Languages Using L-Graphs

Abstract

Formal language theory, which has been actively developing for nearly seventy years, encompasses problems for which solutions either remain undiscovered or are unsuitable for constructing practical methods. The difficulties stem from the complexity of analyzing computation protocols and derivations in classical frameworks such as Turing machines, pushdown automata, and others.This work explores a method of representing formal languages through L-graphs, which provide a more convenient conceptual framework for analysis. This approach enables the application of efficient graph theory methods to solve problems in formal language theory, particularly the optimization of formal descriptions using techniques known for finite automata (which can be viewed as the simplest representatives of L-graphs). Unrestricted L-graphs characterize the class of recursively enumerable languages, i.e., Chomsky type-0 languages. In other words, any recursively enumerable language can be defined by an Lgraph, and conversely, any language defined by an L-graph is recursively enumerable. Subclasses of L-graphs characterizing context-free and regular languages are also described.