Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Frage: Chomsky & reguläre Sprache
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Informatik-Forum -> Frage: Chomsky & reguläre Sprache
 
Autor Nachricht
Schabernack
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 08.01.2009
Beiträge: 5

BeitragVerfasst am: 08 Jan 2009 - 20:22:59    Titel: Frage: Chomsky & reguläre Sprache

Hi,

ich soll nach der Chomsky-Hierarchie bestimmen, welchen Typ eine Grammatik hat. Allerdings ist mir nicht ganz klar, wie das geht (ein totaler Anfänger ist ;_;").
Also, ich bestimme ja erst einmal die Typen der einzelnen Regeln der Grammatik, oder?
Wenn dann auch nur eine Regel z.B. Typ 2 ist, dann ist die komplette Grammatik Typ 2, auch wenn die anderen Regeln nur Typ 0 oder Typ 1 haben?
Habe ich das richtig verstanden? Oder ist es genau anders rum?

Und dann habe ich noch eine Frage zu den regulären Sprachen: Woran erkennt man, dass ein Sprachschatz regulär ist?

Ich hoffe, ihr könnt mir weiterhelfen ^^

lg schabernack
Annihilator
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 18.05.2007
Beiträge: 6394
Wohnort: (hier nicht mehr aktiv)

BeitragVerfasst am: 08 Jan 2009 - 20:39:39    Titel:

In der Regel möchte man das größtmögliche n finden, sodass die Grammatik Typ n hat. Wenn eine Grammatik also beispielsweise kontextfrei ist, dann hat ist zwar vom Typ 0 und vom Typ 1, aber die speziellste Form ist Typ 2. Mögliches Vorgehen: Du nimmst an, die Grammatik sei vom Typ 3. Wenn du anhand der Produktionen siehst, dass das nicht stimmen kann, dann nimmst du an, sie sei vom Typ 2 und so weiter.

Zum Nachweis, dass eine Sprache regulär (also vom Typ 3) ist, kannst du zum einen versuchen, eine Typ3-Grammatik dafür zu finden oder zum anderen einen DEA bzw. NEA angeben, der eben jene Sprache akzeptiert.
Schabernack
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 08.01.2009
Beiträge: 5

BeitragVerfasst am: 08 Jan 2009 - 21:23:00    Titel:

Zitat:
Mögliches Vorgehen: Du nimmst an, die Grammatik sei vom Typ 3. Wenn du anhand der Produktionen siehst, dass das nicht stimmen kann, dann nimmst du an, sie sei vom Typ 2 und so weiter.

Ah, okay. Also praktisch: Wenn eine Regel vom Typ 3 ist, dann ist die Grammatik typ 3. Wenn nicht, dann guck ich, ob eine Regel vom Typ 2 ist -> wenn ja dann ist die Grammatik eben typ 2. ...usw usw.
Hab ich das richtig verstanden? oder muss ich auf noch mehr achten bzw. wie ist das mit der "speziellsten Form" gemeint? (Entschuldige meine Begriffsstutzigkeit, aber ich bin echt neu *sigh*)

http://infb05.in.funpic.de/SS06/FSA/Uebungsblatt%209%20SS06.pdf
z.b. hier bei 4a) da wäre dann die ganze Grammatik vom Typ 3, weil die 4. Regel vom Typ 3 ist, oder?

Zitat:
Zum Nachweis, dass eine Sprache regulär (also vom Typ 3) ist, kannst du zum einen versuchen, eine Typ3-Grammatik dafür zu finden oder zum anderen einen DEA bzw. NEA angeben, der eben jene Sprache akzeptiert.

Hm, kay. Ich werde es dann mal mit einer Grammatik versuchen, da wir DEA und NEA wohl erst in der nächsten Vorlesung haben ^^“

Danke, das hat mir schonmal weitergeholfen ^^
Annihilator
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 18.05.2007
Beiträge: 6394
Wohnort: (hier nicht mehr aktiv)

BeitragVerfasst am: 08 Jan 2009 - 21:37:25    Titel:

