Regulärer Ausdruck & Äquivalenz rechtslineare Grammatik |
| 31.10.2017, 19:51 | Auf diesen Beitrag antworten » | ||||
| Maxpayne0 | Regulärer Ausdruck & Äquivalenz rechtslineare Grammatik Hi an alle, ich sitze grad an einer Übung dran und bräucht etwas Hilfe. 1.) Ich möchte einen regulären Ausdruck angeben, der folgende Sprache spricht: Entweder 101 oder 001 oder eine beliebig viele Anzahl der Paare 01 und 10, wobei die Paare mindestens einmal vorkommen müssen (Reihenfolge der Paare ist beliebig). Wäre der reguläre Ausdruck so richtig: ((101|001)|(01|10+)) 2.) Ich soll folgende Typ-3 Grammatik in eine äquivalente rechtslineare Grammatik transformieren: G= ({a,b},{S,T,U},P,S) P={S->abT, S->aT, T->bS, T->b, T->baU, T->bU, U->aS, U->a, U->epsilon} Leider finde ich dazu nichts. Wäre jemand eventuell so freundlich und würde mir die Vorgehensweise erklären? Vielen Dank. Euer Maypayne0 |
||||
|
|
|||||
| 01.11.2017, 10:17 | Auf diesen Beitrag antworten » | ||||
| as_string | Hallo! Zur 1: ich denke, das Plus muss erst nach der Klammer kommen. Gruß Marco |
||||
| 01.11.2017, 11:03 | Auf diesen Beitrag antworten » | ||||
| Karlito | Hallo Maxpayne0, wenn ich das richtig sehe, ist die Grammatik schon fast rechtslinear. Es ist doch nur noch gefordert, dass nur Paare aus Terminalen und Nichtterminalen als Produktionsziel angegeben werden können, oder? D.h. die Produktionen: Wenn meine Annahme stimmt, dann brauchst Du ja nur neue Nichtterminale einführen, welche ein Paar ersetzen. Bsp: Gruß, Karlito |
||||
| 01.11.2017, 23:23 | Auf diesen Beitrag antworten » | ||||
| Maxpayne0 | @as_string Vielen Dank, klingt logisch! Eine Frage hätte ich zu Ausdrücken noch. Im Beispiel: ((101|001)|(01|10+)) heißt es ja auf der einen Seite (101|001) entweder oder, auf der anderen Seite (01|10) kann zwischen 01 und 10 beliebig gewählt werden. Wie ist das zu erklären? @Karlito Danke! Du hast vollkommen Recht, mir war bisher der Unterschied von Typ-3-Grammatiken und rechtslinearen Grammatiken nicht klar. Ist es eigentlich jedes Mal erforderlich eine Typ-3-Grammatik in eine rechtslineare umzuwandeln, um einen endlichen Automaten zu konstruieren? Das gäbe ja bei einigen Fällen ziemlich viele neue Zustände... |
||||
| Anzeige | |||||
|
|
|||||
| 02.11.2017, 08:07 | Auf diesen Beitrag antworten » | ||||
| Karlito |
Die Wahl entweder 01 oder 10 kann einfach durch das + beliebig oft wiederholt werden. Deswegen muss das Plus auch hinter die Klammer. Außerdem schließt beliebig viele doch auch keinmal ein, oder? Demnach müsste es außerdem ein Stern anstatt des Plus sein.
Ich gehe davon aus, dass es erforderlich ist, ohne es genau zu wissen. Das mit den vielen neuen Zuständen stört doch einen Computer nur, wenn es wirklich viele werden. Dafür kann er mit einem konstruierten endlichen Automaten besser umgehen als mit einer Grammatik. Gruß, Karlito |
||||
| 02.11.2017, 12:42 | Auf diesen Beitrag antworten » | ||||
| Maxpayne0 | Genau hast recht, ich bräuchte in dem Fall jedoch mindestens einmal jedes Paar. Um nochmal auf meine Frage zu kommen. Auf einem der Folien unseres Dozenten steht: ab | bc = die Sprache die das Wort ab UND bc enthält. (ab)* | (bc)+ (gemeint ist ein hochgestelltes Plus) = die Sprache die beliebige Anzahl ab enthält ODER beliebige Anzahl bc (mindestens einmal). Worin unterscheidet sich hier das UND und ODER? Es leuchtet mir einfach nicht ein ... Maxpayne0 |
||||
| 02.11.2017, 13:06 | Auf diesen Beitrag antworten » | ||||
| Karlito | Hallo Maxpayne0, beide Formulierungen meinen, dass beide Alternativen in der Sprache enthalten sind. Die deutsche Sprache ist hier vielleicht etwas uneindeutig. Analoges Beispiel, welche die selbe Tüte beschreibt: - Eine Tüte enthält rote und blaue Kugeln - Wenn man in die Tüte greift, erhält man rote oder blaue Kugeln Gruß, Karlito |
||||
| 12.11.2017, 16:19 | Auf diesen Beitrag antworten » | ||||
| Maxpayne0 | @Karlito Der Vergleich war sehr hilfreich! Danke dafür. Hat mein Verständnis für reguläre Ausdrücke verbessert. Maxpayne0 |
||||
|
|
