Scribd
Cargar
97 vistas2 páginas

Turing y AP

Este documento presenta varios problemas relacionados con autómatas de pila y máquinas de Turing. En la sección 1, pide diseñar autómatas de pila para reconocer 7 lenguajes formales. En la sección 2, pide diseñar autómatas de pila no deterministas para reconocer 8 lenguajes. En la sección 3, pide diseñar máquinas de Turing para reconocer 7 lenguajes. Finalmente, la sección 4 pide construir máquinas de Turing para realizar 10 operaciones aritméticas y de manipul

Cargado por

Fidel Serpa
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd
97 vistas2 páginas

Turing y AP

Este documento presenta varios problemas relacionados con autómatas de pila y máquinas de Turing. En la sección 1, pide diseñar autómatas de pila para reconocer 7 lenguajes formales. En la sección 2, pide diseñar autómatas de pila no deterministas para reconocer 8 lenguajes. En la sección 3, pide diseñar máquinas de Turing para reconocer 7 lenguajes. Finalmente, la sección 4 pide construir máquinas de Turing para realizar 10 operaciones aritméticas y de manipul

Cargado por

Fidel Serpa
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd

UNIVERSIDAD CENTRAL DE VENEZUELA

FACULTAD DE CIENCIAS
ESCUELA DE COMPUTACION
Matemáticas Discretas III (Cód. 6108)

AUTOMATAS DE PILA Y MÁQUINAS DE TURING

1. Diseñe el AFP que acepte los siguientes lenguajes:


a. Σ = {a, b}. L= {aib2i | i ≥ 0}.
b. Σ = {a, b}. L= {a2ibi | i ≥ 1}.
c. Σ = {a, b, c}. L= {aibjci+j | i, j ≥ 0}.
d. Σ = {a, b, c}. L= {aibjcs | i, j ≥ 0, s= máx(0, i-j)}.
e. Σ = {0, 1}. L= {S2Sc | SϵΣ*, c= complemento}.
f. Σ = {0, 1}. L= {0i12i+j0j | i, j ≥ 1}.
g. Σ = {a, b}. L = {anbn+1 | n ≥ 0}.

2. Diseñe un AFNDP que reconozca los siguientes lenguajes:


a. L = {aib2i : i ≥ 1}
b. L = {a2ib3i : i ≥1}
c. L = {aibj : i ≥ j ≥ 1}
d. L = {aibj : j ≥ i ≥ 1}
e. L = {ai+jbicj : i,j≥1}
f. Lenguaje de todas las cadenas de ceros y unos con el mismo número de
ceros que de unos.
h. Lenguaje de todas las cadenas con el doble de ceros que de unos

3. Diseñe una máquina de Turing que reconozca los siguientes lenguajes:


a. Σ = {0,1}. Lenguaje de todas las cadenas que terminen en 0.
b. Σ = {0,1}. Lenguaje de todas las cadenas que contengan un número par de
1’s.
c. L = {anbncn: n≥1}
d. L = {02m1m: m≥0}
e. L = {aib2iai: i≥0}
f. L = {aibjci+j: i≥0, j≥1}
g. El conjunto de cadenas binarias con el mismo número de ceros que de
unos.
4.- Construya una máquina de Turing que calcule:
a. f(m) = m + 3
b. f(m,n) = m + n
c. f(m) = 2m
d. f(m) = m div 2
e. f(m) = m mod 3
f. f(m,n) = 2*m + 3*n
g. f(m,n) = max(m,n)
h. f(m,n) = min (m,n)
i. Duplicar cadena sobre {a,b}
j. Insertar la cadena ‘abba’ en la tercera posición

También podría gustarte