Zum neuen Informatik-Forum >>
 FAQFAQ   SuchenSuchen   MitgliederlisteMitgliederliste   BenutzergruppenBenutzergruppen   RegistrierenRegistrieren   ProfilProfil   Einloggen, um private Nachrichten zu lesenEinloggen, um private Nachrichten zu lesen   LoginLogin 

Grammatik für kontextfreie Sprache

 
Dieses Forum ist gesperrt, du kannst keine Beiträge editieren, schreiben oder beantworten.   Dieses Thema ist gesperrt, du kannst keine Beiträge editieren oder beantworten.    Informatikerboard.de Foren-Übersicht -> Theoretische Informatik
Vorheriges Thema anzeigen :: Nächstes Thema anzeigen  
Autor Nachricht
Drys@k



Anmeldungsdatum: 13.05.2006
Beiträge: 5

BeitragVerfasst am: 01. Jun 2006 19:14    Titel: Grammatik für kontextfreie Sprache Antworten mit Zitat

Hallo Leute,

ich möchte zur Sparache L1 welche kontextfrei ist ein geeignete Grammatik finden !

L1 := {a^m b^n | m, n >= 0, m ungleich n}

Dabei macht mir das m ungleich n ziemlich zu schaffen, weil mir nicht ganz klar ist, wie ich eine Produktion P erstellen kann, die beliebig viela a´s und b´s erzeugen kann ohne das entweder das a oder b immer öfter vorkommt als das andere. Da müsste ja iregend was zufälliges in der Produktion geschehen...

Würde mich über einen Denkanstoß sehr freuen..
bzw. vielleicht ist es ja ok die Produktion P so zu wählen das meinetwegen die a´s immer öfter vorkommen wie die b´s oder umgekehrt !!????

MfG

Drys@K
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
Crotaphytus



Anmeldungsdatum: 08.05.2005
Beiträge: 213

BeitragVerfasst am: 01. Jun 2006 19:25    Titel: Antworten mit Zitat

Hm... Ich weiß jetzt grad überhaupt nicht, wie ich dir da auf die Lösung helfen soll. Von daher schreib ich einfach mal was hin und du sagst mir, was du davon hältst... Augenzwinkern

s -> axyb
x -> ax
y -> by
x -> _ (leeres Wort)
y -> _

Müsste man eventuell noch an eure Definition von ner kontextfreien Grammatik anpassen und noch noch die Mengen der Variablen und der Terminale definieren. Aber prinzipiell sollts das gewesen sein...

_________________
Genie oder Wahnsinn? Wer kann es wissen...
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
Drys@k



Anmeldungsdatum: 13.05.2006
Beiträge: 5

BeitragVerfasst am: 01. Jun 2006 19:54    Titel: Antworten mit Zitat

Hallo Crotaphytus,

erstmal Danke für Deine schnelle Antwort.

Unter der Annahme, dass bei Deiner Produktion X und Y Variablen sind bzw. a und b Terminalsymbolde erzeugt Deine Grammatik das Wort a^2 b^2 und nicht das Wort a^m b^n bzw. kommen a´s und b´s bei Dir gleich oft vor welches gegen die Bedingung verstößt, dass es entweder mehr a´s als b´s geben darf oder umgekehrt.

MfG

Drys@k
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
Crotaphytus



Anmeldungsdatum: 08.05.2005
Beiträge: 213

BeitragVerfasst am: 01. Jun 2006 21:44    Titel: Antworten mit Zitat

Ja, x und y sind Variablen, a und b Terminale. Und sie erzeugt alles, was du haben willst. Beispiel gefällig? Nehmen wir mal aaab. Also, wir starten bei s (ich hab die Regeln dann auch einfach mal von oben nach unten durchnummeriert, damit du weißt, welche Regel ich anwende):

(1) s -> axyb
(2) -> aaxyb
(2) -> aaaxyb
(4) -> aaayb
(5) -> aaab

Fertig!

_________________
Genie oder Wahnsinn? Wer kann es wissen...
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
Drys@k



Anmeldungsdatum: 13.05.2006
Beiträge: 5

BeitragVerfasst am: 01. Jun 2006 22:23    Titel: re.. Antworten mit Zitat

OK du hast vollkomen recht...

Danke

Drys@k
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
Beiträge der letzten Zeit anzeigen:   
Dieses Forum ist gesperrt, du kannst keine Beiträge editieren, schreiben oder beantworten.   Dieses Thema ist gesperrt, du kannst keine Beiträge editieren oder beantworten.    Informatikerboard.de Foren-Übersicht -> Theoretische Informatik 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.
Du kannst Dateien in diesem Forum nicht posten
Du kannst Dateien in diesem Forum nicht herunterladen