Informatiker Board | Druckvorschau: Grammatiken

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)
---- formale Sprachen (http://www.informatikerboard.de/board/board.php?boardid=12)
----- Grammatiken (http://www.informatikerboard.de/board/thread.php?threadid=1181)

Geschrieben von Lisa23 am 14.03.2012 um 12:02:

Grammatiken

Hallo,
ich hätte ne frage wie man herausfinden kann um welche Wortmenge L es sich handelt .
z.b. bei
S--->A
A--->ab
A--->aAb
wie finde ich heraus was L ist was muss man da genau betrachten?
also ich weiss das A=ab ist oder aabb aber ich weiss nicht wie ich bei Grammatiken immer auf das L komme.

Mfg
Lisa

Geschrieben von Karlito am 14.03.2012 um 19:27:

Hallo,

eine Grammatik ist ja immer über ein 4-Tupel der Form

$[latex] G = (V, \Sigma, P, S)[/latex]$

definiert. Dabei Steht S für dein Startsymbol. Allermeist ist dies auch S, so wie es auch hier ist.

Ausgehend von dem Startsymbol kann man alle Wörter der Sprache über der Grammatik ableiten. Herauszufinden, um welche Sprache es sich handelt ist ein wenig schwierig. Am besten man versucht sich die ersten paar möglichen Ableitungen aufzuschreiben. Die meisten Aufgaben sind so gestellt, dass man erkennen kann, um welche Sprache es sich handelt. So wie auch hier. Etwas anderes kann ich dir nicht raten.

VG,

Karlito

Geschrieben von Lisa23 am 14.03.2012 um 20:47:

wäre hier
L={ab,aabb} falsch? weil ich weiss nicht was S--->A noch anderes sein kann ausser diese beiden möglichkeiten

Geschrieben von Karlito am 14.03.2012 um 21:07:

Hallo Lisa,

ja, ist leider unvollständig.

A -> aAb kannst du doch mehrfach anwenden. So ensteht z.B.

aAb -> (aAb für A einsetzen) aaAbb ->(ab für A einsetzen) aaabbb.

Was also entseht ist die Sprache a^n b^n, d.h. die Sprache aller Wörter, die gleich viele a und b enthalten.

VG,

Karlito