Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Definitionsbereiche von n bei PPL

+1 Punkt
63 Aufrufe

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 ?

Gefragt 9, Feb 2016 in PUM-AA von utdtz utdtz Eins-Komma-Null-Anwärter(in) (3,110 Punkte)  

Eine Antwort

+1 Punkt
 
Beste Antwort
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.
Beantwortet 9, Feb 2016 von Lukas König Dozent (10,065,100 Punkte)  
ausgewählt 9, Feb 2016 von utdtz utdtz
...