Diskussion:Deterministisch kontextfreie Sprache

Unter den Abschlusseigenschaften war aufgeführt, dass DCFL abgeschlossen unter Epsilon-freien Homomorphismen ist. Hab's geändert. Hier dazu das Gegenbeispiel:

DCFL sind nicht abgeschlossen unter Anwendung Epsilon-freier Homomorphismen.
DP = deterministischer Kellerautomat
DP = DCFL

$L=\{1a^{n}b^{n}c^{m}|n,m\in \mathbb {N} \}\cup \{2a^{n}b^{m}c^{m}|n,m\in \mathbb {N} \}\$

h sei ein Epsilon-freier Homomorphismus:

$h(1)=h(2)=1\$

$h(a)=a\$

$h(b)=b\$

$h(c)=c\$

Dann gilt:

$h(L)=\{1a^{n}b^{m}c^{l}|n=m\lor m=l\}\$

$L\in 1DP\$

$h(L)\notin 1DP$

(Der vorstehende, nicht signierte Beitrag stammt von 84.186.34.230 (Diskussion • Beiträge) 1:56, 21. Mar 2007) -- PvQ Bewertung - Portal 01:57, 21. Mär. 2007 (CET)

DCFL vs. LR(k)

Im Artikel steht:

Jede LR(k)-Grammatik beschreibt eine deterministisch-kontextfreie Sprache. Strenggenommen gilt die Umkehrung zwar nicht, denn es gibt deterministisch-kontextfreie Sprachen, die keine LR(0)-Sprachen sind (d.h. nicht als LR(0)-Grammatik darstellbar sind), jedoch lassen sie sich durch Einführung einer eindeutigen Markierung für das Wortende in eine solche überführen.

Das ist Unfug; die Umkehrung ist doch: Für jede deterministisch kontextfreie Sprache L gibt es ein k, so dass L eine LR(k)-Sprache ist. Und die gilt. Trotzdem sollte der Hinweis auf die LR(0)-Sprachen bleiben. Wenn niemand was dagegen hat, ändere ich den Artikel entsprechend. -- UKoch 22:58, 9. Jun. 2011 (CEST)

Hab's jetzt geändert. -- UKoch 18:12, 3. Aug. 2011 (CEST)

Mächtigkeit von LALR- und SLR-Parsern

Im Abschnitt "Verhältnis zu anderen Sprachklassen" steht:

Da die Konstruktion eines LR-Parsers aus einer LR(1)-Grammatik für eine deterministisch kontextfreie Sprache häufig zu sehr großen Parse-Tabellen führt, werden in der Praxis leichte Einschränkungen vorgenommen, die zu geringerer Mächtigkeit führen. Die beiden Einschränkungen dieser Art sind LALR- und SLR-Parser.

Worauf bezieht sich dabei die Mächtigkeit? Auf Sprachebene gilt doch LR(k)=LALR(k)=SLR(k)=LR(1)=LALR(1)=SLR(1). --141.3.44.17 17:16, 25. Mai 2016 (CEST)