Atividade 2 Linguagens Formais e Automatos

Prévia do material em texto

12/06/2024, 09:21Atividade 2: Linguagens Formais e Autômatos
Página 1 de 10https://famonline.instructure.com/courses/35817/quizzes/177188
Atividade 2
Entrega 21 abr em 23:59
Pontos 1
Perguntas 5
Disponível 12 fev em 0:00 - 21 abr em 23:59
Limite de tempo Nenhum
Tentativas permitidas 2
Instruções
Este teste foi travado 21 abr em 23:59.
Histórico de tentativas
Tentativa Tempo Pontuação
MANTIDO Tentativa 2 13 minutos 0,4 de 1
MAIS RECENTE Tentativa 2 13 minutos 0,4 de 1
Tentativa 1 6 minutos 0,4 de 1
Pontuação desta tentativa: 0,4 de 1
Enviado 4 abr em 15:14
Esta tentativa levou 13 minutos.
 
Pergunta 1
0 / 0,2 pts
Importante:
Caso você esteja realizando a atividade através do aplicativo "Canvas Student", é necessário que
você clique em "FAZER O QUESTIONÁRIO", no final da página.
Leia o texto a seguir:
Na Teoria dos autômatos, um sub tópico da Ciência da computação teórica, um autômato finito
determinístico — também chamado máquina de estados finita determinística (AFD) — é uma
Máquina de estados finita que aceita ou rejeita cadeias de símbolos gerando um único ramo de
computação para cada cadeia de entrada. "Determinística" refere-se à unicidade do
processamento. O primeiro conceito similar ao de autômatos finitos foi apresentado por
McCulloch e Pitts em 1943. Modelo esse que foi produzido na busca por estruturas mais simples
A+
A
A-
https://famonline.instructure.com/courses/35817/quizzes/177188/history?version=2
https://famonline.instructure.com/courses/35817/quizzes/177188/history?version=2
https://famonline.instructure.com/courses/35817/quizzes/177188/history?version=1
12/06/2024, 09:21Atividade 2: Linguagens Formais e Autômatos
Página 2 de 10https://famonline.instructure.com/courses/35817/quizzes/177188
Você respondeu
 que se refere à unicidade do processamento.
A alternativa está incorreta, pois uma Máquina de Estados Finita Determinística proporciona a
existência de uma unidade de processamento, portanto, ela não tem relação com a definição de
Autômato Finito determinístico. A alternativa correta é “entendida como conceito abstrato”, pois o
conceito de Autômato Finito Determinístico é considerado abstrato na área da matemática.
Considerando suas características determinísticas, ele pode ser aplicado via Hardware e
Software com o objetivo de solucionar problemas.
Resposta correta
para a reprodução de máquinas de estado finitas.
A figura acima representa um autômato finito determinístico através de um Diagrama de transição
de estados. Nesse autômato há três estados: S0, S1 e S2 (representados graficamente por
círculos). A entrada é constituída por uma sequência finita de caracteres 1s e 0s. Para cada
estado da máquina, existe um arco de transição levando a um outro estado para ambos os
caracteres 0 e 1. Isso significa que, em um dado estado, após a leitura de cada símbolo a
máquina determinística transita para um único estado referente à aresta associada ao símbolo.
Por exemplo, esteja o autômato atualmente no estado S0 e o símbolo de entrada para aquela
instância um '1', então ele salta deterministicamente para o estado S1. Todo AFD possui um
estado inicial (denotado graficamente por uma seta de origem anônima) onde a sua computação
começa e um conjunto de estados de aceitação (denotados graficamente por um círculo de borda
dupla) o qual indica a aceitação da cadeia de entrada.
Um Autômato finito determinístico é normalmente definido como um conceito matemático
abstrato, mas devido à seu fator determinístico, ele pode ser implementado através de Hardware
e Software para resolver diversos problemas específicos. Por instância, AFDs são utilizados para
modelar softwares que validam entradas de usuário tal como o seu e-mail em um servidor de
correio eletrônico [...].
Fonte: AUTÔMATO finito determinístico. Wikiwand, [s. d]. Disponível em:
<https://www.wikiwand.com/pt/Aut%C3%B4mato_finito_determin%C3%ADstico>. Acesso em: 05 ago. 2023.
Um Autômato Finito Determinístico, também conhecido como Máquina de Estados Finita
Determinística (AFD), é uma máquina de estados finita
12/06/2024, 09:21Atividade 2: Linguagens Formais e Autômatos
Página 3 de 10https://famonline.instructure.com/courses/35817/quizzes/177188
 entendida como conceito abstrato.
 que valida entradas de usuário.
 que deve ser implementada somente via software.
 que é área importante na teoria dos autômatos.
 
