Saltar al contenido

Gramáticas regulares vs libres de contexto

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

  1. B → a donde B es un no terminal en N y a es un terminal en Σ
  2. B → aC donde B y C están en N y a está en Σ
  3. 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

  1. A → a donde A es un no terminal en N y a es un terminal en Σ
  2. A → Ba donde A y B están en N y a está en Σ
  3. 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.

¡Haz clic para puntuar esta entrada!
(Votos: 0 Promedio: 0)



Utiliza Nuestro Buscador

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *