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.)

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck pumpinglemma turingmaschine tipp zahlendarstellung cmos klausurrelevant bonusklausur komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz minimierung sprachen nichtdeterministisch huffman chomsky-normalform fehler-in-aufgabe anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik fehlererkennbarkeit huffman-kodierung hauptklausur vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy endliche-automaten konjunktive-normalform pipelining zustände saalübung leeres-wort ohne-lösungen betriebssystem speicherorganisation moore monotone-grammatik 2-komplement fehler reguläre-sprache hammingzahl monoton lösungsweg pumping-lemma-für-kontextfreie-sprachen kodierung berechenbarkeit pumping-lemma klausureinsicht disjunktive-normalform info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin entscheidbarkeit minimierung-endlicher-automaten chomsky-klassen von-neumann-rechner binärzahl entscheidbar programmiersprachen aufzählbarkeit stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

0 Pluspunkte 1 Minuspunkt
74 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
in HU-3-1 von uafjv uafjv Tutor(in) (168k Punkte)  

2 Antworten

1 Pluspunkt 0 Minuspunkte

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

 

von uafjv uafjv Tutor(in) (168k Punkte)  
0 Pluspunkte 1 Minuspunkt

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)

 

von uafjv uafjv Tutor(in) (168k Punkte)  
...