Convertir la gramática a continuación en Forma Normal de Chomsky. Dar todos los pasos intermedios.

S -> AB | aB
A -> aab|lambda
B -> bbA

Ok, así que la primera cosa que hice fue agregar un nuevo comienzo de la variable S0

así que ahora tengo

S0 -> S
S -> AB | aB
A -> aab|lambda
B -> bbA

a continuación, he quitado todos los de la lambda reglas:

S0 -> S
S -> AB | aB | B
A -> aab
B -> bbA | bb

Luego me registré para S->S y A->B tipo de reglas que no existe. Y esa era la respuesta que se me ocurrió, ¿ necesito hacer algo más o hice algo mal?

La primera cosa a comprobar es, ¿la has leído Wikipedia?
La solicitud de aclaración: ¿Qué es la lambda? Es un símbolo terminal?
sí, ¿por qué? No tengo idea de lo de la última regla que está diciendo. Lambda es el Epsilon en wikipedia, se va a null
Regla #3 en la página de la Wikipedia dice que sólo el símbolo inicial se expanda a epsilon. Por lo que tendrá que lidiar con su A -> ... | lambda/epsilon.
……no voy a hacer?

OriginalEl autor tehman | 2011-09-19

3 Comentarios

  1. 20

    Wikipedia dice:

    En ciencias de la computación, una gramática independiente del contexto se dice que está en forma normal de Chomsky si todas sus reglas de producción son de la forma:

    • Un -> BC, o
    • Un -> α, o
    • S -> ε

    donde Un, B, C son no terminal símbolos, α es un símbolo terminal, S es el símbolo inicial, y ε es la cadena vacía. Asimismo, tampoco B ni C puede ser el símbolo inicial.

    Continuar su trabajo:

    S0 -> S
    S -> AB | aB | B
    A -> aab
    B -> bbA | bb
    

    Lugar de utilizar | para denotar diferentes opciones, dividir una regla en varias reglas.

    S0 -> S
    S -> AB
    S -> aB
    S -> B
    A -> aab
    B -> bbA
    B -> bb
    

    Crear nuevas reglas Y -> a y Z -> b porque vamos a necesitar pronto.

    S0 -> S
    S -> AB
    S -> aB
    S -> B
    A -> aab
    B -> bbA
    B -> bb
    Y -> a
    Z -> b
    

    S -> aB no es de la forma S -> BC porque a es una terminal. Por lo tanto, cambiar a en Y:

    S0 -> S
    S -> AB
    S -> YB
    S -> B
    A -> aab
    B -> bbA
    B -> bb
    Y -> a
    Z -> b
    

    Hacer lo mismo para el B -> bb regla:

    S0 -> S
    S -> AB
    S -> YB
    S -> B
    A -> aab
    B -> bbA
    B -> ZZ
    Y -> a
    Z -> b
    

    Para A -> aab, crear C -> YY; para B -> bbA, crear D -> ZZ:

    S0 -> S
    S -> AB
    S -> YB
    S -> B
    A -> CZ
    C -> YY
    B -> DA
    D -> ZZ
    B -> ZZ
    Y -> a
    Z -> b
    

    Para S -> B, duplicar la regla donde S se produce en el lado derecho y en línea de la regla:

    S0 -> B
    S0 -> S
    S -> AB
    S -> YB
    A -> CZ
    C -> YY
    B -> DA
    D -> ZZ
    B -> ZZ
    Y -> a
    Z -> b
    

    Acuerdo con las reglas S0 -> B y S0 -> S por unirse a la mano derecha a la mano izquierda lados de las demás normas. También, eliminar los huérfanos reglas (donde el LHS símbolo nunca se usa en RHS):

    S0 -> DA
    S0 -> ZZ
    S0 -> AB
    S0 -> YB
    A -> CZ
    C -> YY
    B -> DA
    D -> ZZ
    B -> ZZ
    Y -> a
    Z -> b
    

    Y hemos terminado. Ufff!

    entonces no tengo que deshacerse de la epsilon? Creo que el agregado de reglas sería S -> B y B-> H?
    wow excelente explicación, ¿te importaría ampliar un poco sobre lo que hizo durante los últimos dos cajas?

    OriginalEl autor Nayuki

  2. 5

    Sin entrar en demasiada teoría y pruebas(puede verse a este en la Wikipedia), hay algunas cosas que usted debe hacer cuando la conversión de un Contexto Libre de la Gramática en Forma Normal de Chomsky, que generalmente tienen que realizar cuatro Normales-Formulario de Transformaciones. En primer lugar, es necesario identificar todas las variables que pueden producir la cadena vacía(lambda/epsilon), directa o indirectamente (Lambda de forma Libre). En segundo lugar, usted necesita para eliminar unidad producciones – (Unidad de forma Libre). En tercer lugar, usted necesita encontrar todas las variables que están en directo/utilidad (Utilidad). Cuatro, usted necesita encontrar todas la accesible símbolos (Accesible). En cada paso se podría o no podría tener una nueva gramática. Así que para tu problema esto es lo que se me ocurrió…


    Gramática Independiente Del Contexto

    G(Variables = { A B S }
    Start = S 
    Alphabet = { a b lamda}
    
    Production Rules = { 
    S  ->  |  AB  |  aB  |  
    A  ->  |  aab  |  lamda  |  
    B  ->  |  bbA  |   } )
    

    Quitar lambda/epsilon

    ERRASABLE(G) = { A }
    
    G(Variables = { A S B }
    Start = S
    Alphabet = { a b }
    
    Production Rules = { 
    S  ->  |  AB  |  aB  |  B  | 
    B  ->  |  bbA  |  bb  |   } )
    

    Retire la unidad produtions

    UNIT(A) { A }
    UNIT(B) { B }
    UNIT(S) { B S }
    G (Variables = { A B S }
    Start = S 
    Alphabet = { a b }
    
    Production Rules = { 
    S  ->  |  AB  |  aB  |  bb  |  bbA  |  
    A  ->  |  aab  |  
    B  ->  |  bbA  |  bb  |   })
    

    Determinar vivo símbolos

    LIVE(G) = { b A B S a }
    
    G(Variables = { A B S }
    Start = S
    Alphabet = { a b }
    
    Production Rules = { 
    S  ->  |  AB  |  aB  |  bb  |  bbA  |  
    A  ->  |  aab  |  
    B  ->  |  bbA  |  bb  |   })
    

    Quitar inalcanzable

    REACHABLE (G) = { b A B S a }
    G(Variables = { A B S }
    Start = S 
    Alphabet = { a b }
    
    Production Rules = { 
    S  ->  |  AB  |  aB  |  bb  |  bbA  |  
    A  ->  |  aab  |  
    B  ->  |  bbA  |  bb  |   })
    

    Reemplazar todo mezclado cadenas con sólidos nonterminals

    G( Variables = { A S B R I }
    Start = S
    Alphabet = { a b }
    
    Production Rules = { 
    S  ->  |  AB  |  RB  |  II  |  IIA  |  
    A  ->  |  RRI  |  
    B  ->  |  IIA  |  II  |  
    R  ->  |  a  |  
    I  ->  |  b  |   })
    

    Chomsky Forma Normal

    G( Variables = { V A B S R L I Z }
    Start = S 
    Alphabet = { a b }
    
    Production Rules = { 
    S  ->  |  AB  |  RB  |  II  |  IV  |  
    A  ->  |  RL  |  
    B  ->  |  IZ  |  II  |  
    R  ->  |  a  |  
    I  ->  |  b  |  
    L  ->  |  RI  |  
    Z  ->  |  IA  |  
    V  ->  |  IA  |   })
    

    OriginalEl autor Maximino Gomez

  3. 1

    Alternativas respuesta: La gramática sólo puede producir un número finito de cadenas, es decir, 6.

     S -> aabbbaab | aabbb | bbaab | bb | abbaab | abb.
    

    Ahora se puede condensar esto al volver a la Forma Normal de Chomsky con la mano.


    Por sustitución, podemos encontrar el conjunto de todas las cadenas producidas. Su inicial reglas:

    S -> AB | aB.
    A -> aab | lambda.
    B -> bbA.
    

    Primera división hasta la S regla:

    S -> AB.
    S -> aB.
    

    Ahora sustituir lo que a y B a ampliar en:

    S -> AB
      -> (aab | lambda) bbA
      -> (aab | lambda) bb (aab | lambda).
    S -> aB
      -> abbA
      -> abb (aab | lambda).
    

    Ampliar estas de nuevo para obtener:

    S -> aabbbaab.
    S -> aabbb.
    S -> bbaab.
    S -> bb.
    S -> abbaab.
    S -> abb.
    

    Para cambiar este conjunto finito a Forma Normal de Chomsky, es suficiente para hacerlo por fuerza bruta sin ninguna inteligente de factoring. Primero le vamos a presentar dos de la terminal de reglas:

    X -> a.
    Y -> b.
    

    Ahora para cada cadena, en la que consumimos la primera letra con un terminal de la variable y el resto de las letras con nuevas variables. Por ejemplo, como este:

    S -> aabbb. (initial rule, not in Chomsky Normal Form)
    
    S -> XC, where X->a and C->abbb.
    C -> XD, where X->a and D->bbb.
    D -> YE, where Y->b and E->bb.
    E -> YY, where Y->b and Y->b.
    

    Acabamos de pasar por este proceso para todas las 6 cuerdas, generando una gran cantidad de nuevas variables intermedias.

    Agradable, fuera-de-la-cuadro de respuesta. Puede usted por favor detalles sobre cómo ocurrió esto y cómo se podría transformar esta a Forma Normal de Chomsky?
    Gracias por la sugerencia. Editado y hecho.

    OriginalEl autor Nayuki

Dejar respuesta

Please enter your comment!
Please enter your name here