automatas



























GLC.
Gramáticas Libres de Contexto (GLC), o de tipo 2: las reglas son de la forma X → α, donde X es una variable y α es una cadena que puede contener variables y constantes. Estas gramáticas producen los lenguajes Libres de Contexto (abreviado “LLC”)
Capturan la noción de constituyente sintáctico y la noción de orden.
Herramienta formal quepuede ser vista tanto desde un punto de vista generador como estructurador.
Propiedades computacionales interesantes: se puede reconocer en tiempo polinómico.
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ónde símbolos de V U T, eventualmente vacía (α = ε)
Una GLC es un dispositivo generador.
Definimos el lenguaje LG generado por una gramática G del siguiente modo: G = {w / S →* w}, siendo ⇒* una “especie” de clausura transitiva de → y w una tira de terminales.
ÁRBOL DE DERIVACIÓN.
Es una representación gráfica (en forma de árbol invertido) de un proceso de derivación en una gramática. Se defineel árbol de derivación como sigue:
la raíz del árbol será el símbolo inicial de la gramática
los nodo interiores del árbol están etiquetados por los símbolos no terminales
las hojas están etiquetadas por símbolos terminales
si un nodo interior etiquetado por A, posee como hijos los nodos etiquetados por , entonces es una producción de la gramática, en donde , representa símbolo terminal ono terminal.
Sea la siguiente gramática:
G=( Σ={a, b}, N={S,A,B},S P ) P: S→aABAa , A→ε |aA , B→ε|bB la construcción de un árbol de derivación en el proceso de la generación de la palabra aa es el siguiente:

Propiedades de un árbol de derivación.

Sea G = (N, T, S, P) una gramática libre de contexto, sea A Є N una variable. Diremos que un árbol TA= (N, E) etiquetado es un árbol dederivación asociado a G si verifica las propiedades siguientes:
La raíz del árbol es un símbolo no terminal
Cada hoja corresponde a un símbolo terminal o λ.
Cada nodo interior corresponde a un símbolo no terminal.
Para cada cadena del lenguaje generado por una gramática es posible construir (al menos) un árbol de derivación, en el cual cada hoja tiene como rótulo uno de los símbolos de la cadena.Árbol de derivación. 

Ejemplo:

Sea G=(N, T, S, P) una GLC con P: S→ ab|aSb

La derivación de la cadena aaabbb será: S → aSb → aaSbb → aaabbb y el árbol de derivación:

FORMAS NORMALES DE CHOMSKY.

Una gramática formal está en Forma normal de Chomsky si todas sus reglas de producción son de alguna de las siguientes formas:

A → BC o
A → a o

donde A, B y C son símbolos no terminales (ovariables) y α es un símbolo terminal.

Todo lenguaje independiente del contexto que no posee a la cadena vacía, es expresable por medio de una gramática en forma normal de Chomsky (GFNCH) y recíprocamente. Además, dada una gramática independiente del contexto, es posible algorítmicamente producir una GFNCH equivalente, es decir, que genera el mismo lenguaje.

Sea G = (∑ N, ∑T, P, $) unagramática con P ⊂ ∑N X (∑N U ∑T)* y X Є ∑N un símbolo no-terminal (o una variable). Podemos clasificar tales símbolos X en tres clases:
Variables accesibles:
Si existe una derivación desde el símbolo inicial que contiene X, es decir, existe $ → * α Xβ donde α, β Є∑*
Variables generativas:
Si existe una derivación desde el la variable que produce una sentencia, es decir, existe X →* ω donde ω Є *T.Variables útiles:
Si existe una derivación desde el símbolo inicial usando que produce una sentencia ω, es decir, existe $ →* α X β →*ω donde α, β Є ∑* y ω Є ∑*T.

DIAGRAMAS DE SINTAXIS

Los diagramas sintácticos, de sintaxis o diagramas del ferrocarril son una forma de representar una gramática libre de contexto. Representan una alternativa gráfica para la Forma de Backus-Naur (BNF,...