[LFA] Questionário

Prévia do material em texto

QUESTIONÁRIO – AV1 – PARTE 1 (40 QUESTÕES)
CONCEITOS BÁSICOS:
1). O que define uma linguagem formal (LF)? Exemplifique um LF.
Entende-se por linguagem formal o estudo de modelos matemáticos que possibilitam a especificação e o reconhecimento de linguagem (no sentido amplo da palavra), suas classificações, estruturas, propriedades, características e inter-relacionamentos.
Ou um conjunto infinito de cadeias de tamanho finito composto por um determinado alfabeto.
As seguintes regras descrevem uma linguagem L formal sobre o alfabeto Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, =}:
Cada cadeia não vazia que não contém "+" ou "=" e não começa com "0" está em L.
Uma sequência contendo "=" está em L se e somente se há exatamente um "=", e ela separa duas cadeias válidas de L.
Uma sequência contendo "+", mas não "=" está em L se e somente se todos os "+" na cadeia separam duas cadeias válidas de L.
Nenhuma cadeia está em L que não as sugeridas pelas regras anteriores.
Sob essas regras, a cadeia "23 +4 = 555" está em L, mas a cadeia "= 234 = +" não está. Esta linguagem formal expressa números naturais, declarações adição bem formadas, e igualdades adição bem formadas, mas estas exprimem apenas o que elas se parecem (sua sintaxe), não o que eles querem dizer (semântica). Por exemplo, em nenhuma parte destas regras existe qualquer indicação de que "0" significa o número zero, ou que "+" significa adição.
2). Qual o significado da equivalência entre linguagens, gramaticas e autômatos?
3). Qual a relação entre grafos e autômatos? Como um autômato poderia ser categorizado?
O relacionamento se dá pois os dois fazem as relações entre os objetos de um determinado conjunto. São geralmente representados graficamente da seguinte maneira: é desenhado um círculo para cada vértice, e para cada aresta é desenhado um arco conectando suas extremidades. 
Um autômato pode ser categorizado como:
AFD – Autômato finito determinístico.
AFN – Autômato finito não determinístico.
AFNe – Autômato finito não determinístico com epsilon transição
AFNE – Autômato finito não determinístico estendido.
ADP – Autômato de pilha
4). Qual a relação entre os conceitos de autômatos, arquiteturas computacionais e linguagens de programação?
Todos lidam com definições e propriedades de modelos matemáticos (formais) de computação.
5). Como garantir a equivalência de linguagens?
Testar palavras em ambas linguagens e verificar se são aceitas.
Criar dois AFDs e verificar se ambos aceitam a mesma linguagem.
6). O que são linguagens ambíguas? Qual o seu problema?
7). Qual a importância das LR’s?
Linguagens regulares são aquelas que podem ser geradas a partir de linguagens finitas pela aplicação de operações regulares. É uma linguagem formal que pode ser expressa usando expressões regulares, ou seja, uma linguagem produzida utilizando as operações de concatenação, união e fecho de Kleene sobre os elementos de um alfabeto. 
As linguagens regulares são utilizadas para descrever dispositivos que realizam computações simples, como os autômatos finitos, pois representam a linguagem mais elementar classificada pela hierarquia de Chomsky que não requer memória para ser reconhecida.
8). Defina o conceito de alfabeto, palavra e linguagem.
Alfabeto: É qualquer conjunto finito, não vazio, de símbolos (ou letras). Geralmente é denotado por Σ.
Exemplos:
Σ = {a,b,c,…,z} (Alfabeto das letras minúsculas )
Σ = {0,1} (Alfabeto binário)
Palavra: É qualquer sequência finita de símbolos de um alfabeto Σ. E pode existir a palavra vazia que contém zero ocorrências de símbolos e é habitualmente denotada por ε.
Linguagem: É uma forma de comunicação. Podemos definir uma linguagem como sendo "um conjunto de elementos (símbolos) e um conjunto de métodos (regras) para combinar estes elementos, usado e entendido por uma determinada comunidade".
9). Quais as principais operações sobre uma palavra? Exemplifique.
Concatenação: É uma operação binária que tem a finalidade de agregar duas palavras e gerar uma nova palavra.
Exemplo:
Σ = {a,b} 
Palavras: x = baaa e y = abab
Xy = baaaabab
Concatenação sucessiva: Representa concatenar repetidamente a própria palavra.
Exemplo:
Palavras: x = ab
Notação: x² = abab
10). O que é uma matriz de transição (ou função de transição)?
Uma função de transição é uma matriz na qual as colunas representam os estados do autômato e as linhas os símbolos do alfabeto. Cada entrada na matriz indica qual o estado final de uma transição a partir do estado indicado na coluna através do símbolo indicado na linha. Ou seja, é a especificação de uma possibilidade de movimentação entre uma configuração e outra.
11). Por que matrizes de transição são finitas?
12). O que é um autômato e qual sua importância?
A máquina responsável pelo comando dos sistemas automatizados.
Autômatos lidam com definições e propriedades de modelos matemáticos (formais) de computação.
Autômatos são essenciais para o estado dos limites de computação. Existem duas questões importantes: o que um computador pode fazer (decidibilidade) e o que um computador pode fazer de forma eficiente (intratabilidade).
Abrange aspectos teóricos vinculados à classificação e a formalização das linguagens estruturadas, bem como a análise de suas características e exemplos. 
13). Explique formalmente os parâmetros que definem o conceito de autômatos.
Alfabetos: é um conjunto de símbolos finito e não-vazio
String: é uma sequência finita de símbolos escolhidos de algum alfabeto
Linguagens: um conjunto de strings, todos escolhidos de algum algum ∑*, onde ∑ é um alfabeto específico.
Problemas: é a questão de decidir se um dado string é elemento de alguma linguagem específica
14). Exemplifique as quíntuplas que definem um AFD.
Q = conjunto finito de estados
Σ = Alfabeto (finito e não vazio) de entrada
δ = Função de transição Q x Σ -> Q
i (q0) = Estado inicial, q0 ∈ Q
F = Conjunto de estados finais
Exemplo: Seja M um autômato finito determinístico, sua representação é:
Q = {q0, q1, q2, q3}
Σ = {0, 1, 2}
δ = {δ(q0, 0)->q0, δ(q0, 1)->q1, δ(q0, 2)->q3, δ(q1, 0)->q3, δ(q1, 1)->q1, δ(q1, 2)->q2, δ(q2, 0)->q3, δ(q2, 1)->q3, δ(q2, 2)->q2, δ(q3, 0)->q3, δ(q3, 1)->q3, δ(q1, 2)->q3}
i = q0
F = {q1, q2}
15). Por que autômatos possuem apenas um estado inicial e qual o motivo pelo qual podem existir mais de um estado final?
Só tem um inicial pois precisa ser bem definido, não há como decidir como começar se houver mais de um estado inicial.
Há um conjunto de estados finais para tratar todas as palavras aceitas por aquele autômato.
16). Monte um algoritmo para simular um AFD.
17). Quando dois AFDs são considerados equivalentes?
Se as linguagens aceitas por ambos forem iguais.
18). Quando um AFD e considerado mínimo e qual a sua importância?
É considerado mínimo se não conter estados inúteis e não conter estados distintos equivalentes.
O objetivo da minimização é criar um autômato irredutível, mais eficiente, menor.
19). Nos cenários de AFD e AFN, explique o que significa reconhecer uma palavra.
Significa que a partir de um estado inicial todos os símbolos são reconhecidos e levam a um estado final válido.
20). O que são e-transições? De um exemplo.
É a função de transição definida para aceitar ɛ (ausência de símbolos)
21). Qual o conceito de um AFNE (estendido)? Qual a sua vantagem? Exemplifique.
Função de Transição Estendida é uma função que toma um estado q e um string w e retorna um estado p – o estado que o autômato alcança quando começa no estado q e processa a sequência de entradas w. A função de transição estendida é normalmente denotada por δ, δ* ou ainda δ com acento circunflexo. 
A grande vantagem para um AFNE é que se consegue montar uma matriz de transição baseada em valores de entradas como string e não caractere a caractere da palavra.
Exemplos: funções de transição estendida para cada prefixo da string 11010 com o autômato que aceita strings que contem 01 como substring:
δ(q0,11010) = δ(δ(q0,1),1010)= δ(q0,1010) = δ(δ(q0,1),010) = δ(q0,010) = δ(δ(q0,0),10) = δ(q2,10) = δ(δ(q2,1),0) = δ(q1,0) = q1
22). Qual a relação de transformação entre AFD, AFN, AFN-e e AFNE? Explique.
Como cada autômato é mais simplificado que o outro dá para ir fazendo as transformações até chegar no mais complexo.
Para realizar a transformação entre os autômatos basta:
1. Montar a matriz de transição do autômato atual.
2. Combinar os estados da matriz de transição
3. Refazer o autômato com a nova matriz combinada.
4. Simplificar o autômato.
23). Descreva o algoritmo para transformar um AFN em AFD.
24). Descreva o algoritmo para transformar um AFNe em AFN.
25). Descreva o algoritmo para transformar um AFNE em AFNe.
DEMONSTRAÇÕES:
26). Prove que n é par se n² é par ( e vice-versa).
N é par -> N é da forma 2x
N = 2x
N² = (2x)² = 4x² = 2(2x²)
27). Monte a FSM (MEF – Maquina de Estado Finito) para o problema de uma máquina de chá(1,00) e café (0,50) que aceita somente moedas e devolve o troco.
28). Monte um FSM para modelar o funcionamento de um elevador em um prédio de 3 andares. Apesente as transições.
Transições:
	
	1
	2
	3
	Q1
	Q1
	Q2
	Q3
	Q2
	Q1
	Q2
	Q3
	Q3
	Q1
	Q2
	Q3
29). Para dois AFDs M1 e M2, mostre que existem AFDs para L(M1)’, L(M1)+L(M2), L(M1)&L(M2).
30). Prove que se um AFD reconhece uma linguagem infinita, o FSM simplificado deve conter algum ciclo.
31). Monte os diagramas de um AFD e de um AFN para reconhecer a seguinte linguagem: L=(0,1)*1010.
32). Monte os diagramas de um AFD e de um AFN para reconhecer a seguinte linguagem: L=(0,1)*1(0,1)(0,1).
33). Qual o número de prefixos, sufixos e subpalavras de uma palavra de tamanho n?
34). O conjunto de ancestrais de um individuo é finito ou infinito? Forneça pistas para esta prova (argumento).
35). O conjunto de todas as palavras de um alfabeto é finito ou infinito? E se o alfabeto for unário?
37). Prove que a linguagem dada por todas as palavras binárias que possuem um substring “111” é regular.
38). Demonstre que a linguagem dada por L=anbn não é regular.
39). O conjunto de todas as funções nos naturais é enumerável? Prove.
40). Dado um alfabeto A qualquer, mostre que A* é enumerável, mas P(A) não é.