Bilaterally Colored Finite Automata and their Regular Expressions with Application to Context-Free Parsing
A. S. Ito, Yoshiaki TAKAHASHI · 2024
Recently, we introduced and investigated a colored variant of finite automata, so-called "colored finite automata." Its accepting states are able to be differently colored each and therefore a single automaton can classify and distinguish multiple languages at once. In this paper, we further extend the concept of colored accepting states and propose a new automaton, called bilaterally colored finite automaton (biCFA) which can possess as many differently colored initial states as possible, rather than a specified single initial state.We next introduce its regular expression counterpart, called bilaterally colored regular expression (biCRE), which exactly expresses the same tuple of languages as accepted by the corresponding biCFA. Notably, the mono-colored version of colored regular expression is a succinct and intuitive alternative of the existing ordinary regular expression.We also demonstrate the usefulness and feasibility of biCREs by applying the concept to extended (i.e., regular right part) context-free grammar and exhibit a super-short pure Python program which parses familiar arithmetic expressions.