Faça um programa cliente/servidor multithread onde:

LISTA DE EXERCÍCIOS – Máquinas de Turing
1. Seja M = (K, ∑, δ, s), em que K = {q0, q1, q2}, ∑ = {a, b, #}, s = q0, e δ é fornecido pela tabela abaixo: q δ(q, σ) σ q0 a (q1, L) q0 b
(q0, R) q0 #
(q0, R) q1 a
(q1, L) q1 b
(q2, R) q1 #
(q1, L) q2 a
(q2, R) q2 b
(q2, R) q2 #
(h, ‘#’)
a) Execute a máquina a partir da configuração inicial (q0, abb#bb##aba).
b) Descreva informalmente o que realiza M, e o que M faria se fosse iniciada em qualquer outro quadrado da fita.
2. Construa uma máquina de Turing simples para decidir as cadeias de L={w ∈ {a,b}*| w tem 2 “a” consecutivos}.
3. Demonstre o lema que permite a construção de máquinas de Turing compostas.
4. Explique o que a máquina de Turing composta abaixo faz (exercite-a com a seguinte entrada #abab##):
>L

σ≠#

RσL

σ=#
R (#) R#
5. Construa uma máquina de Turing composta para efetuar a operação "monus" entre dois números naturais escritos em unário (se o parâmetro da esquerda é maior que o da direita o resultado é a subtração, senão o resultado é zero, isto é, a fita será apagada). 6. Idem anterior para a operação “div”.
7. Idem anterior para a operação “mod”.
8. Construa uma máquina de Turing composta para multiplicar dois números naturais escritos em unário. Sugestão: Utilize a máquina de cópia, depois una as cadeias com outra máquina (descreva as máquinas separadamente e depois monte a estrutura conjunta). 9. Construa uma Máquina de Turing para decidir anbncn.
10. Descreva uma Máquina de Turing não-determinística que aceite a linguagem L:
L = {wwRuuR | w, u ∈ {a, b}*}.