Una Gramática Libre de Contexto es una tupla con 4 parámetros :
G = (V,T,P,S)
• V – conjunto de símbolos variables
• T – conjunto de símbolos terminales
• S ∈ V, símbolo inicial
• P – conjunto de reglas de producción :
A → α , con α sucesión de símbolos de V ∪ T, eventualmente vacía (α = ε)
Estas gramáticas, conocidas también 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 S ∉ (N ∪ T)
En una gramática libre del contexto, cada producción de P tiene la forma
Suscribirse a:
Enviar comentarios (Atom)
Profesor
Aqui tiene mi Blog o Pagina con evidencias, ejercicios, teoría y ejemplos de lo que hemos hecho en este cierre de semestre. Como puede ver a...
-
Un árbol de derivación permite mostrar gráficamente cómo se puede derivar cualquier cadena de un lenguaje a partir del símbolo distinguido ...
-
Tabla: conjunto de pares clave-valor, llamados elementos de la tabla. La tabla de símbolos es una componente necesaria de un compilador. Al...
-
El objetivo de la creación modular de una maquina de Turing es poder desarrollar máquinas complejas a partir de bloques elementales, a parti...
No hay comentarios:
Publicar un comentario