Informatiker Board | Druckvorschau: Grammatik

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
-- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
--- Grammatik (http://www.informatikerboard.de/board/thread.php?threadid=1335)

Geschrieben von chaos0403x am 02.12.2012 um 18:08:

Grammatik

Hab mal ne Frage, wie kann ich zeigen das die kontextsensitive und die expansive Grammatik der selben Sprachklasse angehören.

LG

Geschrieben von Karlito am 02.12.2012 um 18:54:

Ohne weiter darüber nachgedacht zu haben:

Teilmengenbeziehung in beide Richtungen. Zeige für alle möglichen Produktionen, dass sie auch in der jeweils anderen Sprache enthalten sind.

VG,

Karlito

Geschrieben von chaos0403x am 02.12.2012 um 20:15:

Das hab ich an einem Beispiel schon gemacht, nur das mir die idee fehlt wie ich das formal und allgemein aufschreibe.

Geschrieben von Karlito am 03.12.2012 um 14:44:

Hallo,

das ist leider keine Sache die mir leicht fällt und ich habe leider momentan wenig Zeit die Frage zu beantworten.

Deswegen hier ein schnell zusasmmengeschusterter Ansatz:

Die Richtung $[latex]kontextsensitiv \subseteq expansiv[/latex]$ stelle ich mir recht einfach vor. Soweit ich es richtig in Erinnerung habe, sind die Produktionen kontextsensitiver Sprachen nicht verkürzend.

So kann man Argumentieren:
Alle Produktionen $[latex](xAy \rightarrow xzy) \in Kontextsensitiv [/latex]$ sind auch in der Menge der expansiven Sprachen enthalten, da die Produktionen nicht verkürzend sind und somit $[latex]|xAy| \leq |xzy|[/latex]$ .

Der Fall $[latex]S \rightarrow \epsilon[/latex]$ muss natürlich mit abgespeist werden.

Die Rückrichtung ist denke ich schwerer und da habe ich momentan auch (noch) keinen Ansatz.

Edit: Meistens ist es möglich vieles textuell zu beschreiben, solange es wasserdicht ist. Es muss oft nicht alles in Formeln gepackt werden, nur wenn es nötig und günstig ist.

VG,

Karlito