2020/02/18 by Rance Cleaveland, Cleaveland, Rance
Computer Science · #D.3.1 #F.4.3 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Formal Methods in Verification #Logic, programming, and type systems #Semantic Web and Ontologies
paper · pdf · doi:10.48550/arxiv.2002.07562
openalex publication_date 2020/02/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04
This paper shows how the use of Structural Operational Semantics (SOS) in the style popularized by the process-algebra community can lead to a more succinct and useful construction for building finite automata from regular expressions. Such constructions have been known for decades, and form the basis for the proofs of one direction of Kleene's Theorem. The purpose of the new construction is, on the one hand, to show students how small automata can be constructed, without the need for empty transitions, and on the other hand to show how the construction method admits closure proofs of regular languages with respect to other operators as well. These results, while not theoretically surprising, point to an additional influence of process-algebraic research: in addition to providing fundamental insights into the nature of concurrent computation, it also sheds new light on old, well-known constructions in automata theory.