Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Kontextfreie Grammatik erzeugen - Frage zu Ersetzung
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Informatik-Forum -> Kontextfreie Grammatik erzeugen - Frage zu Ersetzung
 
Autor Nachricht
xpfreak
Junior Member
Benutzer-Profile anzeigen
Junior Member


Anmeldungsdatum: 20.05.2006
Beiträge: 68

BeitragVerfasst am: 26 Nov 2008 - 19:35:45    Titel: Kontextfreie Grammatik erzeugen - Frage zu Ersetzung

Hallo zusammen,
wenn ich eine Ersetzungsregel habe, bsw: S => SaSb | a werden dann die zwei S jeweils durch den gleichen Term substituiert oder kann man da variieren (bsw. ein S durch a und das andere durch SaSb)?
cyrix42
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 14.08.2006
Beiträge: 24256

BeitragVerfasst am: 26 Nov 2008 - 19:39:32    Titel:

Du kannst sie auch verschieden ersetzen. Also z.B. wäre damit auch folgende Ableitung korrekt:

S-> SaSb -> aaSB -> aaSaSbb -> aaaaSbb -> aaaaabb.


Cyrix
xpfreak
Junior Member
Benutzer-Profile anzeigen
Junior Member


Anmeldungsdatum: 20.05.2006
Beiträge: 68

BeitragVerfasst am: 26 Nov 2008 - 19:43:03    Titel:

Danke dir, schade. Hast du vllt. eine Ansatzidee, wie ich die folgende Grammatik erzeugen, die folgende Sprache erzeugt:

{uawb | u,w <- {a, b}*, |u| = |w|}

Das war nämlich meine Ansatzidee mit den zwei S... Smile
Armin Gibbs
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 06.02.2008
Beiträge: 992

BeitragVerfasst am: 26 Nov 2008 - 19:50:25    Titel:

Ich will mal, aus der Hüfte geschossen, behaupten, dass deine Sprache nicht kontextfrei ist. Du könntest also, sofern du eine kontextfreie Grammatik suchst, lange mit der Suche beschäftigt sein.
xpfreak
Junior Member
Benutzer-Profile anzeigen
Junior Member


Anmeldungsdatum: 20.05.2006
Beiträge: 68

BeitragVerfasst am: 26 Nov 2008 - 19:53:36    Titel:

Wir sollen im Übungsblatt aber zeigen, dass diese Sprache kontextfrei ist, indem wir eine kontextfreie Grammatik angeben...

Das "<-" entspricht einem ist Element von.
Armin Gibbs
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 06.02.2008
Beiträge: 992

BeitragVerfasst am: 26 Nov 2008 - 19:59:07    Titel:

Aha. Ich nehme den Schnellschuss also zurück und versuche mich mit einem anderen:

S -> Xb
X -> YXY | a
Y -> a | b
xpfreak
Junior Member
Benutzer-Profile anzeigen
Junior Member


Anmeldungsdatum: 20.05.2006
Beiträge: 68

BeitragVerfasst am: 26 Nov 2008 - 20:16:20    Titel:

Das ist ja genial, danke, sieht super aus Smile
theglide22
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 12.01.2009
Beiträge: 6

BeitragVerfasst am: 12 Jan 2009 - 23:07:21    Titel:

Hallo,
ich befasse mich auch im moment u.a mit dem thema kontextfreie Sprachen.
Könnte mir evtl. jemand die obige Aufgabe und Lösung erklären?
Ist es in der Aufgabe so gemeint, dass ein u entweder ein a oder b (oder ab, oder auch nichts wegen *) sein kann (w analog)?
Wie könnte ich dann mit dem angegebenen Lösungsvorschlag z.b das Wort
aabb erzeugen?
Vielen Dank
Smutje
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 19.07.2008
Beiträge: 3004
Wohnort: Gießen

BeitragVerfasst am: 12 Jan 2009 - 23:38:52    Titel:

theglide22 hat folgendes geschrieben:
Ist es in der Aufgabe so gemeint, dass ein u entweder ein a oder b (oder ab, oder auch nichts wegen *) sein kann (w analog)?


Code:
{uawb | u,w <- {a, b}*, |u| = |w|}


bedeutet, das für das u und das w alle Worte nach der Regel {a, b}* eingesetzt werden können, wobei u != w sein darf, aber die Länge von u und w identisch sein muss. Oder war die Frage, was {a, b}* bedeutet?

theglide22 hat folgendes geschrieben:
Wie könnte ich dann mit dem angegebenen Lösungsvorschlag z.b das Wort aabb erzeugen?


(wenn ich mich an Armin Gibbs' Lösung bedienen darf? Wink In Klammern jeweils die # der Regel)
S ->(1) Xb ->(2) YXYb ->(3) aXYb ->(2) aaYb ->(3) aabb
theglide22
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 12.01.2009
Beiträge: 6

BeitragVerfasst am: 13 Jan 2009 - 00:30:34    Titel:

yo danke für die gute und schnelle Antwort! hab das b aus Regel1 irgendwie ignoriert... Confused
Aber jetzt is alles klar. THX
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Informatik-Forum -> Kontextfreie Grammatik erzeugen - Frage zu Ersetzung
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum