CFG significa gramática libre de contexto. Es una gramática formal que se utiliza para generar todos los patrones posibles de cadenas en un lenguaje formal determinado. La gramática libre de contexto G se puede definir mediante cuatro tuplas como:
G = (V, T, P, S)
Dónde,
GRAMO es la gramática, que consta de un conjunto de reglas de producción. Se utiliza para generar la cadena de un idioma.
t es el conjunto final de un símbolo terminal. Se indica con letras minúsculas.
EN es el conjunto final de un símbolo no terminal. Se indica con letras mayúsculas.
PAG es un conjunto de reglas de producción, que se utiliza para reemplazar símbolos no terminales (en el lado izquierdo de la producción) en una cadena con otros símbolos terminales o no terminales (en el lado derecho de la producción).
comando zip en linux
S es el símbolo inicial que se utiliza para derivar la cadena. Podemos derivar la cadena reemplazando repetidamente un no terminal por el lado derecho de la producción hasta que todos los no terminales hayan sido reemplazados por símbolos terminales.
Ejemplo 1:
Construya el CFG para el lenguaje que tiene cualquier número de a sobre el conjunto ∑= {a}.
Solución:
Como sabemos, la expresión regular para el lenguaje anterior es
r.e. = a*
La regla de producción para la expresión regular es la siguiente:
S → aS rule 1 S → ε rule 2
Ahora, si queremos derivar una cadena 'aaaaaa', podemos comenzar con símbolos de inicio.
S aS aaS rule 1 aaaS rule 1 aaaaS rule 1 aaaaaS rule 1 aaaaaaS rule 1 aaaaaaε rule 2 aaaaaa
Allá. = a* puede generar un conjunto de cadenas {ε, a, aa, aaa,.......}. Podemos tener una cadena nula porque S es un símbolo inicial y la regla 2 da S → ε.
Ejemplo 2:
Construya un CFG para la expresión regular (0+1)*
Solución:
rebajas con imágenes
El CFG puede estar dado por,
Production rule (P): S → 0S | 1S S → ε
Las reglas están en la combinación de 0 y 1 con el símbolo de inicio. Dado que (0+1)* indica {ε, 0, 1, 01, 10, 00, 11, ....}. En este conjunto, ε es una cadena, por lo que en la regla podemos establecer la regla S → ε.
Ejemplo 3:
Construya un CFG para un idioma L = donde w € (a, b)*.
Solución:
La cadena que se puede generar para un idioma determinado es {aacaa, bcb, abcba, bacab, abbcbba, ....}
La gramática podría ser:
S → aSa rule 1 S → bSb rule 2 S → c rule 3
Ahora, si queremos derivar una cadena 'abbcbba', podemos comenzar con símbolos de inicio.
S → aSa S → abSba from rule 2 S → abbSbba from rule 2 S → abbcbba from rule 3
Por tanto, cualquier cadena de este tipo puede derivarse de las reglas de producción dadas.
objeto de java
Ejemplo 4:
Construya un CFG para el lenguaje L = anorteb2ndonde n>=1.
Solución:
La cadena que se puede generar para un idioma determinado es {abb, aabbbb, aaabbbbbb....}.
La gramática podría ser:
S → aSbb | abb
Ahora, si queremos derivar una cadena 'aabbbb', podemos comenzar con símbolos de inicio.
S → aSbb S → aabbbb