Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in SPR-AA

Beantwortet: Verwirrung Buch und Vorlesung

Wed, 05 Feb 2020 20:21:44 +0000

Es ist eine echte Teilmenge.

Aber das Skript ist an der Stelle auch nicht falsch, es ist nur schwächer in der Formulierung. Man kann ja auch schreiben
$$3 \leq 4$$
obwohl auch die noch schärfere Formulierung gilt:
$$3 < 4$$

Beantwortet: Wie funktioniert Sprachmächtigkeit

Fri, 12 Jan 2018 14:06:37 +0000

Hallo Jasper,

Bei den kontextfreien Sprachen wird unterschieden zwischen deterministischen und nicht deterministischen kontextfreien Sprachen. Eine det. kontextfreie Sprachen wird durch einen det. KA erkannt und eine n-det. kontextfreie Sprache durch einen n-det. KA.

Dabei ist die Deterministische eine Teilmenge von der Nichtdeterministischen.

Jede det. kontextfreie Sprache kann durch eine LK(A) Grammatik erzeugt werden (Für mehr Infos dazu siehe Kapitel 3, Folie 40). Jede n-det. kontextfreie Sprache wird von einer kontextfreien Grammatik erzeugt. Damit kann die kontextfreie Grammatik aber natürlich auch die det. kontextfreie Sprache erzeugen.

Damit gilt: L(det-KA) ist eine Teilmenge von L(ndet. KA)

Die Aussage: "L2 = L det Kellerautomat und L2 = L n.det. Kellerautomat" habe ich so noch nicht gesehen und muss in die oberen Fälle differenziert werden. So ist das auch abgebildet in der Übersicht zu den Sprachen.

Ich hoffe das konnte dir weiterhelfen!

Viele Grüße,

Timon (Tutor)

Beantwortet: Beispielgrammatik Typ-1-Sprache

Sat, 04 Feb 2017 14:55:41 +0000

Ja ich sehe das genau so, hier hat man keine Möglichkeit das S in ein Terminal zu überführen und kann somit keine Wörter generieren.

Beantwortet: minimale Reguläre Ausdrücke

Sat, 23 Jul 2016 18:00:59 +0000

Wenn nach einem Regulären Ausdruck gefragt ist, wird es wohl für einen korrekten Regulären Ausdruck die "korrekte" Anzahl Punkte geben.

Wenn z.B. nach einem minimalen Regulären Ausdruck gefragt wird wirst du wohl auch nicht die volle Punktzahl erhalten.

Bei einer allgemeinen Frage ist eine Algemeine Lösung richtig, bei einer spezifischen Frage nur eine spezifische Lösung.

Angaben ohne Gewähr ;)

Beantwortet: Wann schreibe ich bei nichtleeren Wörtern ein "+" in die Sprachdefinition und wann ein "*"?

Tue, 29 Dec 2015 10:58:00 +0000

Hey,

bei beiden Sprachen hast du richtig erkannt, dass durch die Form der Bedingungen das leere Wort nicht in den Sprachen enthalten ist. Ob du nun vorne bei der Definition der Zeichenmenge ein + oder * in den Exponenten schreibst, spielt für die Sprache somit keine Rolle: Das leere Wort ist durch die Bedingung in beiden Fällen nicht in der Sprache und soll das auch nicht. Du würdest in beiden Fällen die selbe Sprache definieren.

Bei der Sprache in Kapitel 4 Aufgabe 29 muss also nicht ein + im Exponenten stehen, kann es aber.

Mein persönlicher Ratschlag: Wenn die, zu beschreibende Sprache das leere Wort nicht enthalten soll, das + in den Exponenten schreiben. Damit läuft man nicht in Gefahr, dass "ausversehen" doch das leere Wort in der Sprache enthalten ist, falls man beim Aufstellen der Bedingung das leere Wort nicht ausschließt.

Viele Grüße
Ashvin (Tutor)

Beantwortet: Unterschied kontextsensitive und monotone Grammatik?

Wed, 22 Oct 2014 16:09:58 +0000

Hallo,

das ist eigentlich ganz einfach:

Kontextsensitive Grammatiken sind auch monoton (denn durch eine kontextsensitive Regel ϕAψ→ϕγψ wird immer ein einzelnes Zeichen A durch eine nichtleere Zeichenfolge γ ersetzt, also kann das Wort durch die Ableitung nicht kleiner werden).
Monotone Grammatiken sind nicht unbedingt kontextsensitiv (denn eine Regel wie AB→BA ist nicht kontextsensitiv).

Entsprechend sind kontextsensitive Grammatiken eine echte Teilmenge der monotonen Grammatiken, ABER:

Die Menge der durch monotone Grammatiken darstellbaren Sprachen ist gleich der Menge der durch kontextsensitive Grammatiken darstellbaren Sprachen. Beide Grammatiktypen können nämlich genau die Typ-1-Sprachen erzeugen.

Viele Grüße

Lukas König