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.
Titolo: | A regularity condition for context-free grammars |
Autori: | PALANO, BEATRICE SANTA (Primo) |
Parole Chiave: | Complexity measures; Context-free grammars |
Settore Scientifico Disciplinare: | Settore INF/01 - Informatica |
Data di pubblicazione: | 2007 |
Tipologia: | Book Part (author) |
Appare nelle tipologie: | 03 - Contributo in volume |
File in questo prodotto:
File | Descrizione | Tipologia | Licenza | |
---|---|---|---|---|
dcfs07.pdf | Post-print (versione accettata dall'editore) | Administrator Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.