Artikel pedia
| Home | Kontakt | Artikel einreichen | Oberseite 50 artikel | Oberseite 50 autors
 
 


Artikel kategorien
Letztes fugte hinzu
    Ms-access

   Instrumentation + schnittstellen

   Pc tuning - volle kraft voraus für ihr system

   Informatorische grundlagen

   Javascript

   Interne sortieralgorithmen - der kern der sache

   Plotter und sonstige drucker

   Frage 20 (rössl priska)

   Internet - programmierung

   Monitore

   Semesterarbeit und spezialgebiet für informatik

   Erörterungs zum thema

   Inhaltsverzeichnis

   Einführung in die entwicklung ganzheitlicher informationssysteme:

   Titel dokument
alle kategorien




  Chomsky hierarchie



Kurzreferat zu Sprachen und Gramatiken in Bezug auf Unterteilung in Typen       1. Grammatik und Sprache -         Notation -         Definition Grammatik -         Bestandteildefinition -         Definition Formale Sprache -         Definition Aufzählbare Sprachen -         Definition Entscheibare Sprachen -         Definition Reguläre Sprachen   2. Typ-0-Sprachen -         Typ-0-Grammatik -         Beispiel -         Turingmaschine   3. Typ-1-Sprachen -         kontextsensitive Grammatik -         Beispiel -         linear beschränkter Automat   4. Typ-2-Sprachen -         kontextfreie Grammatik -         Beispiel -         Kellerautomaten   5. Typ-3-Sprachen -         Reguläre Grammatik -         Beispiel -         endlicher Automat     1.

Grammatik und Sprache   1.1 Notation: Nichtterminalsymbole werden in Backus-Naur-Form, in spitzen Klammern < >, gesetzt. Der Pfeil ® einer Produktionsregel wird durch das Zeichen ::= dargestellt. Alternativen werden durch einen senkrechten Strich ½ getrennt. Geschwungene Klammern {} bedeuten Wiederholungen und eckige Klammern [] umschließen optionale Teile.       1.

2 Definition Grammatik:             Eine Grammatik G=(T,N,P,S) ist ein Viertupel mit:             .     T endliche Menge der terminalen Symbole             .     N endliche Menge der nichtterminalen Symbole, T Ç N = Ø             .     P Produktionssystem mit endlich vielen Produktionsregeln             .     S 0 N, Startsymbol   1.3 Bestandteildefinition: Terminale T:                 Das Alphabet der Sprache. Terminalsymbole sind Zeichen oder Wörter, die nicht mehr weiter zerlegt werden können und mit denen jeder Satz einer Sprache formuliert wird.                         Tdeutsch = {a, ...

z, A, ...Z, der, die , das, Professor, Studentin, ...

}                         T*: Menge aller Wörter, die durch die Hintereinanderreihung endlich vieler Terminalsymbole einschließlich des leeren Wortes e, erzeugt werden können   Nichtterminale N:          Hilfssymbole, mit deren Hilfe die Grammatikregeln formuliert werden können. Jedes   nichtterminale Symbol entspricht einer Variablen und läßt sich in eine Folge anderer nichtterminaler und terminaler Symbole umschreiben. Ndeutsch = {<Satz>, <Subjekt>, <Prädikat>, <Objekt>, <Artikel>,                                                                                                                                                                                                                                                                                                 <Substantiv>, <Verb>, <Attribut>, ...}                                    Äquivalent zu T* wird N* definiert.




  Produktionen P:            enthält Regeln zur Konstruktion von Zeichenketten der Sprache und legen fest, wie ein nichtterminales Symbol weiter ersetzt werden kann. Sie werden meistens in der Notation u ® v angegeben. Es gilt: u,v 0 (T È N)* Damit eine solche Regel anwendbar ist, muß u mindestens ein Nichtterminalsymbol enthalten. <Satz> ® <Subjekt> <Prädikat> <Objekt>. Das bedeutet, daß ein Satz aus einem Subjekt, einem Prädikat, einem Objekt und einem Punkt an dessen Ende besteht.   Startsymbol S:              Ein Startsymbol S ist ein ausgezeichnetes nichtterminales Symbol mit dem jede Anwendung von Produktionsregeln beginnt.

Beispielsweise ist für die deutsche Sprache das nichtterminale Symbol "Satz" ein Startsymbol.   1.4 Definition Formale Sprache (allgem. Sprache) Die von der Grammatik G erzeugte formale Sprache L(G) wird definiert durch die Menge aller Wörter w, die nur aus Terminalsymbolen bestehen und die alle aus dem Startsymbol S ableitbar sind. (Übersichten zum Gesamtverständnis der Sprachen, Automaten, Grammatiken  und ihrer Zusammenhänge finden sie in den Anlagen)   1.5 Definition Aufzählbare Sprachen Eine Sprache L(G) heißt aufzählbar, wenn es einen Algorithmus gibt, der alle Wörter w dieser Sprache nacheinander erzeugen kann.

