Gegeben seien die Grammatik ´G = ({S, A, B, C}, {a, b}, P, S)´ mit

´P = {´ ´S -> A B´, ´S -> B C´, ´A -> B A´, ´A -> a´, ´B -> C C´, ´B -> b´, ´C -> AB´, ´C -> a´ }´

  1. Stelle mittels des Cocke-Younger-Kasami-Algorithmus fest, welche der folgenden Wörter in ´L(G)´ liegen:

    1. ´w_1 = "abbba"´
    2. ´w_2 = "baaba"´
    3. ´w_3 = "bbbaaa"´

  2. Untersuche ob ´L(G)´ endlich oder unendlich ist.

Approach

"Teil 1\n\nMan erhält für die drei Wörter nach dem CYK-Algorithmus die folgenden Tabellen:\n\n´{A,C}´ | ´{S,C}´ | ´O/ ´ | ´O/ ´ | ´O/ ´\n:-:|:-:|:-:|:-:|:-:\n´a´ | ´{B}´ | ´O/ ´ | ´O/ ´ | ´{A}´\n | ´b´ | ´{B}´ | ´O/ ´ | ´{A}´\n | | ´b´ | ´{B}´ | ´{S, A}´\n | | | ´b´ | ´{A,C}´\n | | | | ´a´\n \n´{B}´ | ´{S, A}´ | ´O/ ´ | ´O/ ´ | ´{S, A, C}´\n:-:|:-:|:-:|:-:|:-:\n´b´ | ´{A,C}´ | ´{B}´ | ´{B}´ | ´{S, A, C}´\n | ´a´ | ´{A,C}´ | ´{S,C}´ | ´{B}´\n | | ´a´ | ´{B}´ | ´{S, A}´\n | | | ´b´ | ´{A,C}´\n | | | | ´a´\n \n´{B}´ | ´O/ ´ | ´O/ ´ | ´{A}´ | ´O/ ´ | ´{S, A, C}´\n:-:|:-:|:-:|:-:|:-:|:-:\n´b´ | ´{B}´ | ´O/ ´ | ´{A}´ | ´O/ ´ | ´{S, A, C}´\n | ´b´ | ´{B}´ | ´{S, A}´ | ´O/ ´ | ´{S, A, C}´\n | | ´b´ | ´{A,C}´ | ´{B}´ | ´{S, A, C}´\n | | | ´a´ | ´{A,C}´ | ´{B}´\n | | | | ´a´ | ´{A,C}´\n | | | | | ´a´\n\n\nDamit ist ´w_1 !in L(G)´, aber ´w_2, w_3 in L(G)´.\n\n\nTeil 2\n\nDa die gegebene Grammatik in Chomsky-Normalform ist und es zu jedem Nichtterminal ´X´ aus ´{A,B,C}´ ein ableitbares Wort gibt, in dem ´X´ vorkommt, und zu jedem ´X´ eine terminierende Ableitung existiert, haben wir nur zu sehen, ob es in dem Graphen\n\nS -> A\nS -> B\nS -> C\nA -> A\nA -> B\nC -> A\nC -> B\nB -> C\n\neinen Kreis gibt. Dies ist sofort zu sehen und folglich ist L(G) unendlich.\n\nLösung ohne diesen Algorithmus:\nEs gibt für jedes ´n >= 1´ die Ableitung\n\n´S => AB => BAB => BBAB => … => B^nAB =>^(\\) b^nab´.\n\nDamit enthält ´L(G)´ die unendliche Menge ´{b^nab | n >= 1}´, womit ´L(G)´ unendlich ist."


Solutions

  • Teil 1

    ´w_1 !in L(G)´ und ´w_2, w_3 in L(G)´

    Teil 2

    Da die gegebene Grammatik in Chomsky-Normalform ist und es zu jedem Nichtterminal ´X´ aus ´{A,B,C}´ ein ableitbares Wort gibt, in dem ´X´ vorkommt, und zu jedem ´X´ eine terminierende Ableitung existiert, haben wir nur zu sehen, ob es in dem Graphen

    S -> A S -> B S -> C A -> A A -> B C -> A C -> B B -> C

    einen Kreis gibt. Dies ist sofort zu sehen und folglich ist L(G) unendlich.

  • Teil 2

    Es gibt für jedes ´n >= 1´ die Ableitung

    ´S => AB => BAB => BBAB => … => B^nAB =>^(**) b^nab´.

    Damit enthält ´L(G)´ die unendliche Menge ´{b^nab | n >= 1}´, womit ´L(G)´ unendlich ist.

  • URL:
  • Language: Deutsch
  • Subjects: theoretical computer science
  • Type: Assign
  • Duration: 40min
  • Credits: 6
  • Difficulty: 0.6
  • Tags: hpi cyk algorithm
  • Note:
    HPI, 2014-05-20, Theoretische Informatik 2, Blatt 7, Aufgabe 1
  • Created By: ad-si
  • Created At:
    2014-07-25 07:57:11 UTC
  • Last Modified:
    2014-07-25 07:57:11 UTC