Es müssen alle Produktionen die Form "A --> wB" (für rechtslineare Grammatik) haben, damit die Grammatik vom Typ 3 ist. Sobald eine Produktion nicht diese Form hat, dann ist die Grammatik nicht vom Typ 3. Was dich vermutlich etwas verwirrt, sind die Zahlen 0 bis 3. Viele sind der Ansicht, das es logischer wäre, sie genau in umgekehrter Reihenfolge zu benutzen, aber Chomsky hat sich schon was dabei gedacht. Denk dir einfach folgendes: Je größer die Zahl ist, desto spezieller wird die Grammatik. Je spezieller etwas ist, desto weniger Dinge sind enthalten.
Schabernack
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 08.01.2009
Beiträge: 5

BeitragVerfasst am: 08 Jan 2009 - 21:48:06    Titel:

Ach soo, okay. Ich glaub, dann hab ich das die ganze Zeit genau verkehrt herum gemacht.
Also wenn jetzt z.B eine Regel von Typ 3 ist und alle übrigen vom Typ 2, dann wäre die Grammatik Typ 2, nicht wahr?

Danke, ich glaub, jetzt hab ich’s verstanden. Very Happy
Annihilator
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 18.05.2007
Beiträge: 6394
Wohnort: (hier nicht mehr aktiv)

BeitragVerfasst am: 08 Jan 2009 - 22:01:12    Titel:

Schabernack hat folgendes geschrieben:
Ach soo, okay. Ich glaub, dann hab ich das die ganze Zeit genau verkehrt herum gemacht.
Also wenn jetzt z.B eine Regel von Typ 3 ist und alle übrigen vom Typ 2, dann wäre die Grammatik Typ 2, nicht wahr?

Ja richtig. Aber bitte sei vorsichtig mit einer Formulierung wie "Regel vom Typ 2"! Den Typ kannst du nur einer Grammatik zuweisen, nicht aber einer Produktion. Mir ist zwar klar, was du meinst, aber es könnte sein, dass das mancher Dozent nicht gern hört.

Noch eine Möglichkeit nachzuweisen, dass eine gegebene Sprache regulär ist: "Einfach" einen regulären Ausdruck dafür finden.
Armin Gibbs
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 06.02.2008
Beiträge: 992

BeitragVerfasst am: 08 Jan 2009 - 22:18:05    Titel:

Wenn ich das Übungsblatt (optisch) sehe, vergeht mir schon der Spaß.
Schabernack
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 08.01.2009
Beiträge: 5

BeitragVerfasst am: 10 Jan 2009 - 16:02:21    Titel:

Zitat:
Ja richtig. Aber bitte sei vorsichtig mit einer Formulierung wie "Regel vom Typ 2"! Den Typ kannst du nur einer Grammatik zuweisen, nicht aber einer Produktion. Mir ist zwar klar, was du meinst, aber es könnte sein, dass das mancher Dozent nicht gern hört.


Oh, okay. Danke für den Hinweis.

Zitat:
Noch eine Möglichkeit nachzuweisen, dass eine gegebene Sprache regulär ist: "Einfach" einen regulären Ausdruck dafür finden.


DAS ist natürlich auch eine Möglichkeit. Danke.

Zitat:
Wenn ich das Übungsblatt (optisch) sehe, vergeht mir schon der Spaß.


? Den Studenten der FH Brandenburg sicher auch. ;P
Armin Gibbs
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 06.02.2008
Beiträge: 992

BeitragVerfasst am: 10 Jan 2009 - 16:27:46    Titel:

Zitat:
Noch eine Möglichkeit nachzuweisen, dass eine gegebene Sprache regulär ist: "Einfach" einen regulären Ausdruck dafür finden.


UND beweisen, dass die von dem Ausdruck erzeugte Sprache tatsächlich die Gesuchte ist. Dasselbe gilt natürlich auch für Automatenkonstruktionen etc.
Schabernack
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 08.01.2009
Beiträge: 5

BeitragVerfasst am: 14 Jan 2009 - 16:30:11    Titel:

So, Aufgaben abgegeben. Vielen, vielen Dank für die Hilfe. Very Happy
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Informatik-Forum -> Frage: Chomsky & reguläre Sprache
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