Page 107 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS

107

Σ = alfabeto de la maquina

Γ = alfabeto de la cinta

Q0 = estado inicial

#, $ = limites izquierdo y derecho de la cinta (no son parte de la palabra a reconocer)
F = conjunto de estados de aceptación.

Δ = la función de transición que puede expresarse en términos muy generales así:
Q0#W$--> ΑQΒ en donde Q ϵ F (partiendo del estado inicial y leyendo símbolo a símbolo una W
entre los símbolos # Y $, pasará a un estado Q cualquiera que forme parte del conjunto de F,
haciendo los reemplazos Α, Β.

Un ala recorre una gramática sensible al contexto, tal que el lenguaje generado es L(G), de forma
tal que L(G) = L(ALA) Y L(ALA) = L(G).

Una gramática libre de contexto tiene reglas de producción del tipo:
V  W donde:

V = símbolos no terminales (NT)

W= cadena de terminales y/o no terminales.

Cuando se refiere al concepto libre de contexto, se dice que el símbolo no terminal puede ser
reescrito por el correspondiente w (terminales y no terminales), sin tener en cuenta que hay a la
izquierda o la derecha.

Importante es que este tipo de gramática permite describir la mayoría de los lenguajes de
programación, sobre todo lo atinente a la sintaxis asociada a cada lenguaje. Así los analizadores
del tipo LL y LR trabajan con un subconjunto limitado de estas gramáticas libres de contexto
ajustadas a cada lenguaje.

Definiciones formales:

Problemas recursivamente enumerarles

Un problema l es recursivamente enumerarle si existe una máquina de Turing M tal que L = L
(M).
Nótese que M en la definición no necesariamente se detiene en todas las entradas.
Caracterización de los problemas recursivamente enumerarles

Suponga que l es un lenguaje sobre un alfabeto A. Se puede caracterizar entonces: L es
recursivamente enumerarle si y sólo si existe un algoritmo que entrega una lista de cadenas W0,
W1, ... en A∗ tal que:

 Cada WI en la lista de salida está en L.
 Para cada W ∈ L, existe I ∈ N tal que W = WI (es decir lo puedo enumerar o numerar).

Vale decir, el algoritmo enumera los elementos de L.