¿Cómo puedo convertir algunos de lenguaje regular a su equivalente Contexto Libre de la Gramática?
Es necesario construir el DFA correspondiente a la expresión regular, o hay alguna regla para este tipo de conversión?

Por ejemplo, considere la siguiente expresión regular

01+10(11)*

¿Cómo puedo describir la gramática correspondiente a la anterior RE?

se preguntaba si hay alguna librería de código libre implementaciones útil para esta tarea por ahora

OriginalEl autor Prasoon Saurav | 2010-04-14

3 Comentarios

  1. 11
    • Cambio a+B a la gramática

      G -> A
      G -> B
    • Cambio de Una* a

      G -> (empty)
      G -> A G
    • Cambio de AB en

      G -> AB

    y proceder de forma recursiva en a y B. la Base de los casos están vacías idioma (no de producción) y un único símbolo.

    En su caso

     A -> 01
     A -> 10B
     B -> (empty)
     B -> 11B

    Si el idioma es descrita por el autómata finito:

    • uso de los estados como no terminal símbolos
    • usar el lenguaje como un conjunto de símbolos terminales
    • agregar una transición p -> aq para cualquier transición de p> q en la letra a en el original autómata
    • uso inicial del estado como símbolo inicial de la gramática
    ¿Por qué es B -> 11 en lugar de B -> B11?
    Mi error, gracias.
    ¿Por qué están cambiando A+B en G -> A y G -> B? No + significa «uno o más de los anteriores expresión» en regex?
    En el lenguaje formal de la teoría de A+B se utiliza para denotar la suma, en los lenguajes de programación notación A|B se utiliza en su lugar.

    OriginalEl autor sdcvvc

  2. 6

    Supongo que te refieres a convertir a una gramática formal, con reglas del formulario V->w, donde V es un no terminal y w es una cadena de terminales/nonterminals. Para empezar, usted puede simplemente decir (mezcla de CFG y sintaxis regex):

    S -> 01+10(11)*

    Donde S es el símbolo inicial. Ahora vamos a romper un poco (y añadir un espacio en blanco para mayor claridad):

    S -> 0 A 1 0 B
    A -> 1+
    B -> (11)*

    La clave es convertir *es y +es la recursividad. En primer lugar, vamos a convertir la estrella de Kleene de un plus por la inserción de un intermedio de la regla que acepta la cadena vacía:

    S -> 0 A 1 0 B
    A -> 1+
    B -> (empty)
    B -> C
    C -> (11)+

    Por último, vamos a convertir + notación para recursividad:

    S -> 0 A 1 0 B
    A -> 1
    A -> A 1
    B -> (empty)
    B -> C
    C -> 11
    C -> C 11

    Para manejar x?, simplemente, que se dividió en una regla de producción de vacío y una regla de producción de x .

    OriginalEl autor Joey Adams

  3. 2

    Realidad, diferentes CFG gramáticas pueden producir el mismo idioma. Así que dada una expresión regular (lengua habitual), de mapas, de nuevo una CFG no es única.

    Definitivamente, usted puede construir una CFG que se traducen en una expresión regular. Las respuestas de arriba muestra algunas maneras de lograr esto.

    Espero que esto le da un alto nivel de idea.

    OriginalEl autor JackWM

Dejar respuesta

Please enter your comment!
Please enter your name here