Questões para estudo dirigido

Questões para estudo dirigido.

1. De acordo com a abordagem do curso defina ;
a. Alfabeto.
b. Palavra.
c. Comprimento de palavra
2. Dadas as seguintes palavras, apresente seus prefixos, sufixos e comprimentos;
a. prefixo
b. sufixo
c. abbccaa
d. yyttyty
3. Dado o alfabeto ={x,y} e as palavras, A = xyy e B = yyx. Apresente as possíveis concatenações.
4. Defina Computação no contexto de teoria da computação.
5. Para que servem as máquinas universais? Por que o conceito de solucionabilidade não pode se apoiar apenas em algoritmos?
6. Quais as características e como funciona a máquina Norma? Dê um exemplo de implementação.
7. Quais as características e como funciona a máquina de Post? Dê um exemplo de implementação.
8. Quais as características e como funciona a máquina de pilhas? Dê um exemplo de implementação.
9. Para a máquina de Turing, considere a tabela a seguir e represente o grafo correspondente bem como especifique a linguagem reconhecida.

b a b
A
B ß q0
(q0, b, D)
(q1, A, D)

(q3, B, D)
(q4, ß, D) q1 (q1, a, D)
(q2, B, E)

(q1, B, D)

q2

(q2, a, E)

(q0, A, D)
(q2, B, E)

q3

(q3, B, D)
(q4, ß, E) q4 10. O que é um MÓDULO no contexto de estados finitos estudado?
11. Considere um automóvel com um cambio de 4 marchas a frente (1a, 2a, 3a, 4a) uma a ré (r) e mais a posição neutro. O acionamento é feito através de comando eletrônico. Trata-se de uma “borboleta” que responde aumentando a marcha quando a borboleta é pressionada do lado direito (d) e reduz a marcha quando a borboleta é pressionada do lado esquerdo (e). Além disso, se o curso de pedal do acelerador for levado ao fim de curso (f), a marcha será reduzida em 1 exceto quando já estiver em 1ª marcha. Assim, responda.
a. Represente o módulo que modela o funcionamento do acionamento de marchas desse automóvel por Tabela de transições
b. Represente o módulo que modela o funcionamento do acionamento de marchas desse automóvel