Turing
Enviado por erickrenteria • 20 de Mayo de 2014 • Informes • 315 Palabras (2 Páginas) • 213 Visitas
de Turing aceptan lenguajes estructurados por frases.
Configuración de una máquina de Turing:
Contenido de la cinta: entre corchetes.
A la izquierda del símbolo actual se incluye el estado.
Aceptación: secuencia de configuraciones de la máquina que empieza con
]ΔYΔ] y termina con [hΔ Δ[i
Teorema: Todo lenguaje estructurado por frases es aceptado por una máquina de Turing.
Para cada gramática G existe una máquina de Turing no determinista M de 2 cintas que
aceptas el lenguaje generado por G.
Construcción de la máquina:
1. Se copia la cadena de entrada en la primera cinta.
2. Se escribe S (símbolo inicial) en la cinta 2.
3. Se aplican las reglas de reescritura de forma no determinista a la cadena de la cinta 2.
4. Si la cinta 2 contiene sólo símbolos terminales, se compara con la cadena de la cinta 1.
Si son iguales, el proceso ha terminado. Si no, provocar una terminación anormal.
Las máquinas de Turing originan las siguientes clases de lenguajes:
L es recursivamente enumerable (RE) si exist
de Turing aceptan lenguajes estructurados por frases.
Configuración de una máquina de Turing:
Contenido de la cinta: entre corchetes.
A la izquierda del símbolo actual se incluye el estado.
Aceptación: secuencia de configuraciones de la máquina que empieza con
]ΔYΔ] y termina con [hΔ Δ[i
Teorema: Todo lenguaje estructurado por frases es aceptado por una máquina de Turing.
Para cada gramática G existe una máquina de Turing no determinista M de 2 cintas que
aceptas el lenguaje generado por G.
Construcción de la máquina:
1. Se copia la cadena de entrada en la primera cinta.
2. Se escribe S (símbolo inicial) en la cinta 2.
3. Se aplican las reglas de reescritura de forma no determinista a la cadena de la cinta 2.
4. Si la cinta 2 contiene sólo símbolos terminales, se compara con
...