LFA Lista de Exerc cios 2 Resolvida

Prévia do material em texto

Professor Me Paulo David Linguagens Formais e Autômatos 
Lista de Exercícios 2 
 
 
1) Observe as afirmativas a seguir, considerando a 
definição e o estudo de Autômatos com Pilha (AP) 
responda V para Verdadeiro e F para Falso. 
(V) Autômato com Pilha é um formalismo que pode ser 
aplicado no projeto sintático de linguagens 
computacionais. 
(V) A configuração de um Autômato com Pilha em um 
dado momento pode ser descrita por uma tripla <s, x, 
α> onde s é o estado corrente, x é a cadeia da fita que 
falta ser processada e α é o conteúdo da pilha, com o 
topo no início de α. 
(F) Autômatos com Pilha são mais poderosos do que 
Autômatos Finitos Não-Determinísticos (AFNDs) que, 
por sua vez, são mais poderosos que Autômatos 
Finitos Determinísticos (AFDs). 
(F) Pode-se afirmar que para uma cadeia ser 
reconhecida por um Autômato com Pilha, o 
processamento da mesma deve encerrar com um 
estado final ativo. 
 
2) Uma subpalavra é definida como qualquer sequência 
de símbolos contíguos da palavra. 
Represente (desenhe) o autômato que reconhece a 
linguagem {w ∈ {a, b}* | aaa é subpalavra de w}. 
Resposta: 
 
 
3) Considerando o alfabeto  = {a, b}, determine a 
linguagem que representa cada um dos autômatos 
finitos determinísticos (AFD) a seguir: 
a) 
 
Resposta: 
{b(ab)nb | n≥0}. 
 
b) 
 
Resposta: 
{b(a)nba | n≥0}. 
 
 
 
 
 
c) 
 
Resposta: 
{b(a)nb | n≥0}. 
 
d) 
 
Resposta: 
{a(ba)nb | n≥0}. 
 
e) 
 
Resposta: 
{a(a)nb(a)nb | n≥0}. 
 
4) Considerando o alfabeto  = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, 
determine a linguagem que representa cada um dos 
autômatos finitos determinísticos (AFD) a seguir: 
a) 
 
Resposta: 
{x ∈ + | a sequência descrita por x corresponda a um 
valor divisível por 5}. 
 
b) 
 
Resposta: 
{x ∈ + | a sequência descrita por x corresponda a um 
valor inteiro par}. 
 
 
 
 
 
Faculdade Maurício de Nassau 
Curso: Sistemas de Informação 
Disciplina: Linguagens Formais e Autômatos 
Professor MSc. Paulo David 
 
 Professor Me Paulo David Linguagens Formais e Autômatos 
 
c) 
 
Resposta: 
{x ∈ + | a sequência descrita por x corresponda a um 
valor inteiro ímpar}. 
 
5) Dado o AP a seguir: 
 
 
 
Dê a representação formal para o autômato P2, ou seja, 
indique todos os seus componentes (K, Σ, Γ, ∆, s, F). 
• K = {q0, q1, q2} 
• Σ = {0, 1} 
• Γ = {$, X} 
• ∆ = {1: ((q0, 0, ), (q0, X)), 2: ((q0, 1, X), (q1, 
)), 3: ((q1, 1, X), (q1, )), 4: ((q1, , $), (q2, $))} 
• s = {q0} 
• F = {q2} 
 
6) Uma expressão regular provê uma forma concisa e 
flexível de identificar cadeias de caracteres de 
interesse, como caracteres particulares, palavras ou 
padrões de caracteres. Considere a figura a seguir: 
 
 
 
Verifique para cada ER nos itens a seguir, se são 
equivalentes ao autômato apresentado no diagrama 
anterior. 
a) (ab)*(bb)*c 
b) (ab)*abc* 
c) abb*ccc 
d) ab(bb)*cc* 
e) a(ab)b*bc* 
 
7) Considerando o estudo de Autômatos Finitos com 
Saída, analise as afirmativas a seguir. 
I – A Máquina de Mealy é um Autômato Finito 
Determinístico com saídas associadas as transições. 
É um Autômato Finito modificado de forma a gerar 
uma palavra de saída para cada transição. 
II – A Máquina de Moore é um Autômato Finito 
Determinístico com saídas associadas aos Estados. 
Possui uma segunda função, que gera uma palavra de 
saída (que pode ser vazia) para cada estado da 
máquina. 
III – Tanto na máquina de Mealy quanto na máquina 
de Moore, a saída não pode ser lida, ou seja, não pode 
ser usada como memória auxiliar. 
 
Está correto o que se afirma em: 
a) I, apenas. 
b) II, apenas. 
c) I e II, apenas. 
d) I e III, apenas. 
e) I, II e III. 
 