Dazu gehören: -         Typ-0-Sprachen -         Sprachen die von Turingmaschinen mit eingeschränktem Eingabeband akzeptiert werden   1.6 Definition Entscheidbar Sprachen Eine Sprache L(G) über einer Mnege von Terminalsymbolen T, L(G) Í T* , heißt entscheidbar, wenn es eien Algorithmus gibt, der nach endlich vielen Schritten feststellt, ob für jedes w  Í T* gilt, daß entweder w  Î L(G) oder w Ï L(G) zutrifft. -         bilden echte Teilmengen der aufzählbaren Sprachen -         sind echte Obermenge der kontextsensitiven Sprachen -         werden durch Kellerautokaten erkannt. Dies sind endliche Automaten, die um eine Keller erweitert werden, um bereits erkannte Zeichen zu speichern   2. Typ-0-Sprachen Dies sind Sprachen mit einer Typ-0-Grammatik.   2.

1 Typ-0-Grammatik Dies ist eine Grammatik ohne Einschränkungen.             "u ® v aus P gilt: u Î (T È N)+ = (T È N)* {e}, v Î (T È N)* Die beiden damit verknüpften Forderungen sind die, daß auf der linken Seite mindestens ein Nichtterminalsymbol stehen muß und u nicht das leere Wort e ist.   2.2 Beispiel Die folgende Grammatik erzeugt die Sprache L(G)={ai ½ mit i als positive Zweierpotenz} G=(T, N, P, S) G=({S, A, B, C, D, E},{a}, P, S) P={S ® ACaB, aD ® Da, Ca ® aaC, AD ® AC, CB ® DB, aE ® Ea, CB ® E, AE ® e} Bsp.: S ® ACaB ® AaaCB ® AaaE ® aa(e) = aa   2.3 Turingmaschine Eine Turingmaschine akzeptiert Sprachen die nach einer Typ-0-Grammatik gebildet werden.

Eine Turingmaschine ist ein 7-Tupel T = (X,B,Z,d,b,z0,ZE), wobei gilt: -         X ist eine nichtleere, endliche Menge, das Eingabealphabet, -         B Ê X ist eine nichtleere, endliche Menge, das Bandalphabet, -         Z ist eine nichtleere, endliche Menge, die Zustandsmenge, -         d: (ZZE) x B ® B x {L,N,R} x Z ist eine Funktion, die Überführungsfunktion, welche jedem Paar(Zustand, gelesenen Zeichen) ein Tripel (zu schreibendes Zeichen, Kopfbewegung, Folgezustand) zuordnet, -         b Î BX ist das Leerzeichen oder Blank, -         z0 Î Z ist der Anfangszustand, -         ZE Í Z ist die Endzustandsmenge   3. Typ-1-Sprachen Dies sind Sprachen mit einer Typ-1-Grammatik.   3.1 kontextsensitive Grammatik Die Einschränkung besteht darin, daß auf der linken Seite der Produktion ein nichtterminales Symbol existieren muß, das nur unter Beibehaltung eines Kontextes, sofern ein solcher vorhanden ist, ersetzt werden darf: "x ® y aus P, $ A Î N und w1, w2, v Î (T È N)* mit v ¹ e, so daß aus x = w1Aw2 folgt y=w1vw2 Dies bedeutet, daß A nur im Kontext w1...



