 Thema: Chomsky-Normalenform |
|
|
Ahhh okay, das macht die Sache auf jeden Fall klarer!
Weil unsere Professorin hat zu diesem Thema nur gesagt "Wird weggestrichen" , was nicht super viel geholfen hat... 
Danke dir!
|
|
| Thema: regulärer Ausdruck darf 010 nicht enthalten |
|
|
Also ich habe heute die Lösung herausgefunden und auch schon absegnen lassen...
es war iwas mit 1*(0*111*0)1*0* iwie so, weiß es grad aber nicht mehr auswendig ^^ wollte euch nur dran teilhaben, das wir auf jeden die lösung haben
Danke das ihr geholfen habt
|
|
| Thema: Chomsky-Normalenform |
|
|
Ich habe mich nun mal vorrangearbeitet, aber bei Schritt 3 (epsilon-Regel entfernen) , da komm ich nicht vorran!
Wenn ich eine Epsilonregel entferne, was muss ich dann dahinschreiben , bzw. wie notiere ich das?
G1 = ({S}, {0,1}, S, {S -> µ, S -> 0, S->1, S -> 0S0 , S -> 1S1})
S -> µ
S -> 0
S -> 1
S -> 0S0
S -> 1S1
Schritt 1:
Y0 -> 0
Y1 -> 1
S -> µ
S -> Y0
S -> Y1
S -> Y0SY0
S -> Y1SY1
Y0 -> 0
Y1 -> 1
Schritt 2:
E -> SY0
F -> SY1
S -> µ
S -> Y0
S -> Y1
S -> Y0E
E -> SY0
S -> Y1F
F -> SY1
Y0 -> 0
Y1 -> 1
Schritt 3:
Schritt 4 ist nicht nötig, da es hier keine Ketten und Kreise gibt..
Anmerkung: µ = epsilon
|
|
| Thema: Chomsky-Normalenform |
|
|
Hey Leute.
Wir haben heute die Chomsky-Normalenform gemacht und unser Tutor hatte uns zum überlegen folgende Aufgabe gegebe (Keine Sorge, die dient nicht der Abgabe oder so, er möchte uns einfach nur mehr Aufgaben geben zum üben):
Gib äquivalente Grammatiken in Chomsky-Normalform für folgende kontextfreie Grammatiken
G = (V; T; S; P) an.
1. G1 = ({S}, {0,1}, S, {S -> µ, S -> 0, S->1, S -> 0S0 , S -> 1S1})
Jetzt muss man ja in 4 Schritten vorgehen:
1. Alle Terminale in die Form Y_0 bringen mit Y_0 -> 0
2. Alle nebeneinander stehenden Variablen der Rechten Seite zusammenfügen.
3. Entfernen der epsilon - Regeln : Hier werden alle Regeln A -> µ , außer S' -> µ gestrichen. Für jede Regel, die ein solches A auf der rechten Seite enthält, wird eine Regel hinzugefügt, in der das A gestrichen wurde.
4. Beseitigung der Kettenregeln
Wir kamen leider nicht mehr dazu, diese Aufgabe in der Stunde durchzurechnen (er will es nächste mal tun), aber mich würd das jetzt schon interessieren, zumal es für den Übungszettel morgen hilfreich wäre, wenn ich die Chomsky-Normalenform draufhabe
Jetzt habe ich doch iwie Probleme, dieses Verfahren so darauf anzuwenden. Kann mir das vllt jmd mal anhand dieses Beispieles erklären?
|
|
| Thema: regulärer Ausdruck darf 010 nicht enthalten |
|
|
Japp 100% sicher, habe die Aufgabe absichtlich direkt kopiert, damit keine fehler passieren.
DAs ist aber auch das, was uns persönlich zweifeln lässt , also das "enthält nicht"
|
|
| Thema: regulärer Ausdruck darf 010 nicht enthalten |
|
|
Meine Frage:
Guten Tag: Ich habe hier eine Frage zu den regulären Ausdrücken. Hier die Aufgabe:
Gib reguläre Ausdrücke für die folgenden Sprachen über Sigma = {0,1} an:
(a) L1 = {w | w enthält nicht das Wort 010}
Meine Ideen:
Unsere Idee war erst, das wir (1)(0*111*0*)*(1) nehmen. Haben aber im Endeffekt rausgefunden, dass des nicht wirklich stimmt.
Kann uns da jmd weiterhelfen?
|
|
|
