A hierarchy theorem for regular languages over free bisemigroups
In this article a question left open in [2] is answered. In particular, we show that it is essential that in the definition of parenthesizing automata an arbitrary number of parentheses can be used. Moreover, we prove that the classes Regm of languages accepted by a parenthesizing automaton with at...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Published: |
2004
|
| Series: | Acta cybernetica
16 No. 4 |
| Kulcsszavak: | Számítástechnika, Nyelvészet - számítógép alkalmazása |
| Subjects: | |
| Online Access: | http://acta.bibl.u-szeged.hu/12741 |
| Summary: | In this article a question left open in [2] is answered. In particular, we show that it is essential that in the definition of parenthesizing automata an arbitrary number of parentheses can be used. Moreover, we prove that the classes Regm of languages accepted by a parenthesizing automaton with at most m pairs of parentheses form a strict hierarchy. In fact, this hierarchy is proper for all alphabets. |
|---|---|
| Physical Description: | 567-577 |
| ISSN: | 0324-721X |