Axiomatizing NFAs Generated by Regular Grammars
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914905941082112 |
|---|---|
| author | Gorrieri, Roberto |
| author_facet | Gorrieri, Roberto |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_00502 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Axiomatizing NFAs Generated by Regular Grammars Gorrieri, Roberto Formal Languages and Automata Theory Logic in Computer Science 68Q10, 68Q45 F.1.1; F.4.3 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. |
| title | Axiomatizing NFAs Generated by Regular Grammars |
| topic | Formal Languages and Automata Theory Logic in Computer Science 68Q10, 68Q45 F.1.1; F.4.3 |
| url | https://arxiv.org/abs/2402.00502 |