Atividade 4 - Linguagens Formais e Automatos

Prévia do material em texto

Atividade 3 – Linguagens Formais e Autômatos
Pergunta 01: 
Apesar da sua simplicidade, o modelo máquina de Turing possui, no mínimo, a mesma capacidade, ou seja, o mesmo poder computacional de qualquer computador de propósito geral. O ponto de partida de Turing foi analisar a situação, a partir da qual uma pessoa, com um instrumento de escrita e um apagador, poderia realizar cálculos em uma folha de papel e, a partir disso, derivar resultados lógicos.
 
Assinale a alternativa que indica a sequência correta para essa operação simples.
Pergunta 02: 
Leia o trecho a seguir:
“Em 1936, Alonzo Church demonstrou a tese de Church, na qual afirmou que qualquer função computável poderia ser processada através de uma máquina de Turing, dessa forma, se criou a premissa de que sempre existirá um procedimento definido, no qual uma máquina de Turing processará uma função computacional”.
 
MENEZES, P. B. Linguagens formais e autômatos. São Paulo: Sagah, 2015. p. 159.
 
Considerando o excerto apresentado sobre as propriedades da máquina de Turing, analise as afirmativas a seguir.
 
I. É impossível apresentar formalmente se a máquina de Turing é, de fato, o modelo mais genérico de dispositivo computacional.
II. Todos os modelos conhecidos propostos após a máquina de Turing possuem, no máximo, a mesma capacidade computacional da máquina de Turing.
III. A tese de Church não foi assumida como uma hipótese para toda a teoria da computação, razão pela qual não é empregada.
IV. A máquina de Turing é um autômato cuja fita possui tamanho máximo e pode ser usada simultaneamente como dispositivo de entrada e de saída.
 
Está correto o que se afirma em:
Pergunta 03: 
A máquina de Turing é um dispositivo teórico, conhecido como máquina universal, concebido pelo matemático britânico Alan Turing e que foi fundamental para o desenvolvimento da teoria da computação, tendo em vista ter sido o marco que deu origem aos primeiros dispositivos computacionais.
 
Considerando o texto apresentado, que aborda a implementação de uma das primeiras máquinas de Turing sob a ótica de sua essencialidade, analise as afirmativas a seguir e assinale V para a(s) verdadeira(s) e F para a(s) falsa(s).
 
I. (  ) A máquina de Turing foi inicialmente implementada como uma máquina automatizada capaz de calcular qualquer algoritmo e processar instruções.
II. (  ) Podemos dividir a aplicabilidade da máquina de Turing em problemas solucionáveis e problemas não solucionáveis ou não processáveis.
III. (  ) Para a máquina de Turing, uma das características de um algoritmo processável é ter uma descrição infinita e executável.
IV. (  ) Para a máquina de Turing, uma das características de um algoritmo processável é ter uma sequência de passos discretos.
 
Assinale a alternativa que apresenta a sequência correta.
Pergunta 04: 
Leia o trecho a seguir:
“A unidade de controle apresenta um número finito e predefinido de estados. A cabeça da fita tem a finalidade de ler o símbolo de uma célula, uma a cada vez, e gravar um novo símbolo por vez. Após a leitura/gravação (a gravação é realizada na mesma célula de leitura), a cabeça vai mover uma célula para a direita ou para a esquerda”.
 
MENEZES, P. B. Linguagens formais e autômatos. São Paulo: Sagah, 2015. p. 215.
 
A partir do apresentado, analise as asserções a seguir e a relação proposta entre elas.
 
I. A fita é usada simultaneamente como dispositivo de entrada, de saída e de memória de trabalho.
Pois:
II. Define o estado da máquina e comanda as leituras, as gravações e o sentido de movimento da cabeça.
 
A seguir, assinale a alternativa correta
Pergunta 05: 
Leia o trecho a seguir:
“O modelo abstrato de computação, proposto por Turing em 1936 e conhecido como máquina de Turing, tinha como objetivo explorar os limites da capacidade de expressar soluções de problemas. Trata-se de uma proposta de definição formal da noção intuitiva de algoritmo. Diversos outros trabalhos, como Cálculo Lambda e funções recursivas, resultaram em conceitos equivalentes ao da máquina de Turing”.
 
MENEZES, P. B. Linguagens formais e autômatos. São Paulo: Sagah, 2015. p. 114.
 
A respeito da hipótese de Church, analise as afirmativas a seguir e assinale V para a(s) Verdadeira(s) e F para a(s) Falsa(s).
  
I. (  ) A hipótese de Church apresenta-se demonstrável como na noção computável ou na função de algoritmo.
II. (  ) A capacidade de computação representada pela máquina de Turing é o limite máximo que pode ser atingido por qualquer dispositivo de computação.
III. (  ) A hipótese de Church não consegue afirmar que qualquer outra forma de expressar algoritmos terá a mesma capacidade computacional da máquina de Turing.
IV. (  ) A nomenclatura hipótese de Church não é assumida como verdadeira na ciência da computação.
 
Assinale a alternativa que apresenta a sequência correta.
Pergunta 06: 
Leia o trecho a seguir:
“Com o passar do tempo vários modelos surgiram, e a máquina de Turing é o modelo mais basilar da teoria da computação, porém, apesar das várias modificações, observou-se que, ao mudar as variáveis, os outros modelos não se mostraram diferentes em relação à máquina de Turing”.
 
