Definitionsbereiche von n bei PPL

Question

Was sind die Definitonsbereiche von n für

-das PPL für reguläre Sprachen

-das PPL für kontextfreie Sprachen?

Der einführende Satz lautet ja:

"Es existiert eine Konstante n element N / N_0, sodass für alle w element L mit w größer gleich n ...."

Wann nehme ich N, wann N_0 ?

Answer 1

Es handelt sich bei beiden PPLs um große $n$ (vor allem um mit dem gewählten Automaten oder der gewählten Grammatik wachsende $n$) - ob die 0 dabei ist oder nicht ist völlig irrelevant.

Im Fall von EA muss das $n$ mindestens so groß sein wie die Anzahl der Zustände eines EA - EAs mit $0$ Zuständen wären nicht einmal theoretisch wohldefiniert. Bei Grammatiken wächst das $n$ sogar exponentiell mit der Anzahl der Nonterminale - und auch hier darf es nicht $0$ Nonterminale geben.