Passive Model Learning of Visibly Deterministic Context-free Grammars
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911116641173504 |
|---|---|
| author | Muškardin, Edi Burgstaller, Tamim |
| author_facet | Muškardin, Edi Burgstaller, Tamim |
| contents | We present PAPNI, a passive automata learning algorithm capable of learning deterministic context-free grammars, which are modeled with visibly deterministic pushdown automata. PAPNI is a generalization of RPNI, a passive automata learning algorithm capable of learning regular languages from positive and negative samples. PAPNI uses RPNI as its underlying learning algorithm while assuming a priori knowledge of the visibly deterministic input alphabet, that is, the alphabet decomposition into symbols that push to the stack, pop from the stack, or do not affect the stack.
In this paper, we show how passive learning of deterministic pushdown automata can be viewed as a preprocessing step of standard RPNI implementations. We evaluate the proposed approach on various deterministic context-free grammars found in the literature and compare the predictive accuracy of learned models with RPNI. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_16305 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Passive Model Learning of Visibly Deterministic Context-free Grammars Muškardin, Edi Burgstaller, Tamim Formal Languages and Automata Theory We present PAPNI, a passive automata learning algorithm capable of learning deterministic context-free grammars, which are modeled with visibly deterministic pushdown automata. PAPNI is a generalization of RPNI, a passive automata learning algorithm capable of learning regular languages from positive and negative samples. PAPNI uses RPNI as its underlying learning algorithm while assuming a priori knowledge of the visibly deterministic input alphabet, that is, the alphabet decomposition into symbols that push to the stack, pop from the stack, or do not affect the stack. In this paper, we show how passive learning of deterministic pushdown automata can be viewed as a preprocessing step of standard RPNI implementations. We evaluate the proposed approach on various deterministic context-free grammars found in the literature and compare the predictive accuracy of learned models with RPNI. |
| title | Passive Model Learning of Visibly Deterministic Context-free Grammars |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2508.16305 |