Convierta la expresión regular a CFG

Question

¿Cómo puedo convertir un poco de lenguaje normal a su Gramática libre de contexto equivalente? ¿Es necesario construir el DFA correspondiente a esa expresión regular o existe alguna regla para tal conversión?

Por ejemplo, considere la siguiente expresión regular

01 + 10 (11) ^*

¿Cómo puedo describir la gramática correspondiente al RE arriba?

Answer 1

• Cambio A + B a la gramática

  G -> A 
  G -> B 
  

• Cambio A * a

  G -> (empty) 
  G -> A G 
  

• Cambio AB para

  G -> AB 
  

y proceda recursivamente en A y B. Los casos base son lenguaje vacío (sin producciones) y un solo símbolo.

En su caso

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

Si el idioma es descrito por autómata finito:

• estados uso como símbolos no terminales
• utilizan el lenguaje como un conjunto de símbolos terminales
• añadir una transición p -> aq para cualquier transición p -> q en la letra a en el autómata originales
• utilizar el estado inicial como símbolo inicial en la gramática

Answer 2

Supongo que quiere decir convertirlo a una gramática formal con reglas de la forma V-> w, donde V es un no terminal y w es una cadena de terminales/no terminales. Para empezar, se puede decir simplemente (mezclando la sintaxis de expresiones regulares y CFG):

Donde S es el símbolo inicial. Ahora vamos a romper, en 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 a la recursividad. En primer lugar, vamos a convertir la estrella de Kleene a un plus mediante la inserción de una regla intermedia que acepte la cadena vacía:

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

Por último, convertiremos + notación para la recursividad:

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

Manejar x?, simplemente divídalo en una regla que produzca vacío y una regla que produzca x.

Answer 3

En realidad, diferentes gramáticas de CFG pueden producir el mismo idioma. Entonces, dada una expresión regular (lenguaje regular), su mapeo de un CFG no es único.

Definitivamente, se puede construir un CFG que dan como resultado una expresión regular dada. Las respuestas anteriores muestran algunas formas de lograr esto.

Hope esto le da una idea de alto nivel.