Scribd
Cargar
492 vistas26 páginas

Introducción a Máquinas de Turing

Este documento presenta 5 ejercicios sobre máquinas de Turing, incluyendo las definiciones de las máquinas y sus transiciones para cada problema. Los ejercicios resuelven tareas como contar símbolos en una cadena, convertir símbolos, y duplicar un símbolo en la entrada.

Cargado por

Danny Tapias Duque
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 DOCX, PDF, TXT o lee en línea desde Scribd
492 vistas26 páginas

Introducción a Máquinas de Turing

Este documento presenta 5 ejercicios sobre máquinas de Turing, incluyendo las definiciones de las máquinas y sus transiciones para cada problema. Los ejercicios resuelven tareas como contar símbolos en una cadena, convertir símbolos, y duplicar un símbolo en la entrada.

Cargado por

Danny Tapias Duque
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 DOCX, PDF, TXT o lee en línea desde Scribd

Maquinas de Turing

Danny Tapias Duque

Juan Diego Zapata

Institución Universitaria Digital de Antioquia

Desarrollo de Software

PREPROF2102TC 20200003: Autómatas, Gramáticas y Lenguajes

Docente. Joaquín Fernando Aguilar Camacho

Diciembre 2021
1. a n b n+1 c n

a b c µ
→q0 (q1;µ,R) λ λ (q7;µ,S)
q1 (q1;a,R) (q1;b,R) (q1;c,R) (q2;µ,L)
q2 λ λ (q3;µ,L) λ
q3 λ (q5;µ,L) (q4;µ,L) λ
q4 λ (q6;c,L) (q4;c,L) λ
q5 λ (q6;µ,L) λ λ
q6 (q6;a,L) (q6;b,L) λ (q0;µ,R)
*q7 λ λ λ λ

M =(K= { q 0 , q 1, q 2 , q 3 , q 4 , q 5 , q 6 , q 7 } , Σ={ a , b , c } , Γ = {a , b , c , μ } , s={ q 0 } , T ={ q 7 } , B={ µ } , δ= { δ ( q 0 , a )=


2. Una cadena compuesta con 0 y 1, debe convertir cada 0 en 1 y cada 1 en 0.

0 1 µ
→q0 (q0;1,R) (q0;0,R) (q1;µ,L)
q1 (q1;0,L) (q1;1,L) (q2,µ,R)
*q2 λ λ λ

M =(K= { q 0 , q 1, q 2 } , Σ= {0,1 } , Γ= { 0,1, μ } , s= {q 0 } ,T = {q 2 } , B= { µ } , δ={δ ( q 0,0 )=( q 0; 1 , R ) , δ ( q 0,1 )= ( q 0 ; 0


3. Una cadena compuesta con 0 y 1, debe contar el número de 1 que se
encuentren en
la cadena. Por ejemplo, en una cadena 011010, el resultado debe contener sin
importar lo que este a la izquierda, uno o varios espacios vacíos 111 espacios
vacíos
(puede ser 111, aaa, XXX, lo importante es que indique el número de unos).
0 1 µ
→q0 (q0;µ,R) (q1;1,R) λ
q1 (q3;1,L) (q1;1,R) (q4;µ,L)
q2 λ (q1;µ,R) λ
q3 λ (q3;1,L) (q2;µ,R)
q4 λ (q4;1,L) (q5;µ,R)
*q5 λ λ λ

M =(K= { q 0 , q 1, q 2 , q 3 , q 4 , q 5 } , Σ={ 0,1 } , Γ = {0,1 , μ } , s={ q 0 } , T ={ q 5 } , B={ µ } , δ={δ ( q 0,0 )=( q 0 ; μ , R ) , δ ( q


4. Cree un enunciado propio que pueda ser una aplicación de la máquina de
Turing
Una cadena compuesta por (a) que devuelva el doble de (a) que se ingresaron en
un principio.

a 1 μ
→q0 (q0;1,R) λ (q1;μ,L)
q1 (q1;a,L) (q2;a,R) (q3;μ,R)
q2 (q2;a,R) λ (q1;μ,L)
*q3 λ λ λ

M =¿ (Q0,a)=(Q0,1,R), δ(Q0,μ)=(Q1,μ,L), δ(Q1,a)=(Q1,a,L), δ(Q1,1)=(Q2,a,R), δ(Q1,μ)=(Q3,μ,R),


δ(Q2,a)=(Q2,a,R),δ(Q2,μ)=(Q1,μ,L)}¿
5. Para el siguiente ejercicio, debe diseñar la máquina de Turing y crear la
notación matemática.
Considerando la séptupla y las transiciones.
• M=({Q0,Q1,Q2},{0,1,2},{0,1,μ},Q0, μ,{Q2},δ)
• δ(Q0,0)=(Q1,1,R)
• δ(Q1,1)=(Q0,0,R)
• δ(Q1, μ)=(Q2, μ,R)
• δ(Q1, 2)=(Q2, 2,R)
• δ(Q2, 2)=(Q2, 2,R)
• δ(Q2, μ)=(Q2, μ,R)
0 1 2 µ
→q0 (q1;1,R) λ λ λ
q1 λ (q0;0,R) (q2;2,R) (q2;µ,R)
q2 λ λ (q2;2,R) (q2;µ,R),(q3;µ,S)
*q3 λ λ λ λ

M =¿ (Q0,0)=(Q1,1,R), δ(Q1,1)=(Q0,0,R), δ(Q1,μ)=(Q2,μ,R), δ(Q1,2)=(Q2,2,R), δ(Q2,2)=(Q2,2,R),


δ(Q2,μ)=(Q2,μ,R),δ(Q2,μ)=(Q3,μ,S)}¿

También podría gustarte