Aula 1 - Autômatos finitos determinísticos

Prévia do material em texto

Aula 1 - Autômatos finitos determinísticos 
1.Os autômatos, ou máquinas de estados, são abstrações matemáticas para representar 
modelos computacionais. Esses modelos computacionais possibilitam a idealização de 
computadores, podendo representar linguagens complexas, tais como as recursivas e 
recursivamente enumeráveis às simples linguagens regulares. Um dos tipos de 
autômatos usados para reconhecer a linguagem regular é o AFD, marcado fortemente 
por seu determinismo. 
Assinale a alternativa correta acerca do significado de determinismo usado pelo AFD. 
 
a) É a capacidade que um autômato finito tem de chegar a dois estados diferentes 
por meio da transição espontânea épsilon, sendo essa transição determinante 
no estado de aceitação. 
 
b) É a capacidade que um autômato finito com estado finito tem de assegurar que 
pode ou não utilizar um símbolo, ficando a cargo do estado não consumir todos 
os símbolos do alfabeto, sendo o consumo dos símbolos optativo. 
 
c) É a capacidade que um autômato com estados finitos e predefinidos estabelece 
a partir de seus estados iniciais de alcançar o único estado de aceitação possível, 
caracterizando o determinismo. 
 
d) É a capacidade que um autômato finito tem de gerar um único ramo de 
computação para cada cadeia de entrada fornecida. Esse autômato pode ser 
expressado por meio da quíntupla da formalização. 
 
e) É a capacidade que um autômato finito tem de realizar sua computação na 
função programa por meio de três estados iniciais e dois estados de aceitação, 
sendo esta a quantidade mínima de estados apropriados. 
 
2. O diagrama de estados usado no AFD é um recurso gráfico muito expressivo para 
representar muitas máquinas, entre elas as máquinas de estados finitas. Com esse 
diagrama, é possível estabelecer a transição de um estado para outro por meio do 
consumo dos símbolos disponíveis no alfabeto em questão. A seguir, são informados 
detalhes sobre um diagrama de estados: 
 
Q = {q0, q1, q2, q3, q4, q5}, 
Σ = {0, 1}, 
Função programa = { 
δ(q0, 0) = q5, δ(q0, 1) = q1, 
δ(q1, 0) = q2, δ(q1, 1) = q5, 
δ(q2, 0) = q5, δ(q2, 1) = q3, 
δ(q3, 0) = q4, δ(q3, 1) = q5, 
δ(q4, 0) = q4, δ(q4, 1) = q4, 
δ(q5, 0) = q0, δ(q5, 1) = q0 
} 
q0 é q0. 
F = { q0, q4} 
 
De acordo com as informações, indique qual diagrama corresponde às especificações 
descritas. 
a) 
 
b) 
 
c) 
 
 
 
d) 
 
 
e) 
 
3. O diagrama de estados usado no AFD é um recurso gráfico muito expressivo para 
representar muitas máquinas, entre elas as máquinas de estados finitas. Com esse 
diagrama, é possível estabelecer a transição de um estado para outro por meio do 
consumo de todos os símbolos disponíveis no alfabeto usado em determinada 
linguagem. A seguir, é esboçado o diagrama 2. Determine a linguagem L(M2) aceita pelo 
AFD M2 representado no diagrama. 
 
A. L(M2) = {w ∈ (0, 1)* | w é formada por uma cadeia de comprimento ímpar e 
contendo sequencialmente 0s e 1s}. 
B. L(M2) = {w ∈ (0, 1)* | w é formada por uma cadeia de comprimento ímpar, tendo 
0 no meio e terminando em 1}. 
C. L(M2) = {w ∈ (0, 1)* | w é formada por um cadeia que deve ter uma sequência 
mínima de três 1s consecutivos}. 
D. L(M2) = {w ∈ (0, 1)* | w é formada por uma cadeia que deve ter uma sequência 
mínima de quatro 1s consecutivos}. 
E. L(M2) = {w ∈ (0, 1)* | w é formada por uma cadeia que deve ter uma sequência 
mínima de cinco 1s consecutivos}. 
4. A formalização do autômato finito deteminístico (AFD) fornece a precisão e a notação 
para representar esse tipo de modelo computacional (AFD). No AFD, sua formalização 
pode ser expressada por meio da 5-upla (Q, Σ, δ, q0, F). A seguir, é esboçado o diagrama 
que reconhece a linguagem L(M3). 
 
Leia as afirmativas a seguir a respeito dos componentes da formalização do AFD: 
I. Esse AFD tem Q = {q0, q1, q2, q3, q4}, F = {q1, q3} e Σ = {p, a, i}. 
II. Esse AFD tem Q = {q0, q1, q2, q3, q4}, F = {q3}, δ(q0, a) = q0. 
III. Esse AFD tem Q = {q0, q1, q2, q3, q4}, F = {q3}, Σ = {p, i}, q0 = q1. 
IV. Esse AFD tem Q = {q0, q1}, F = {q2} e Σ = {p, a, i}, δ(q2, a) = q2, δ(q2, p) = q2. 
V. Esse AFD tem Q = {q0, q1, q2, q3, q4}, Σ = {p, a, i}, δ(q0, i) = q0. 
Assinale a alternativa que contém as assertivas corretas: 
A. I e IV. 
B. I e V. 
C. I, II e III. 
D. II e III. 
E. E. II e V. 
 
5. Em AFDs, pode haver muitas soluções para o mesmo problema, incluindo aquelas 
soluções com muitos estados. Ao implementar um AFD, uma pergunta pertinente que 
se deve fazer é se o AFD foi construído com o menor número possível de estados. Com 
isso, é apropriada a utilização do algoritmo de minimização de autômatos. 
Analise as afirmativas a seguir, que tratam das características do algoritmo de 
minimização de autômatos, e classifique-as em verdadeiras (V) ou falsas (F): 
( ) Neste algoritmo, os estados finais e os não finais são separados na primeira interação, 
depois são unidos, chegando a ser indissolúveis. 
( ) Os estados equivalentes são aqueles que, ao consumirem um símbolo, vão ter 
comportamentos de aceitação/rejeição idênticos. 
( ) O algoritmo procura uma partição, de forma que os estados não equivalentes estejam 
no mesmo bloco. 
( ) A minimização do autômato finito une os estados equivalentes entre si, alterando e 
aperfeiçoando o funcionamento do autômato. 
Assinale a alternativa que apresenta a ordem correta: 
a) F, V, F, V. 
b) F, V, F, F. 
c) V, F, V, V. 
d) V, F, F, V. 
e) F, V, V, F.