Teste_ Atividade 2 - Limguagem formais (1)

Prévia do material em texto

13/10/2023, 10:52 Teste: Atividade 2
https://famonline.instructure.com/courses/31552/quizzes/158006/take 1/8
Atividade 2
Iniciado: 12 out em 14:15
Instruções do teste
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.
0,2 ptsPergunta 1
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 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
A+
A
A-
13/10/2023, 10:52 Teste: Atividade 2
https://famonline.instructure.com/courses/31552/quizzes/158006/take 2/8
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
que valida entradas de usuário.
que deve ser implementada somente via software.
que se refere à unicidade do processamento.
entendida como conceito abstrato.
que é área importante na teoria dos autômatos.
0,2 ptsPergunta 2
Leia o texto a seguir:
[...] Equivalência entre AFD e AFN – Embora um AFN seja somente um acréscimo
ao AFD, na 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
A+
A
A-
13/10/2023, 10:52 Teste: Atividade 2
https://famonline.instructure.com/courses/31552/quizzes/158006/take 3/8
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:
I e III, apenas.
I e II, apenas.
II e III, apenas.
III, apenas.
II, apenas.
0,2 ptsPergunta 3
Leia o trecho abaixo:
A+
A
A-
13/10/2023, 10:52 Teste: Atividade 2
https://famonline.instructure.com/courses/31552/quizzes/158006/take 4/8
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 é:
A+
A
A-
13/10/2023, 10:52 Teste: Atividade 2
https://famonline.instructure.com/courses/31552/quizzes/158006/take 5/8
 
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:
Autômatos Finitos não Determinísticos, ou Máquinas de Estados Finitos,do inglês, são usados na modelagem de processos.
Os Autômatos Finitos não Determinísticos (AFD) são os tipos que
conseguem identificar as linguagens racionais de forma precisa.
São as transições de um autômato que definem seu estado e isso ocorre
na interpretação da palavra de entrada.
Um autômato é denominado determinístico, pois é composto de memória
limitada.
Os AFN estão no nível mais alto de complexidade da hierarquia de
Chomsky, inclusive das máquinas de Turing.
0,2 ptsPergunta 4
Leia o texto a seguir:
A+
A
A-
13/10/2023, 10:52 Teste: Atividade 2
https://famonline.instructure.com/courses/31552/quizzes/158006/take 6/8
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.
 
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.
A+
A
A-
13/10/2023, 10:52 Teste: Atividade 2
https://famonline.instructure.com/courses/31552/quizzes/158006/take 7/8
 
É correto o que se afirma em:
I, II e III, apenas.
I e II, apenas.
III e IV, apenas.
II e IV, apenas.
I, III e IV, apenas.
0,2 ptsPergunta 5
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.
A+
A
A-
13/10/2023, 10:52 Teste: Atividade 2
https://famonline.instructure.com/courses/31552/quizzes/158006/take 8/8
Nenhum dado novo para salvar. Última verificação às 10:52 
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 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:
I e II.
II, III e IV.
II e IV.
I e IV.
I e III.
Enviar teste
A+
A
A-