3. Lenguajes Libres de Contexto
3.1. GRAMATICAS LIBRES DEL CONTEXTO
Este tipo de gramáticas son también conocidas como gramáticas de tipo 2 o gramáticas independientes del contexto, son las que generan los lenguajes libres o independientes del contexto.
Los lenguajes libres del contexto son aquellos que pueden ser reconocidos por un autómata de pila determinístico o no determinístico.
Como toda gramática se definen mediante una cuadrupla G = (N, T, P, S), siendo
- N es un conjunto finito de símbolos no terminales
- T es un conjunto finito de símbolos terminales N ∩ T = Ø P es un conjunto finito de producciones
S es el símbolo distinguido o axioma
En una gramática libre del contexto, cada producción de P tiene la forma
Es decir, que en el lado izquierdo de una producción pueden aparecer el símbolo distinguido o un símbolo no terminal y en el lado derecho de una producción cualquier cadena de símbolos terminales y/o no terminales de longitud mayor o igual que 1.
La gramática puede contener también la producción S →ε si el lenguaje que se quiere
generar contiene la cadena vacía.
Los LLC se describen mediante las Gramáticas Libres de Contexto (GLC).
- Todos los LR son LLC, pero no todos los LLC son LR.
- Los LLC (que no sean LR) no pueden denotarse mediante expresiones regulares ni pueden ser reconocidos mediante AF.
- Los LLC se utilizan para especificar la mayoría de los lenguajes de programación
Nota:
Informaciòn recopilada de las siguientes ligas:
José Miguel Puerta, Antonio Fernández Caballero, Departamento de Informática Universidad de Castilla-la Mancha en:
Le doy gracias ala lic. toro por las explicaciones que nos ha facilitado es una gran aportacion de los que no ha dado sobre la gramatica y quiesieramos agregar mas sobre el tema erika y yo: Las gramáticas libres de contexto amplían la capacidad para especificar lenguajes al incluir algunos lenguajes que no son reconocidos por un autómata finito. Las gramáticas libres de contexto son útiles para describir expresiones aritméticas que tengan una anidación arbitraria de paréntesis balanceados y estructuras de bloque en los lenguajes de programación.
ResponderEliminarPrimeramente damos las gracias Lic. Ma. Alejandra Rosas Toro por la excelente explicación del tema ya que es más comprensible gracias a los ejemplos, también por aclarar las dudas suscitadas.
ResponderEliminarUn lenguaje formal es libre de contexto si hay una gramática libre de contexto que la genera.
Las gramáticas libres de contexto permiten describir la mayoría de los lenguajes de programación.