 Regulärer Ausdruck & Äquivalenz rechtslineare Grammatik |
Maxpayne0
Grünschnabel
Dabei seit: 31.10.2017
Beiträge: 5
 |
|
| 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
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Maxpayne0: 31.10.2017 19:54.
|
|
31.10.2017 19:51 |
|
|
as_string 
Haudegen
Dabei seit: 06.11.2013
Beiträge: 639
Herkunft: Heidelberg
|
|
Hallo!
Zur 1: ich denke, das Plus muss erst nach der Klammer kommen.
Gruß
Marco
|
|
|
01.11.2017 10:17 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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: ![[latex]S \rightarrow abT[/latex]](http://www.matheboard.de/latex2png/latex2png.php?S \rightarrow abT) und ![[latex]T \rightarrow baU[/latex]](http://www.matheboard.de/latex2png/latex2png.php?T \rightarrow baU) sind nicht rechtslinear, der Rest passt?
Wenn meine Annahme stimmt, dann brauchst Du ja nur neue Nichtterminale einführen, welche ein Paar ersetzen. Bsp:
wird zu ![[latex]S \rightarrow aB[/latex]](http://www.matheboard.de/latex2png/latex2png.php?S \rightarrow aB) und ![[latex]B \rightarrow bT[/latex]](http://www.matheboard.de/latex2png/latex2png.php?B \rightarrow bT) .
Gruß,
Karlito
|
|
|
01.11.2017 11:03 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
| Zitat: |
Original von 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?
|
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.
| Zitat: |
Original von Maxpayne0
@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...
|
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 08:07 |
|
|
Maxpayne0
Grünschnabel
Dabei seit: 31.10.2017
Beiträge: 5
|
|
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 12:42 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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
|
|
|
02.11.2017 13:06 |
|
|
Maxpayne0
Grünschnabel
Dabei seit: 31.10.2017
Beiträge: 5
|
|
@Karlito
Der Vergleich war sehr hilfreich! Danke dafür.
Hat mein Verständnis für reguläre Ausdrücke verbessert.
Maxpayne0
|
|
|
12.11.2017 16:19 |
|
|
|