MENEZES, P. B. Linguagens formais e autômatos. São Paulo: Sagah, 2015. p. 114.
 
Considerando o excerto apresentado sobre a definição do modelo autômato com múltiplas pilhas, analise as afirmativas a seguir:
 
I. As combinações de múltiplas modificações na máquina de Turing aumenta o poder computacional da máquina de Turing.
II. Trata-se de uma nítida proporção entre a máquina de Turing e as pilhas.
III. Adicionar um maior número de pilhas não gerará aumento da eficácia computacional.
IV. A definição básica é que a máquina de Turing permite que a fita seja limitada dos dois lados.
 
Está correto o que se afirma em:
Pergunta 07: 
Leia o excerto a seguir:
Uma linguagem recursiva é uma linguagem formal, capaz de indicar se determinada palavra w pertence ou não à linguagem, ou seja, para uma dada linguagem L, existirá uma máquina de Turing que é determinada por w ∈ L ou w ∈ ~L, logo, teremos entradas finitas, onde se uma dada palavra pertencer a linguagem, esta é aceita, se não, esta é recusada.
 
MENEZES, P. B. Linguagens formais e autômatos. São Paulo: Sagah, 2015. p. 157.
 
A respeito das linguagens recursivas e dos autômatos e suas classes, analise as afirmativas a seguir e assinale V para a(s) Verdadeira(s) e F para a(s) Falsa(s).
 
I. (  ) Se w ∈ L, o algoritmo não pode identificar a palavra que pertence à linguagem.
II. (  ) Se w ∈ ~L, o algoritmo pode ficar em loop infinito.
III. (  ) As duas classes de linguagem recursiva não contrariam a ideia de algumas pessoas.
IV. (  ) Reconhecer o complemento de uma linguagem não é possível.
 
Assinale a alternativa que apresenta a sequência correta.
Pergunta 08:
O diagrama de transição de estados, ou diagrama de máquina de estados, é uma representação do estado ou situação em que um objeto pode se encontrar no decorrer da execução de processos de um sistema. Observe a imagem a seguir, que apresenta uma ilustração de um diagrama de transição a fim de exemplificar o funcionamento da máquina de Turing:
Figura - Exemplo de um diagrama de transição
Fonte: Adaptada de Passos (2018).
#PraCegoVer: a imagem está dividida em três círculos, em que dois retornam para a direita e uma seta para esquerda, finalizando com uma seta reta para a esquerda, no q4, e ela está dividida com setas retas, para esquerda e para a direita, que fazem a ligação desses círculos.
PASSOS, Y. T. dos P. Máquinas de Turing. Slideshare, 2018. Disponível em: https://www.slideshare.net/yuripassos58/01-maquinas-de-turing. Acesso em: 27 jun. 2021.
 
Considerando a imagem apresentada, ilustrada a fim de apresentar o diagrama de transição, analise as afirmativas a seguir e assinale V para a(s) Verdadeira(s) e F
para a(s) Falsa(s).
 
I. (  ) O q0 é o estado inicial e M entra toda vez que retorna ao 0 restante mais à esquerda.
II. (  ) O q1 indica que deve ir à direita enquanto for 0 ou y, troca 1 pory e anda à direita para encontrar novos ys.
III. (  ) O q2 volta para a direita até encontrar o y, andando à direita, enquanto for x ou y.
IV. (  ) O q3 lê ys até encontrar um b à direita.
 
Assinale a alternativa que apresenta a sequência correta.
 
Pergunta 09:
Na matemática, uma equação diofantina é uma equação polinomial que permite que duas ou mais variáveis assumam apenas valores inteiros. Uma equação linear diofantina é uma equação entre duas somas de monômios de grau zero ou um. Observe, a seguir, a equação diofantina:
 
 Diofantinas
ax + by = c
Solução inteira
 
Considerando o exposto, a fim de apresentar o funcionamento da equação diofantina, analise as afirmativas a seguir e assinale V para a(s) Verdadeira(s) e F para a(s) Falsa(s).
 
I. (  ) Equações diofantinas são equações algébricas com coeficientes inteiros.
II. (  ) Problemas diofantinos têm menos equações que variáveis desconhecidas e se resumem a achar soluções inteiras que deverão funcionar corretamente para todas as equações.
III. (  ) Ao se desenvolver um conhecimento sobre as equações diofantinas lineares em duas ou mais variáveis não será possível solucionar problemas.
IV. (  ) Dada uma equação diofantina P(a0,...,an) = 0, em que P é um polinômio com coeficientes inteiros, quer-se saber se existe um procedimento efetivo que seja capaz de determinar, em um tempo finito, se suas raízes são inteiras.
 
Assinale a alternativa que apresenta a sequência correta.
Pergunta 10:
A ciência da computação trata da evolução do conhecimento matemático desenvolvido ao longo da história humana, desde a Mesopotâmia, passando pela Grécia, até chegar ao vale do silício, e boa parte dessa evolução ocorreu em 1936, com o formalismo desenvolvido por Alan Turing, que depois passou a ser a famosa máquina de Turing.
 
Assinale a alternativa que indica a definição de máquina de Turing.