w2 durch v ersetzt werden darf.   3.2 Beispiel Hierbei entsteht aus der nun folgenden Gramatik die Sprache L(G)={si,ti,ui}mit i Î N G = {T, N, P, S) T = {S, A, B} N = {s, t, u} S = S P = {S ® sAtu½stu, A ® sAtB½stB, Bt ® tB, Bu ® uu} Bsp.: S ® stu S ® sAtu ® sstBtu ® ssttBu ® ssttuu S ® sAtu ® ssAtBtu ® sAttBu ® ssAttuu ® ssstBttuu ® sssttBtuu ® ssstttuuu   3.3 Linear beschränkter Automat Linear beschränkte Automaten nutzen Typ-1-Sprachen.   Definition:         Eine Struktur B = (X, Y, Z, h, z0, F, [, ] ) heißt linear beschränkter Automat,       wenn: -          (X, Y, Z, h, z0, F) ein (nichtdeterministischer) Turing-Automat (ohne Blank), -          [ , ] Î Y ( X ÈZ ) (linke bzw.

rechte Randmarke) und -          aus (y´, z´, o) h Î (y, z) folgt y´ = [ bzw. ] genau dann, wenn y = [ bzw. ]und aus y = [ bzw ] folgt o ¹ l bzw. r . (Die Randmarken dürfen wedergeschrieben, verändert, noch überschritten werden. 4.

Typ-2-Sprachen Dies sind Sprachen mit einer Typ-2-Grammatik.   4.1 kontextfreie Grammatik Für die Regeln aus P wird jetzt noch restriktiver gefordert, daß auf der linken Seite genau ein Nichtterminal stehen muß:             "u ® v aus P gilt: u Î N und  v Î (T È N)* mit v ¹ e Mit kontextfreien Grammatiken kann z.B. die Syntax von Programmiersprachen, wie Turbo Pascal (mein Liebling), festgelegt werden.   Zulässig: A ® aBa, A ® abBCa Verboten: aBc ® abBCc (diese wäre kontextsensitiv!)   4.

2 Beispiel G = (T, N, P, S) T = {S, A, T, R} N = {(, ), +, -, *, /, a, b, c, d, , e} S = S P = { S ® A, A ® T½+T½-T½A+T½A-T, T ® P½T*P½T/P, P ® (A) ½a½b½c½d½e} Bsp.: S ® A ® A+T ® T+P ® P+a ® b+a   4.3 Kellerautomat Kellerautomaten nutzen kontextfreie Sprachen. Definition: Eine Struktur K = ( X, Y, Z, h, z0, S, F ) heißt (endlicher) Kellerautomat, wenn -         X (Eingabealphabet), Y (Kelleralphabet), Z (Zustandsmenge) nichtleere endliche Mengen, -         z0 Î Z (Anfangszustand), S Î Y (Startsymbol), F Í Z (Endzustandsmenge), -         h eine Funktion aus ( X È {e} ) x Z x Y in die Menge aller endlichen Teilmengen von Z x Y*.   5. Typ-3-Sprachen Dies sind Sprachen, die durch Typ-3-Grammatiken definiert werden.

  5.1 Reguläre Grammatik   Dies ist eine kontextfreie Grammatik, die dadurch eingeschränkt wird, daß auf der rechten Seite jeder Regel neben terminalen Symbolen höchstens ein nichtterminales Symbol steht. Tritt auf der rechten Seite ein Nichtterminal auf, so muß es für alle Produktionsregeln einheitlich nur ganz rechts oder nur ganz links stehen:               "u ® v aus P gilt: u Î N und  v Î T* o N oder v Î T* (v ¹ e) (rechtslinear)             "u ® v aus P gilt: u Î N und  v Î N o T* oder v Î T* (v ¹ e) (linkslinear)   Dabei bedeutet o das Konkatenationszeichen. Das bislang verwendete Verbundzeichen È kann nicht eingesetzt werden, da es hier auf die genaue Reihenfolge ankommt und der Verbund von Mengen kommutativ ist.   Zulässig: A ® aaB, B ® b Verboten: A ® aBa, C ® e   5.2 Beispiel G = (T, N, P, S) T = {X0, X1} N = {a, b}, S= X0 P= {X0 ® X0b, X0 ® X1b, X1 ® X1a, X1 ® a} Die von G erzeugte Sprache ist L(G) = {aibk | i, k > 0} Bsp.



: X0 ® X0b ® X1bb ® X1abb ® aabb                         5.3 Endlicher Automat Endliche Automaten nutzen Sprachen des Typs 3. Definition: Ein endlicher Automat ist ein Sechstupel A = (I, O, Q, δ, q0, F), wobei -         I ist das Eingabealphabet (alle gültigen Eingabezeichen, die der Automat kennt), -         O ist das Ausgabealphabet (analog zu I), -         Q ist eine endliche, nichtleere Menge von Zuständen, -         q0 Î Q der Startzustand, -         δ: Q x I → Q x O die Zustandsübergangsfunktion mit einer Abbildung der Paare (q, i), wobei q Î Q ein Zustand ist und i Î I ein Eingabezeichen in ein Paar (q', o), wobei q' Î Q ein Folgezustand und o Î O ein Ausgabezeichen ist sowie -         F Í Q der Menge der Endzustände. Anmerkung: Die einzelnen hier aufgeführten Typen werden in den meisten Literaturquellen als Chomskytypen bezeichnet. Dies entspricht auch der Richtigkeit, jedoch habe ich hier aufgrund der Einfachheit das Chomsky weggelassen. Noch kurz zur Sprache in diesem Zusammenhang.

Eine Sprache L Í T* ist von Chomsky-Typ-i(i=0,1,2,3), falls eine Chomsky-Grammatik G von diesem Typ i existiert, die diese Sprache erzeugt L = L(G). Die gängigen Programmiersprachen sind alle kontextfreie Sprachen (der Wichtigkeit und Vollständigkeit halber noch einmal). Um bei der Vervollständigung zu bleiben. Die Vollständigkeit erlangt Chomsky-Lehre(Hierarchie), indem algorithmische Sprachklassen(Entscheidbarkeit) und die Klassen akzeptierender Automaten eingeordnet werden: -         aufzählbare Sprachen -         entscheidbare Sprachen -         reguläre Sprachen (siehe 1)                                                                                 Anlagen:   Sprach- und Automatenklassen  

Suchen artikel im kategorien
Schlüsselwort
  
Kategorien
  
  
   Zusammenfassung Der Vorleser

   sachtextanalyse

   interpretation zwist

   Fabel interpretation

   literarische charakteristik

   interpretation bender heimkehr

   felix lateinbuch

   interpretation der taucher von schiller

   textbeschreibung

   charakterisierung eduard selicke


Anmerkungen:

* Name:

* Email:

URL:


* Diskussion: (NO HTML)




| impressum | datenschutz

© Copyright Artikelpedia.com