We define a complexity measure on context-free grammars called end. Roughly speaking, for a context-free grammar G, endG(n) measures the distance of variables from the ends of sentential forms along the derivations of words in L(G) of length n. We prove in a constructive way the regularity of L(G) whenever endG(n) is constant. Yet, we improve on this by showing that if L(G) is nonregular then endG(n) = Ω∞(log n). Finally, the optimality of such a lower bound is established.
A regularity condition for context-free grammars / B. Palano - In: Descriptional Complexity of Formal Systems / [a cura di] V. Geffert, G. Pighizzini. - Kosice, : Institute of Computer Science, 2007. - ISBN 9788070976883. - pp. 117-128 (( Intervento presentato al 9. convegno Descriptional Complexity of Formal Systems tenutosi a High Tatras nel 2007.
A regularity condition for context-free grammars
B. PalanoPrimo
2007
Abstract
We define a complexity measure on context-free grammars called end. Roughly speaking, for a context-free grammar G, endG(n) measures the distance of variables from the ends of sentential forms along the derivations of words in L(G) of length n. We prove in a constructive way the regularity of L(G) whenever endG(n) is constant. Yet, we improve on this by showing that if L(G) is nonregular then endG(n) = Ω∞(log n). Finally, the optimality of such a lower bound is established.
| File | Dimensione | Formato | |
|---|---|---|---|
|
dcfs07.pdf
accesso riservato
Tipologia:
Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione
162.53 kB
Formato
Adobe PDF
|
162.53 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.