8) O modelo matemático conhecido como Máquina de 
Turing, consiste basicamente de três partes: Fita, 
Unidade de Controle e Programa ou Função de 
Transição. Analise as afirmativas relativas as partes 
citadas. 
I – A Fita é usada simultaneamente como dispositivo 
de entrada, saída e memória de trabalho. 
II – A Unidade de Controle reflete o estado corrente da 
máquina. Possui uma unidade de leitura e gravação 
(cabeça da fita) a qual acessa uma célula da fita de 
cada vez e movimenta-se para a esquerda ou direita. 
III – O Programa ou Função de Transição é uma 
função que comanda as leituras e gravações, o 
sentido de movimento da cabeça e define o estado da 
máquina. 
 
Está correto o que se afirma em: 
a) I, apenas. 
b) II, apenas. 
c) I e II, apenas. 
d) I e III, apenas. 
e) I, II e III. 
 
9) Considerando o estudo e a definição de Autômatos 
com Pilha, analise as afirmativas a seguir. 
I – Uma definição afirma que o valor inicial da pilha é 
vazio e o autômato para aceitando ao atingir um 
estado final. 
II – Outra definição, afirma que a pilha contém, 
inicialmente, um símbolo especial denominado de 
símbolo inicial da pilha. Não existem estados finais e 
o autômato para aceitando quando a pilha estiver 
vazia. 
III – Estruturalmente, em Autômato com Pilha o último 
símbolo gravado é o primeiro a ser lido. 
 
Está correto o que se afirma em: 
a) I, apenas. 
b) I e II, apenas. 
c) II, apenas. 
d) I e III, apenas. 
e) I, II e III. 
 
 
10) Considerando o estudo de Linguagens e Autômatos 
Finitos, analise as afirmativas a seguir. 
I – Toda linguagem regular é livre de contexto, pois 
existe um corolário que afirma isso a partir do fato de 
que todo autômato finito é um autômato com pilha 
(que não usa a pilha). 
 
 Professor Me Paulo David Linguagens Formais e Autômatos 
II – Por definição, se uma linguagem é reconhecida 
por alguma máquina de Turing, ela é recursivamente 
enumerável. 
III – A linguagem aceita por um Autômato Finito Não-
Determinístico M = (, Q, , q0, F), denotada por L(M), 
é o conjunto de todas as palavras pertencentes a * 
aceitas por M, tais que existe pelo menos um caminho 
alternativo que aceita a palavra. 
 
Está correto o que se afirma em: 
a) I, apenas. 
b) II, apenas. 
c) I e II, apenas. 
d) I e III, apenas. 
e) I, II e III. 
 
11) Dado o Autômato com Pilha M = (, Q, , q0, F, V), 
representado na figura a seguir. (Obs: o símbolo ? 
representa vazio) 
 
 
Verifique quais das palavras a seguir são aceitas pelo 
autômato. 
a) abcba b) aabca c) abccba 
d) aabbcbbaa e) aabbccbbaa 
f) aabccbaa e) aaabbbcbbbaaa 
 
12) Relacione as colunas da direita e com a da esquerda, 
considerando o conjunto de definições importantes 
para o desenvolvimento da teoria de Linguagens 
Formais e Autômatos. 
1 Linguagem 
Formal 
(1) É um conjunto de 
palavras sobre um 
alfabeto. 
2 Concatenação (5) Pode ser visto como uma 
máquina composta, 
basicamente, de três 
partes: Fita, Unidade de 
Controle e Programa 
(Função de Transição). 
3 Monóide Livre (6) É um par ordenado (V, A), 
em que V denota o 
conjunto de vértices (ou 
nós) do grafo e A denota 
uma relação binária sobre 
V, através da qual são 
especificados os arcos do 
grafo. 
4 Sistema de 
Estados Finitos 
(2) É uma operação binária, 
definida sobre uma 
linguagem, a qual associa 
a cada par de palavras 
uma palavra formada 
pela justaposição da 
primeira com a segunda. 
5 Autômato Finito 
Determinístico 
(4) É um modelo matemático 
de sistema com entradas 
e saídas discretas. 
6 Grafo (3) O conjunto de todas as 
palavras sobre um 
alfabeto. 
 
13) Dado a Máquina de Turing M = 
({q0,q1,q2,q3,q4,q5},{a,b,c},{a,b,c,x,y,z,},,q0,{q5},), 
representado na figura a seguir, com: 
 
 
 
 
Marquea alternativa CORRETA. 
a) A Máquina de Turing reconhece a cadeia abbc. 
b) A Máquina de Turing reconhece a cadeia aabbc. 
c) A Máquina de Turing reconhece a cadeia abbccc. 
d) A Máquina de Turing reconhece a cadeia aabbcc. 
e) A Máquina de Turing reconhece a cadeia aaabc. 
 
14) Seja a função de transição f de uma MT não-
determinística M = ({qo,q1,q2}, {0,1}, {0,1,B}, f, qo, B, 
{q2}): 
 
f  0 1  
q0 (q0,,R) (q0,1,R) (q1,0,R)  
q1  (q1,0,R) 
(q0,0,L) 
(q1,1,R) 
(q0,1,L) 
(q2,,R) 
q2     
 
Represente graficamente a MT e verifique se as 
cadeias abaixo pertencem à linguagem aceita por M. 
a) 01 
b) 011 
c) 110 
 
Reposta: Reconhece todas