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) = Ω∞(logn). We establish the optimality of such bound. Finally, we show that, in case of unambiguous context-free grammars, the end lower bound for generating nonregular languages turns out to be linear.
A regularity condition for context-free grammars / B. Palano. - In: INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE. - ISSN 0129-0541. - 19:4(2008), pp. 845-857. ((Intervento presentato al 9. convegno International Workshop on Descriptional Complexity of Formal Systems tenutosi a Novy Smokovec nel 2007.
A regularity condition for context-free grammars
B. PalanoPrimo
2008
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) = Ω∞(logn). We establish the optimality of such bound. Finally, we show that, in case of unambiguous context-free grammars, the end lower bound for generating nonregular languages turns out to be linear.File | Dimensione | Formato | |
---|---|---|---|
pubblicato.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
660.21 kB
Formato
Adobe PDF
|
660.21 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.