Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Genaue Erklärung der Grammatikregeln ?

–1 Punkt
49 Aufrufe
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
Gefragt 22, Sep 2015 in HU-3-1 von uafjv uafjv Tutor(in) (167,990 Punkte)  

2 Antworten

–1 Punkt

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)

 

Beantwortet 22, Sep 2015 von uafjv uafjv Tutor(in) (167,990 Punkte)  
+1 Punkt

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

 

Beantwortet 22, Sep 2015 von uafjv uafjv Tutor(in) (167,990 Punkte)  
...