The Algebra of Nondeterministic Finite Automata
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910312972681216 |
|---|---|
| author | Gorrieri, Roberto |
| author_facet | Gorrieri, Roberto |
| contents | A process algebra is proposed, whose semantics maps a term to a nondeterministic finite automaton (NFA, for short). We prove a representability theorem: for each NFA $N$, there exists a process algebraic term $p$ such that its semantics is an NFA isomorphic to $N$. Moreover, we provide a concise axiomatization of language equivalence: two NFAs $N_1$ and $N_2$ recognize the same 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 3 conditional axioms, only. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2301_03435 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | The Algebra of Nondeterministic Finite Automata Gorrieri, Roberto Formal Languages and Automata Theory Logic in Computer Science 68Q45, 68Q85 F.4.3; F.1.1 A process algebra is proposed, whose semantics maps a term to a nondeterministic finite automaton (NFA, for short). We prove a representability theorem: for each NFA $N$, there exists a process algebraic term $p$ such that its semantics is an NFA isomorphic to $N$. Moreover, we provide a concise axiomatization of language equivalence: two NFAs $N_1$ and $N_2$ recognize the same 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 3 conditional axioms, only. |
| title | The Algebra of Nondeterministic Finite Automata |
| topic | Formal Languages and Automata Theory Logic in Computer Science 68Q45, 68Q85 F.4.3; F.1.1 |
| url | https://arxiv.org/abs/2301.03435 |