Si encuentras algo que no comprendes puedes dejarnos un comentario y haremos todo lo necesario de ayudarte rápidamente.
Solución:
La gramática regular es lineal a la derecha o a la izquierda, mientras que la gramática libre de contexto es básicamente cualquier combinación de terminales y no terminales. Por lo tanto, puede ver que la gramática regular es un subconjunto de la gramática libre de contexto.
Entonces, para un palíndromo, por ejemplo, es de la forma,
S->ABA
A->something
B->something
Puede ver claramente que los palíndromos no se pueden expresar en gramática regular, ya que debe ser lineal a la derecha o a la izquierda y, como tal, no puede tener un no terminal en ambos lados.
Dado que las gramáticas regulares no son ambiguas, solo hay una regla de producción para un no terminal dado, mientras que puede haber más de una en el caso de una gramática libre de contexto.
Creo que lo que quieres pensar son los diversos lemas de bombeo. Un lenguaje regular puede ser reconocido por un autómata finito. Un lenguaje libre de contexto requiere una pila, y un lenguaje sensible al contexto requiere dos pilas (lo que equivale a decir que requiere una máquina de Turing completa).
Entonces, si pensamos en el lema de bombeo para los lenguajes regulares, lo que dice, esencialmente, es que cualquier lenguaje regular se puede dividir en tres partes, X, yy zdonde todas las instancias del lenguaje están en xy*z (donde * es la repetición de Kleene, es decir, 0 o más copias de y.) Básicamente tiene un “no terminal” que se puede expandir.
Ahora, ¿qué pasa con los lenguajes libres de contexto? Hay un lema de bombeo análogo para lenguajes libres de contexto que divide las cadenas del lenguaje en cinco partes, uvxyzy donde todas las instancias del lenguaje están en ultravioletaixyizpara i ≥ 0. Ahora, tienes dos “no terminales” que se pueden replicar o bombear, siempre y cuando tengas el mismo numero.
La diferencia entre la gramática regular y libre de contexto:
(N, Σ, P, S): terminales, no terminales, producciones, estado inicial Símbolos de terminales
● símbolos elementales del lenguaje definidos por una gramática formal
● abc
Símbolos no terminales (o variables sintácticas)
● reemplazado por grupos de símbolos terminales de acuerdo con las reglas de producción
● ABC
gramática regular: gramática regular derecha o izquierda gramática regular derecha, todas las reglas obedecen a las formas
- B → a donde B es un no terminal en N y a es un terminal en Σ
- B → aC donde B y C están en N y a está en Σ
- B → ε donde B está en N y ε denota el vacío stringes decir, el string de longitud 0
gramática regular izquierda, todas las reglas obedecen a las formas
- A → a donde A es un no terminal en N y a es un terminal en Σ
- A → Ba donde A y B están en N y a está en Σ
- A → ε donde A está en N y ε es el vacío string
gramática libre de contexto (CFG)
○ gramática formal en la que cada regla de producción tiene la forma V → w
○ V es un único símbolo no terminal
○ w es un string de terminales y/o no terminales (w puede estar vacío)
Te mostramos las comentarios y valoraciones de los usuarios
Si te gustó nuestro trabajo, puedes dejar un post acerca de qué te ha gustado de este artículo.