Pergunta 2
0,2 / 0,2 pts
Leia o trecho abaixo:
Um autômato finito (às vezes dizemos, por uma tradução literal do inglês, máquina de estado
finito, em vez de máquina com um número finito de estados ou máquina de estado finito ou
máquina de estado finito), autômato de estado finito ou máquina de estado finito (FSA, FSM), é
uma máquina abstrata que é uma ferramenta fundamental na matemática discreta e na ciência da
computação. Eles são encontrados na modelagem de processos, controle, protocolos de
comunicação, verificação de programas, teoria da computabilidade, no estudo de linguagens
formais e na compilação. Eles são usados para encontrar padrões em um texto.
Nós distinguimos autômatos finitos não determinísticos (abreviados AFN) autômato finito não
determinístico inglês ou NFA, os autômatos finitos determinísticos (abreviados AFD) em
autômatos finitos determinísticos ingleses ou DFA. Sem mais precisão, um autômato finito é
sempre não determinístico, mas deveríamos antes dizer “indeterminista”, uma vez que é
irrelevante se é determinístico ou não.
Autômatos finitos (determinísticos ou não) reconhecem exatamente as linguagens racionais. Eles
são as máquinas mais simples na hierarquia de Chomsky e, portanto, são menos poderosas do
que autômatos pushdown e, é claro, máquinas de Turing.
 Figura 1: Autômato finito que reconhece gravações binárias de múltiplos de 3.
Um autômato é composto de estados e transições. Seu comportamento é controlado por uma
palavra fornecida como entrada: o autômato muda de estado para estado, de acordo com as
transições, ao ler cada letra da entrada. No exemplo acima, para a entrada, e se o PLC iniciar, ele
passa sucessivamente pelos estados, o cálculo correspondente é:
12/06/2024, 09:21Atividade 2: Linguagens Formais e Autômatos
Página 4 de 10https://famonline.instructure.com/courses/35817/quizzes/177188
 Um autômato é denominado determinístico, pois é composto de memória limitada.
 
Os Autômatos Finitos não Determinísticos (AFD) são os tipos que conseguem identificar as linguagens
racionais de forma precisa.
 
Os AFN estão no nível mais alto de complexidade da hierarquia de Chomsky, inclusive das máquinas de Turing.
Correto!
 
São as transições de um autômato que definem seu estado e isso ocorre na interpretação da palavra de
entrada.
 
Autômatos Finitos não Determinísticos, ou Máquinas de Estados Finitos, do inglês, são usados na modelagem
de processos.
Esta alternativa é correta, pois um autômato é composto de estados e transições. O estado inicial
 
O autômato é chamado de “finito” porque possui um número finito de estados: portanto, possui
apenas uma memória limitada. Podemos muito bem considerar autômatos sem limitação no
número de estados: a teoria resultante é muito semelhante à teoria usual. Um autômato finito
pode ser visto como um grafo direcionado rotulado: estados são vértices e transições são arestas
rotuladas. O estado inicial é marcado por uma seta de entrada; um estado final é, de acordo com
os autores, duplamente circulado (na figura 1 acima, o estado é inicial e final) ou marcado com
uma seta para fora (na figura 2 abaixo, 1 é inicial e 3 é final).
Fonte: AUTÔMATO finito não determinístico. Frwiki, [s. d]. Disponível em:
https://pt.frwiki.wiki/wiki/Automate_fini_non_d%C3%A9terministe. Acesso em: 05 ago. 2023.
Considerando as informações apresentadas, assinale a opção correta:
12/06/2024, 09:21Atividade 2: Linguagens Formais e Autômatos
Página 5 de 10https://famonline.instructure.com/courses/35817/quizzes/177188
é marcado por uma seta de entrada, e o estado final é duplamente circulado ou marcado com
uma seta para fora.
Pergunta 3
0,2 / 0,2 pts
Leia o texto a seguir:
Autômatos com pilha diferem da definição normal de máquinas de estados finitos de duas
maneiras:
1. Eles podem fazer uso da informação que está no topo da pilha para decidir qual transição
deve ser efetuada;
2. Eles podem manipular a pilha ao efetuar uma transição.
Autômatos com pilha escolhem uma transição analisando o símbolo atual na cadeia de entrada, o
estado atual e o topo da pilha. Máquinas de estados finitos convencionais apenas analisam o
símbolo na cadeia de entrada e o estado atual. Autômatos com pilha adicionam a pilha como
recurso auxiliar, deste modo, dado um símbolo da cadeia de entrada, o estado atual e um símbolo
no topo da pilha, uma transição é selecionada.
Máquinas de estados finitos apenas escolhem um novo estado como resultado da sua transição,
já os autômatos com pilha também podem manipular a pilha, como resultado de sua transição. A
manipulação é feita através do desempilhamento de um símbolo da pilha ou através do
empilhamento de um novo símbolo ao topo da mesma. Alternativamente, um autômato com pilha
pode ignorar a pilha e deixá-la como está.
Os autômatos com pilha compreendem a classe das linguagens livres de contexto, de acordo
com a Hierarquia de Chomsky e, portanto, são modelos de computação equivalentes às
gramáticas livres de contexto.
Um autômato finito com acesso a duas pilhas possui capacidade de computação equivalente ao
de uma máquina de Turing.
Fonte: AUTÔMATO com pilha. Wikiwand, [s. d]. Disponível em:
https://www.wikiwand.com/pt/Aut%C3%B4mato_de_pilha. Acesso em: 05 ago. 2023.
Considerando as informações, avalie afirmações abaixo:
I. Os autômatos de pilha são simplesmente um autômato não-determinístico aumentado com uma
"memória de pilha externa". 
II. Um autômato não-determinístico pode colocar um elemento no topo da pilha e retirar um
12/06/2024, 09:21Atividade 2: Linguagens Formais e Autômatos
Página 6 de 10https://famonline.instructure.com/courses/35817/quizzes/177188
 I e IV.
 II e IV.
 II, III e IV.
 I e II.
