P - Universität Wien

 Grammatik

 59 views
of 19
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Description
Kapitel 4:Die Chomsky Hierarchie Sprachen, Grammatiken, Automaten Peter Brezany Institut für Softwarewissenschaft Universität Wien, Liechtensteinstraße 22…
Share
Transcript
Kapitel 4:Die Chomsky Hierarchie Sprachen, Grammatiken, Automaten Peter Brezany Institut für Softwarewissenschaft Universität Wien, Liechtensteinstraße 22 1090 Wien Tel. : 01/4277 38825 E-mail : brezany@par.univie.ac.at Sprechstunde: Dienstag, 11.30-12.30 1 P.Brezany Institut für Softwarewissenschaft – Universität Wien Kapitel 4: Die Chomsky Hierarchie Sei  ein beliebiges Alphabet. Eine Sprache haben wir als beliebige Teilmenge L  * definiert. Wie lassen sich nun formale Sprachen präzise definieren? - Vier Methoden sind denkbar: 1. Auflistung/Aufzählung aller Sprachelemente - Die explizite Auflistung aller Sprachelemente ist nur für endliche Sprachen (mit relativ wenigen Elementen) möglich und daher für die meisten in der Praxis interessanten Sprachen irrelevant. - Die Aufzählung aller Sprachelemente basiert auf der Benutzung einer berechenbaren Funktion, deren Wertebereich gleich L ist. Bemerkung: Eine Funktion, die sich durch ein Programm realisieren läßt, heißt berechenbar. 2 P.Brezany Institut für Softwarewissenschaft – Universität Wien 2. Spezifikation eines formalen Ausdrucks Ein Beispiel für diese Methode sind reguläre Ausdrücke, die beliebige reguläre Sprachen beschreiben können. Zum Beispiel kann man die Menge der Bezeichner einer Programmiersprache durch L = B(B+Z)* darstellen, wenn B die Menge der Buchstaben und Z die Menge der Ziffern repräsentiert. Diese Methode hat allerdings begrenzte Mächtigkeit und ist nicht allgemein auf Sprachklassen mit höherer Mächtigkeit anwendbar. 3. Grammatiken Grammatiken lassen sich zur (rekursiven) Erzeugung der Sätze einer Sprache benutzen. 4. Automaten Automaten lassen sich zur Erkennung der Sätze einer Sprache verwenden. 3 P.Brezany Institut für Softwarewissenschaft – Universität Wien Die beiden zuletzt genannten Methoden haben für die Praxis die größte Bedeutung. Die Chomsky Hierarchie (nach Noam Chomsky) legt eine Hierarchie von vier Sprachklassen - Chomsky-Typ 0 bis Chomsky-Typ 3 - fest und formalisiert die Beziehung der zugehörigen Grammatik- und Automatenklassen. 4 P.Brezany Institut für Softwarewissenschaft – Universität Wien Erzeugung und Erkennung von Sprachen • Erzeugung von Sprachen Die Erzeugung einer Sprache wird durch eine Grammatik spezifiziert. Grammatiken lassen sich als spezielle Semi-Thue Systeme auffassen: Es wird ein Verfahren angegeben, das aus einem Axiom (Startsymbol) und einer Menge von Regeln (Produktionen) systematisch alle Sätze einer Sprache generiert. Semi-Thue-Systeme (STS) - Ein STS ist eine nichtleere, endliche Relation R  E* x E* auf dem Alphabet E. - Die Tupel der Relation nennt man Regeln oder Produktionen. - Es werden Wörtern Zeichenketten durch andere Zeichenketten ersetzt. Beispiel für ein STS: E = {a,b,c,d,e}, R  E* x E = { (ab, ad), (dc, ee), (e, b), (ad, ae), (eb, b), (abc, e) } oder in Regelschreibweise: ab  ad dc  ee e  b ad  ae eb  b abc  e 5 P.Brezany Institut für Softwarewissenschaft – Universität Wien Beispiel für ein STS (Fortsetzung): Sei gegeben v = abc, w = aeb, so kann gezeigt werden, dass sich mit Hilfe des oben angegebenen Semi-Thue-Systems w aus v ableiten läßt. v = abc  adc  aee  aeb = w also gilt: v (*) w Für Semi-Thue-Systeme hat sich gezeigt, dass es kein allgemeines Verfahren gibt, mit dem man für beliebige Wortpaare v und w entscheiden kann, ob v (*) w gilt oder nicht. Daher wurden von einem amerikanischen Linquisten Noam Chomsky Modifikationen an den allgemeinen Semi-Thue-Systemen vorgenommen, durch die man Sprachkla- ssen erhält, die entscheidbar sind. 6 P.Brezany Institut für Softwarewissenschaft – Universität Wien • Erkennung von Sprachen Sei L  *. Wir definieren zwei Typen von Erkennungsverfahren. - Entscheidbarkeit Es wird ein Verfahren spezifiziert, das für jedes Wort w  * entscheidet, ob w  L oder nicht w  L. - Semi-Entscheidbarkeit Es wird ein Verfahren spezifiert, das für jedes Wort w  * entscheidet, ob w  L. 7 P.Brezany Institut für Softwarewissenschaft – Universität Wien Entscheidbarkeit eines Problems  JA! algorithmischer Test I hat die Eigenschaft Instanz I auf die P problem-spezifische Eigenschaft P NEIN! I hat die Eigenschaft P nicht. Semi-Entscheidbarkeit eines Problems  „Hat die Eigenschaft P!“ algorithmischer Test falls I die Eigenschaft Instanz I auf die P hat. problem-spezifische Eigenschaft P Ist nicht definiert (z.B. hält nicht an), falls die Eigenschaft P nicht hat. 8 P.Brezany Institut für Softwarewissenschaft – Universität Wien Typ-0 Grammatiken Definition: Eine Typ-0 Grammatik ist ein Quadrupel G = ( N, , P, S ) wobei N,  und S die gleiche Bedeutung wie bei KFG haben und wir das Gesamtalphabet ebenfalls mit  bezeichnen. Für die Menge der Regeln, P, gilt: P  *N* x *, endlich  Regeln einer Typ-0 Grammatik sind also von der Form   , wobei  und  Worte über dem Gesamtalphabet sind, mit der zusätzlichen Bedingung, dass  mindestens ein Nichtterminalzeichen enthält. Wie bei KFG lassen sich Regeln als Vorschriften für Textersetzungen in Worten aus * interpretieren, wobei allerdings Teilworte (die als linke Seite einer Regel auftreten) und nicht nur (wie bei KFG) einzelne Nichttermi- nalsymbole ersetzt werden können. 9 P.Brezany Institut für Softwarewissenschaft – Universität Wien Auf dieser Grundlage läßt sich wie bei KFG auf der Basis von P eine Ableitungsrelation  in * definieren und in völlig analoger Weise die von der Grammatik erzeugte Sprache, L(G), definieren. Eine Sprache, die von einer Typ-0 Grammatik erzeugt wird, heißt Typ-0 Sprache. 10 P.Brezany Institut für Softwarewissenschaft – Universität Wien Beispiel: Eine Typ-0 Grammatik, die { ai | i ist eine positive Potenz von 2 } erzeugt, ist im folgenden gegeben: 1) S  ACaB 5) aD  Da 2) Ca  aaC 6) AD  AC 3) CB  DB 7) aE  Ea 4) CB  E 8) AE   A und B dienen als linke und rechte Markierungen des Endes der Satzformen; C ist eine Markierung, die durch aus a bestehenden Zeichenketten zwischen dem A und B läuft und dabei deren Anzahl durch Produktion (2) verdoppelt. S 1 ACaB 2 AaaCB 4 AaaE 7 AaEa 7 AEaa 8 aa oder S 1 ACaB 2 AaaCB 3 AaaDB 5 AaDaB 5 ADaaB 6 ACaaB  ... 11 P.Brezany Institut für Softwarewissenschaft – Universität Wien Kontextsensitive (Typ-1) Grammatiken Definition: Eine Typ-0 Grammatik heißt kontextsensitiv (KSG) oder Typ-1 Grammatik, falls jede Regel in P eine der folgenden beiden Formen besitzt: Entweder 1B2  12 wobei B  N, 1, 2  * und   + oder S   und S tritt nicht auf der rechten Seite von Regeln auf.  12 P.Brezany Institut für Softwarewissenschaft – Universität Wien Beispiel – Kontextsensitive Sprache Die Sprache L = {anbncn | n>0} ist kontextsensitiv. P: S  abc S  aXbc Xb  bX Xc  Ybcc bY  Yb aY  aa aY  aaX G = ({S, X, Y}, {a, b, c}, P, S) 13 P.Brezany Institut für Softwarewissenschaft – Universität Wien Beispiel: Kontextfreie Grammatik: G = ( {S}, {0, 1}, P, S ) P = { S  0S1, S   } L(G) = { 0n1n | n  1 } Aufgabe: Was für eine Sprache wird durch die folgende Typ-0 Grammatik generiert: S  S1B S1  aS1b bB  bbbB aS1b  aa B   14 P.Brezany Institut für Softwarewissenschaft – Universität Wien Zusammenfassung: Die Grammatiken der Chomsky Hierarchie Eine Chomsky Grammatik hat die Form G = (N, , P, S), wo N und  die Alphabete der Nichtterminal- bzw Terminalsymbole darstellen, P die Regelmenge ist und S  N das ausgezeichnete Symbol darstellt. Die einzelnen Grammatikklassen werden durch die Form ihrer Regeln unterschieden: • Typ-0 (unbeschränkte):    mit   *N* und   *. • Typ-1 (kontextsensitive): 1B2  12, mit B  N, 1, 2  * und   + oder S   und S tritt nicht auf der rechten Seite von Regeln auf. • Typ-2 (kontextfrei): A   mit A  N,   * • Typ-3 (reguläre): - rechtslinear: A  x oder A  xB, mit A, B  N und x  *. - linkslinear: A  x oder A  Bx, mit A, B  N und x  *. 15 P.Brezany Institut für Softwarewissenschaft – Universität Wien Chomsky Hierarchie: Sprachklassen,Automaten, und Hierarchiesatz Den vier Grammatik- und Sprachklassen der Chomsky Hierarchie entsprechen vier Klassen von Automaten. Die Automaten des Typs i (0  i  3) erkennen genau die von Chomsky Typ-i Grammatiken generierten Sprachen. Diese Automatenklassen werden wie folgt bezeichnet: Typ-0: Turingmaschinen Typ-1: Linear beschränkte Automaten Typ-2: Kellerautomaten (Stackautomaten) Typ-3: Endliche Automaten 16 P.Brezany Institut für Softwarewissenschaft – Universität Wien Hierarchiesatz: Bezeichne Li, 0  i  3, die Familie der Chomsky Typ-i Sprachen. Dann gilt L3  L2  L1  L0 wobei alle Inklusionen echte Teilmengenbeziehungen repräsentieren.  17 P.Brezany Institut für Softwarewissenschaft – Universität Wien Bemerkungen zur Hierarchieeigenschaft • Die Grammatiken bilden keine Hierarchie: Eine kontextfreie Grammatik braucht nicht kontextsensitiv zu sein. Jedoch läßt sich für jede kontextfreie Grammatik eine dazu äquivalente kontextsensitive Grammatik konstruieren. • Die Sprache { anbn | n  1 } ist kontextfrei, aber nicht regulär. • Die Sprache { anbncn | n  1 } ist kontextsensitiv, aber nicht kontextfrei. Aufgabe: Finden Sie eine kontextsensitive Grammatik, die L = { anbncn | n  1 } generiert. 18 P.Brezany Institut für Softwarewissenschaft – Universität Wien Äquivalenz und Wortproblem Definition: Zwei Typ-0 Grammatiken G und G´ heißen äquivalent genau dann, wenn L(G) = L(G´). Definition: Gegeben sei eine Sprache L  *. Wir betrachten das folgende Problem: Gibt es ein Verfahren, das für ein beliebiges w  * entscheidet, ob w  L oder nicht w  L? Man nennt dies das Wortproblem für L. Bemerkung: • Für Typ-0 Sprachen ist das Wortproblem im allgemeinen nicht entscheidbar. • Für Typ-i Sprachen mit i  1 ist das Wortproblem entscheidbar. 19 P.Brezany Institut für Softwarewissenschaft – Universität Wien
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks