Beispiele für Grammatiken
Results 1 to 2 of 2

Thread: Beispiele für Grammatiken

  1. #1
    Grinsekotze's Avatar
    Title
    Elite
    Join Date
    Oct 2009
    Location
    Krems
    Posts
    334
    Thanks
    192
    Thanked 13 Times in 11 Posts

    Beispiele für Grammatiken

    In den Skriptfolien auf Seite 122 stehen die Definitionen für verschiedene Arten von Grammatiken. Da die jedoch für Otto Normalinformatiker ziemlich unklar sind (inklusive der in den Folien enthaltenen Beispielen), wäre ich sehr dankbar, wenn jemand für jeden Grammatiktyp konkrete Beispiele mit einer Erklärung posten könnte.
    "Captain, the most elementary and valuable statement in science, the beginning of wisdom, is 'I do not know'. I do not know what that is, sir."
    -Ltd Cmdr Data, Star Trek - The Next Generation


    "Do you know what the big problem is in telling fantasy and reality apart?"
    "What?"
    "They're both ridiculous."
    -The Doctor, Doctor Who

  2. #2
    1student's Avatar
    Title
    Super Moderator
    Join Date
    Aug 2011
    Location
    Disneyland Vienna
    Posts
    1,506
    Thanks
    243
    Thanked 825 Times in 716 Posts
    Auf Folie 122 bezogen: Jede Produktion hat die Form α -> β. α steht jeweils für die linke Seite und β für die rechte Seite einer Produktion. Kleinbuchstaben stehen für Terminalsymbole und Großbuchstaben für Nonterminalsymbole. In den Definitionen darunter wird genauer erläutert wie α und β bzw. die Produktionen jeweils aussehen dürfen.

    Unbeschränkte Grammatiken sind alle Grammatiken G = <N, T, P, S>, unabhängig von der Form der Produktionen.

    *Für monotone Grammatiken gibt es die Einschränkung, dass |α| ≤ |β| gelten muss. Bei jeder Produktion müssen also die Anzahl der Elemente auf der linken Seite kleiner oder gleich der Anzahl der Elemente auf der rechten Seite sein. Die Produktionen A -> B oder A -> BB würden z.B. dieses Kriterium erfüllen, AA -> B würde es wiederum nicht erfüllen.

    *Für kontextsensitive Grammatiken gilt, dass jede Produktion die Form uAv -> uwv erfüllen muss, wobei u, v (N ∪ T)* und w (N ∪ T)+.
    u
    und v können jeweils aus beliebig vielen (oder auch keinen) Nonterminalsymbolen und Terminalsymbolen bestehen, während w aus zumindest einem Nonterminal oder Terminalsymbol bestehen muss. Die Produktionen A -> B oder aaA -> aaAb würden z.B. diese Definition erfüllen. aA -> B würde es wiederum nicht erfüllen.

    Kontextfreie Grammatiken sind jene, bei denen die linke Seite nur aus einem einzelnen Nonterminalsymbol besteht, während auf der rechten Seite beliebiges vorkommen kann. A -> bb wäre z.B. kontextfrei, Aa -> bb wiederum nicht.

    Reguläre Grammatiken haben Produktionen der Form A -> aB oder A -> ε.
    Links muss genau ein Nonterminalsymbol vorkommen und rechts ein Terminalsymbol gefolgt von einem Nonterminalsymbol, oder ε. Die Produktion C -> cD würde dies z.B. erfüllen, während C -> ccD dies nicht erfült.

    *Für reguläre Grammatiken gibt es auch eine zweite Definition (siehe Folie 124). Jede Produktion hat die Form A -> aB oder A -> a.
    Die Produktion C -> b wäre damit z.B. möglich, C -> bb wiederum nicht.

    Für alle mit * markierten Definitionen gilt außerdem, dass die Produktion S -> ε nur dann in der Grammatik erlaubt ist, wenn das Startsymbol S nicht auf der rechten Seite vorkommt.
    Last edited by 1student; 12-01-2017 at 01:42.
    "If you can dream it, you can do it."
    -- Walt Disney
    ʘ‿ʘ

  3. The Following 3 Users Say Thank You to 1student For This Useful Post:


Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •