Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Palindrome
Gehe zu Seite 1, 2  Weiter
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Informatik-Forum -> Palindrome
 
Autor Nachricht
calippo
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 17.01.2009
Beiträge: 29

BeitragVerfasst am: 20 Mai 2009 - 17:58:09    Titel: Re: Palindrome

calippo hat folgendes geschrieben:

L als die Menge der Palindrome, über dem Alphabet Sigma{0,1}. Doch es soll das leere Wort kein Element von L sein.




wie kann ich denn diese Menge L formal beschreiben
sarc
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 21.09.2006
Beiträge: 2657

BeitragVerfasst am: 20 Mai 2009 - 18:32:03    Titel:

Das ist die Aufgabe, die du lösen sollst...

Mal ein anderes Beispiel: Nimm dir die Sprache 0+1+, also ne Folge von beliebig vielen 0en und dann beliebig viele 1en, davon jedesmal mindestens 1. Dazu könnten die Regeln einer Grammatik so aussehen:

s -> ab
a -> 0a | 0
b -> 1b | 1

Versuch selbst nachzuvollziehen, warum das passt. Und überleg dann, wie solche Regeln für Palindrome aussehen könnten.
calippo
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 17.01.2009
Beiträge: 29

BeitragVerfasst am: 20 Mai 2009 - 19:01:34    Titel:

also ich hatte schon was gelesen dazu, jedoch ist das leere wort hier enthalten. das sieht dann so aus:

S->0|1|epsilon
S->0S0|1S1

jedoch soll bei mir epsilon nicht dabei sein. kann ich dann einfach epsilon hier rausnehmen, also so:

S->0|1
S->0S0|1S1

??
sarc
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 21.09.2006
Beiträge: 2657

BeitragVerfasst am: 20 Mai 2009 - 19:49:44    Titel:

Probiers doch einfach aus... Wink

Offensichtlich kann das leere Wort nicht mehr erzeugt werden. Alles, was du erzeugst, sind Palindrome. Jetzt musst du nur noch gucken, ob die Erzeugung irgendwann abgebrochen werden kann. Wenn ja passts. Smile
calippo
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 17.01.2009
Beiträge: 29

BeitragVerfasst am: 20 Mai 2009 - 20:03:45    Titel:

sarc hat folgendes geschrieben:

Jetzt musst du nur noch gucken, ob die Erzeugung irgendwann abgebrochen werden kann. Wenn ja passts.


ich habe z.b das hier daraus erzeugt:

S->0S0->01S10->011S110->0111110

aber es wird ja nicht abgebrochen,man kann da ja noch anderes erzeugen
Smutje
Senior Member
Benutzer-Profile anzeigen
Senior Member


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

BeitragVerfasst am: 20 Mai 2009 - 20:16:11    Titel:

Wenn keine Nonterminale mehr vorhanden sind, die du ersetzen kannst, wie soll dann nicht abgebrochen sondern weiter gemacht werden?
sarc
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 21.09.2006
Beiträge: 2657

BeitragVerfasst am: 21 Mai 2009 - 00:32:33    Titel:

Üblicherweise gibt man die komplette Grammatik an, also die Menge der Nichtterminale, der Terminale, die Regeln und das Startsymbol.
calippo
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 17.01.2009
Beiträge: 29

BeitragVerfasst am: 21 Mai 2009 - 13:00:10    Titel:

Ok also die Menge L wird jetzt formal so beschrieben:

G=(Sigma,N,S,P), wobei
Sigma={0,1}, N={S}, und
P={S->0|1
S->0S0|1S1 }

so ok jetzt??

und ich habe dazu nochmal versucht das in Chomsky-Normalform umzuformen, kann jemand nochmal drüber schauen ob ich die neue Grammatik richtig angegeben habe:
Also ich erhalte Grammatik G'=(Sigma,N',S,P') mit
Sigma={0,1}
N'={S,A,B,C,D} und
P'={ S-> 0|1
S-> AC|BD
A->1
B->0
C->SA
D->SB }

ist dies richtig??
Smutje
Senior Member
Benutzer-Profile anzeigen
Senior Member


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

BeitragVerfasst am: 21 Mai 2009 - 13:04:58    Titel:

So vom Drüberschauen scheints zu passen, aber wieso spaltest du die Regel

Code:
S -> 0 | 1 | 0S0 | 1S1


immer in zwei Zeilen auf? Wink
calippo
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 17.01.2009
Beiträge: 29

BeitragVerfasst am: 21 Mai 2009 - 13:21:32    Titel:

ich weiss nicht Very Happy

was mir noch nicht so klar ist, ist wie ich das in Greibach-Normalform mit
L(G_GNF)=L angebe und wie ich den zugehörigen Kellerautomaten M1 angebe(sodass M1 die Sprache L per leerem Keller akzeptiert).

könnt ihr mir hier nochmal helfen bitte.
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Informatik-Forum -> Palindrome
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Gehe zu Seite 1, 2  Weiter
Seite 1 von 2

 
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