Correto!
 I e III.
A alternativa está correta.
A afirmação I está correta, pois os autômatos de pilha são simplesmente um autômato não-
determinístico aumentado com uma "memória de pilha externa". A adição de pilha é usada para
fornecer um recurso de gerenciamento de memória último a entrar, primeiro a sair para autômatos
de pilha.
A afirmação II está incorreta, pois é um autômato não-determinístico que pode colocar um
elemento no topo da pilha e retirar um elemento do topo da pilha. Para ler um elemento na pilha,
os elementos superiores devem ser removidos.
A afirmação III está correta, pois um autômato de pilha é mais poderoso que um autômato finito.
Qualquer linguagem que possa ser aceita pelo autômato finito também pode ser aceita pelo
autômato de pilha.
A afirmação IV está incorreta, pois é o autômato de pilha que aceita uma classe de linguagem que
nem mesmo pode ser aceita pelo autômato finito. Assim, o autômato de pilha é muito mais
superior ao autômato finito.
 
Pergunta 4
0 / 0,2 pts
elemento do topo da pilha.
III. Qualquer linguagem que possa ser aceita pelo autômato finito também pode ser aceita pelo
autômato de pilha.
IV. Um autômato finito é superior ao autômato de pilha, pois o primeiro aceita uma classe de
linguagem que nem mesmo pode ser aceita pelo segundo. 
É correto apenas o que se afirma em:
Leia o texto a seguir:
[...] Equivalência entre AFD e AFN – Embora um AFN seja somente um acréscimo ao AFD, na
12/06/2024, 09:21Atividade 2: Linguagens Formais e Autômatos
Página 7 de 10https://famonline.instructure.com/courses/35817/quizzes/177188
 I e III, apenas.
Resposta correta
 II e III, apenas.
 I e II, apenas.
Você respondeu
 II, apenas.
 III, apenas.
A alternativa está incorreta. É correto o que se afirma em II e III, apenas.
verdade não aumenta seu poder computacional, sendo assim, para cada AFN é possível construir
um AFD equivalente que realiza o mesmo processamento. O contrário também é verdadeiro.
Autômato Finito com Movimentos Vazios – Movimentos vazios constituem uma generalização dos
modelos de máquinas não determinísticas, é um movimento determinado por uma simples
mudança de estado. Uma das vantagens dos autômatos Finitos com Movimentos Vazios no
estudo das linguagens Formais é o fato de facilitar algumas construções e demonstrações
relacionadas com os autômatos.
Equivalência entre AFN e AFe – Analogamente ao não-determinístico, os movimentos vazios não
aumentam o poder computacional dos autômatos finitos. Assim, para cada AFe, é possível
construir um AFN que realiza o mesmo processamento. O contrário é trivialmente verdadeiro [...].
Fonte: LINGUAGENS formais e autômatos 2. Tribo do C.I., 30 nov. 2010. Disponível em:
https://tribodoci.net/artigos/linguagens-formais-automatos-2/. Acesso em: 05 ago. 2023.
Considerando as informações acima, avalie as afirmações a seguir:
I. Um Autômato Finito Determinístico ε, ou Autômato Finito não-Determinístico épsilon é o
autômato que contém movimentos épsilon ou movimentos chamados nulos, pois autômatos
finitos determinísticos são autômatos finitos com zero.
II. A palavra vazia ε é aceita por um Autômato Finito não Determinístico se houver um
estado inicial que também é um estado final, pois quando uma máquina AFN está em um
determinado estado e lê um símbolo, a máquina poderá escolher para onde ir em seguida.
III. Para remover o movimento nulo e convertê-lo em AFN, devemos primeiramente
considerar os dois vértices tendo o movimento épsilon, pois tanto para AFDs quanto para
AFNs, deve-se ler um símbolo para que a máquina faça um movimento.
É correto o que se afirma em:
12/06/2024, 09:21Atividade 2: Linguagens Formais e Autômatos
Página 8 de 10https://famonline.instructure.com/courses/35817/quizzes/177188
A afirmação I está incorreta, pois é um Autômato Finito não Determinístico ε (ou AFN épsilon) que
é o autômato que contém movimentos épsilon ou movimentos nulos. Não um AFD. Além disso,
são os Autômatos Finitos não Determinísticos que são autômatos finitos com zero, um ou mais
movimentos de um determinado estado em um determinado símbolo de entrada.
A afirmação II está correta, pois a palavra vazia ε é aceita por um Autômato Finito não
Determinístico se houver uma caminhada produtiva vazia, ou seja, se houver um estado inicial
que também é um estado final. Outro ponto crucial é que quando uma máquina AFN está em um
determinado estado e lê um símbolo, ela poderá escolher para onde ir em seguida. Mas pode
haver estados nos quais depois de ler um dado símbolo a máquina não tem para onde ir.
A afirmação III está correta, pois para remover o movimento épsilon ou movimento nulo e
convertê-lo em AFN, devemos primeiramente considerar os dois vértices tendo o movimento
épsilon. É sabido que tanto para AFDs quanto para AFNs, deve-se ler um símbolo para que a
máquina faça um movimento. Isso ocorre, pois em Autômatos Finitos não Determinísticos com
movimentos vazios podem ocorrer movimentos sem a leitura de um símbolo da fita lida. Tal
movimento é chamado de transição ε.
 
