Genaue Erklärung der Grammatikregeln ?

Question

Hallo,

Ich verstehe L so, dass das Wort die Länge 2 hat xx und x sowohl 1 als auch 0 annehmen kann
Wörter aus L sind also: 10, 01, 11, 00. Die Beispiele für L sagen aber etwas ganz Anderes aus.
Könnt ihr mir die Regeln, die sich aus der Grammatik L ergeben erläutern?

danke

Answer 1

Wie Lukas schon richtig geschrieben hat, besteht die Sprache L einfach aus Wörter, die aus zwei exakt gleichen Teilen bestehen, die einfach hintereinander geschrieben werden, also xx.

Die Regeln für die Grammatik L, also Teilaufgabe b erzeugt für jede 0, die erzeugt wird, auch parallel ein N. Für die 1 wird parallel ein E erzeugt. Würde man die N und E direkt ersetzten, also jeweils aus einem A => 0A0 bzw. 1A1 erzeugen, dann hätten Sie ein Palindrom gebildet, also xx'. Dies möchten Sie aber nicht, also müssen Sie erst noch Umsortieren. Ihre Ableitung sieht jetzt zum Beispiel so aus: 111000ANNNEEET. Nun ersetzen Sie das letzte E mit ET => 1T und reichen die 1 von hinten nach vorne durch, bis sie das A erreicht haben. Dann nehmen Sie das nächste E und verfahren genauso. Das geht so lange, bis alle Es und As ersetzt sind und Sie nur noch A und T durch lambda ersetzten müssen.

Ich hoffe, dass das jetzt so klarer ist.

Viele Grüße

Friederike Pfeiffer-Bohnen und Lukas König

 

Answer 2

Hallo,

in der Sprache L sind alle Wörter enthalten, die man als "xx" schreiben kann, wobei x aus E* ist. Das Sternchen am E bedeutet (wie immer), dass das entsprechende Symbol beliebig oft vorkommen kann. Hier kann ein x also aus beliebig vielen Symbolen des Eingabealphabets E bestehen. Es ist deshalb nur wichtig, dass die erste Hälfte eines Wortes der Sprache L genau gleich aufgebaut ist, wie die zweite Hälfte. Die Teilworte können aber beliebig lang sein.

Gruß

Lukas (Tutor)