We introduce and study the leftmost variant of the - rewriting systems (RS's) [10]. We first show that any leftmost RS generates a context- free language. Then, we exhibit a context-free language which can be generated by a RS, but cannot be generated by any leftmost RS. On the other hand, we prove that by restricting to letter bounded languages leftmost RS's exactly describe context-free languages. Moreover, we investigate the generative power of finite index vs. infinite index leftmost RS.
On leftmost = rewriting systems / M.P. Bianchi, B. Palano - In: Descriptional Complexity of Formal Systems / [a cura di] C. Campeanu, G. Pighizzini. - Charlottetown : University of Prince Edward Island, 2008. - ISBN 9780919013568. - pp. 61-72 (( Intervento presentato al 10. convegno DCFS tenutosi a Charlottetown nel 2008.
On leftmost = rewriting systems
B. PalanoUltimo
2008
Abstract
We introduce and study the leftmost variant of the - rewriting systems (RS's) [10]. We first show that any leftmost RS generates a context- free language. Then, we exhibit a context-free language which can be generated by a RS, but cannot be generated by any leftmost RS. On the other hand, we prove that by restricting to letter bounded languages leftmost RS's exactly describe context-free languages. Moreover, we investigate the generative power of finite index vs. infinite index leftmost RS.
| File | Dimensione | Formato | |
|---|---|---|---|
|
dcfs08.pdf
accesso riservato
Tipologia:
Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione
174.06 kB
Formato
Adobe PDF
|
174.06 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