Pergunta 5
0 / 0,2 pts
Leia o texto a seguir:
Um autômato é uma máquina que possui um número finito de estados.
Dois autômatos são equivalentes se satisfizerem as seguintes condições: 
1. Os estados inicial e final de ambos os autômatos devem ser os mesmos.
2. Cada par de estados escolhido é de um autômato diferente apenas.
3. Ao combinar os estados com os alfabetos de entrada, os resultados do par devem ser ambos
os estados finais ou intermediários (ou seja, ambos devem estar no estado final ou no estado não
final).
4. Se o par resultante tiver diferentes tipos de estados, ele será não equivalente. (ou seja, um
encontra-se no estado final e o outro no estado intermediário).
Exemplo 1 - Considere dois autômatos diferentes mostrados abaixo na Figura 1.
 
12/06/2024, 09:21Atividade 2: Linguagens Formais e Autômatos
Página 9 de 10https://famonline.instructure.com/courses/35817/quizzes/177188
Respostacorreta
 I, II e III, apenas.
 II e IV, apenas.
Você respondeu
Fonte: EQUIVALÊNCIA de FSA (Autômatos de Estados Finitos). Acervo Lima, [s.d.]. Disponível em:
https://acervolima.com/equivalencia-de-fsa-automatos-de-estados-finitos/. Acesso em: 04 ago. 2023.
Considerando as informações apresentadas, avalie as afirmações abaixo:
I. Dois autômatos A e B são ditos equivalentes se ambos aceitam exatamente o mesmo conjunto
de strings de entrada.
II. Para criar um Autômato Finito Determinístico, devemos criar um estado para representar todas
as combinações de estados que o Autômato Finito não Determinístico pode inserir.
III. Um Autômato Finito só pode contar onde diferentes estados correspondem a diferentes
valores do contador com um número finito de cenários de entrada.
IV. A característica definidora dos Autômatos Finitos não Determinísticos é que eles têm um
número infinito de estados.
 
É correto o que se afirma em:
12/06/2024, 09:21Atividade 2: Linguagens Formais e Autômatos
Página 10 de 10https://famonline.instructure.com/courses/35817/quizzes/177188
 I e II, apenas.
 III e IV, apenas.
 I, III e IV, apenas.
A alternativa está incorreta. É correto o que se afirma em I, II e III, apenas.
A afirmação I está correta, pois dois autômatos, no caso, A e B, são ditos equivalentes se ambos
aceitam exatamente o mesmo conjunto de strings de entrada.
A afirmação II está correta, pois, para criar um Autômato Finito Determinístico que aceite as
mesmas strings de um Autômato Finito não Determinístico, devemos criar um estado para
representar todas as combinações de estados que o Autômato Finito não Determinístico pode
inserir.
A afirmação III está correta, pois um Autômato Finito só pode contar, ou seja, manter um
contador, onde diferentes estados correspondem a diferentes valores do contador com um
número finito de cenários de entrada.
A afirmação IV está incorreta, pois a característica definidora dos Autômatos Finitos é que eles
têm apenas um número finito de estados.
Pontuação do teste: 0,4 de 1