arXiv
Open Access
2024
Axiomatizing NFAs Generated by Regular Grammars
Roberto Gorrieri
Abstrak
A subclass of nondeterministic Finite Automata generated by means of regular Grammars (GFAs, for short) is introduced. A process algebra is proposed, whose semantics maps a term to a GFA. We prove a representability theorem: for each GFA $N$, there exists a process algebraic term $p$ such that its semantics is a GFA isomorphic to $N$. Moreover, we provide a concise axiomatization of language equivalence: two GFAs $N_1$ and $N_2$ recognize the same regular language if and only if the associated terms $p_1$ and $p_2$, respectively, can be equated by means of a set of axioms, comprising 7 axioms plus 2 conditional axioms, only.
Penulis (1)
R
Roberto Gorrieri
Akses Cepat
Informasi Jurnal
- Tahun Terbit
- 2024
- Bahasa
- en
- Sumber Database
- arXiv
- Akses
- Open Access ✓