Autómatos Finitos — Exercícios

Os exercícios assinalados com “✓” serão resolvidos nas aulas práticas; Os assinalados com “†” têm elevada dificuldade. Todos os restantes devem ser resolvidos pelos alunos.

Autómatos Finitos Deterministas

Exercício 01

Para o AFD $A = \del{\set{q_0, q_1, q_2}, \set{a, b}, \delta, q_0, \set{q_2}}$ com a transição $\delta$ dada pela tabela

$$ \begin{array}{c|cc} \delta & a & b \cr \hline q_0 & q_0 & q_1 \cr q_1 & q_2 & q_1 \cr q_2 & q_2 & q_0 \end{array} $$

Desenhe o diagrama de estados.
Escreva as computações de $A$ para as palavras $abaa$ e $bbbabb$ referindo se são, ou não, aceites.
Escreva uma expressão regular que represente a linguagem reconhecida por $A$.

Exercício 02

AFD Exercício 02

Seja $A$ o AFD dado pelo diagrama acima.

Qual é o estado inicial, e quais são os estados finais?
As palavras $0001$, $010101$ e $001110101101$ são aceites?
Que palavras de $\del{01}^\ast$ estão em $L(A)$?

Exercício 03

Seja $A = \del{\set{0, 1, 2}, \set{x, y}, \set{\del{0,x,1}, \del{0,y,0}, \del{1,x,1}, \del{1,y,2}, \del{2,x,1}, \del{2,y,0}}, 0, \set{0}}$ um AFD.

desenhe o diagrama de estados
✓ escreva uma expressão regular que represente a linguagem reconhecida por $A$
✓ repita a alínea anterior para o AFD $A’$ que apenas difere de $A$ no conjunto dos estados de aceitação, que no caso de $A’$ é $\set{0, 1}$

Exercício 04

Construa um autómato finito determinista que reconheça a linguagem das palavras…

sobre $\set{a, b, c}$ em que todos os $a$’s precedem todos os $b$’s que, por sua vez, precedem todos os $c$’s (donde que todos os $a$’s precedem todos os $c$’s), podendo não haver nem $a$’s, nem $b$’s, nem $c$’s.
sobre $\set{a, b}$ que não têm $aa$ como subpalavra.
sobre $\set{a,b,c}$ em que cada $b$ é seguido imediatamente por $cc$.
não vazias sobre $\set{a,b}$ em que o número de $a$’s é divisível por $3$.

Exercício 05

Construa um autómato finito determinista que reconheça a linguagem da ER $(ab)^\ast(ba)^\ast$.

Exercício 06

Calcule ER das linguagens reconhecidas pelos autómatos seguintes.


a)		b)

c)		d)

e)

Exercício 07

Encontre um AFD que aceite a linguagem das palavras em $\del{0 \cup 1}^\ast$…

com prefixo $01$.
com subpalavra $00101$.
expansões binárias dos naturais congruentes zero módulo $5$.
com subpalavra $00$ e sufixo $01$.
com subpalavra $00$ e não têm sufixo $01$.
em que cada bloco de quatro letras consecutivas contém $01$.

Exercício 08

Encontre um AFD que aceite a linguagem das palavras…

com prefixo $010$.
com sufixo $101$.
com subpalavra $010$ ou $101$.
em que as últimas cinco letras têm três $0$s.
$w$ tais que $\len{w}_1 + 2\len{w}_0$ é múltiplo de cinco.
sobre o alfabeto $\set{1,2,3}$ onde a soma dos símbolos é múltiplo de cinco.

Computação Não Determinista

Exercício 09

Determine a linguagem (ER) dos AFND acima.


a)	b)	c)

Considere a linguagem de todos os números inteiros sem sinal, escritos em base $3$, em que o último algarismo ocorre anteriormente no número. Por exemplo, $1202$ e $00$ pertencem a esta linguagem, mas $1002$ e $1$ não. (Os números escritos em base $3$ só podem ter os algarismos $0, 1$ e $2$.)

escreva uma expressão regular que a represente.
defina um autómato finito que a reconheça.
$\dagger$ apresente um autómato finito determinista que a reconheça (Sugestão: tente construí-lo diretamente, sem recorrer a qualquer algoritmo).

Exercício 11

Considere o autómato definido no diagrama acima.

Calcule o $\fecho\at{\set{0}}$ e o $\fecho\at{\set{1,2,3}}$.
Calcule $\delta\at{\set{0},0}$ e $\delta\at{\set{2,3},1}$.
Desenhe as árvores das computações de $011$ e $101$, indicando se são aceites ou rejeitadas.

Exercício 12

Seja $A = \del{\set{0,1,2}, \set{a,b,c}, \delta, 0, \set{1,2}}$ um autómato finito não determinista cuja função de transição é

$$ \begin{array}{c|cccc} \delta & a & b & c & \nil \cr \hline 0 & \set{0} & & \set{1} & \set{2} \cr 1 & & & \set{1} \cr 2 & & \set{1,2} \end{array} $$

Construa um autómato finito determinista equivalente a $A$, usando o algoritmo dado nas aulas, e apresente uma ER que represente a linguagem por ele reconhecida.

Exercício 13

✓ Repita o exercício anterior para o autómato finito não determinista $$B = \del{\set{0,1,2,3}, \set{m,n}, \delta, 0, \set{1}}$$ cuja função de transição é

$$ \begin{array}{c|ccc} \delta & m & n & \nil \cr \hline 0 & \set{1} & \set{2} & \set{1} \cr 1 & & \set{1,3} \cr 2 & & & \set{3} \cr 3 & \set{1,3} & \set{2} \end{array} $$

Exercício 14

✓ Considere a linguagem de todas as palavras sobre $\set{a,b}$ em que o antepenúltimo símbolo é $b$.

defina um autómato finito (não determinista) que reconheça esta linguagem.
aplicando o algoritmo dado nas aulas, construa um autómato finito determinista equivalente ao autómato finito da alínea anterior.

Exercício 15

$\dagger$ Repita o exercício anterior para a linguagem de todas as palavras sobre $\set{a,b}$ em que o terceiro e o antepenúltimo símbolos são $b$. São exemplos de palavras que pertencem a esta linguagem as palavras $aababaa$, $abbbbbbbb$, $abba$ e $bbb$.

Exercício 16

Sejam $A_1 = \del{Q_1, T, \delta_1, q_{01}, F_1}$ e $A_2 = \del{Q_2, T, \delta_2, q_{02}, F_2}$ dois autómatos finitos tais que $Q_1$ e $Q_2$ são disjuntos. Defina um autómato finito $B$ tal que $L\at{B} = L\at{A_1} \cup L\at{A_2}$.

Exercício 17

Defina um AFD equivalente ao AFND

$$N=\del{\set{p,q,r},\set{0,1},\delta,p,\set{q,r}}$$

em que

$$ \begin{array}{c|cc} \delta & 0 & 1 \cr \hline p & \set{p,q} & \set{p} \cr q & \emptyset & \set{r} \cr r & \emptyset & \emptyset \end{array} $$

Minimização e Composição de AFD

Exercício 18

✓ Aplicando o algoritmo dado nas aulas, construa o autómato finito determinista mínimo equivalente a $A = \del{\set{A,B,C,D,E,F}, \set{a,b}, \delta, A, \set{B,D}}$, com a função de transição

$$ \begin{array}{c|cc} \delta & a & b \cr \hline A & B & E \cr B & E & C \cr C & D & F \cr D & F & C \cr E & F & F \cr F & E & F \end{array} $$

e apresente uma expressão regular que represente $L\at{A}$.

Exercício 19

Considere o autómato finito não determinista $A = \del{\set{1,2,3,4,5}, \set{x,y}, \delta, 1, \set{5}}$, com a função de transição

$$ \begin{array}{c|cc} \delta & x & y \cr \hline 1 & \set{1} & \set{1,2} \cr 2 & \emptyset & \set{3} \cr 3 & \set{3} & \set{3,4} \cr 4 & \emptyset & \set{5} \cr 5 & \set{5} & \set{5} \end{array} $$

construa o AFD equivalente a $A$.
construa o AFD mínimo equivalente a $A$.

Exercício 20

✓ Considere a linguagem representada por $(aaa)^\ast$ reunida com $(aa)^\ast$.

defina um autómato finito (não determinista) que reconheça aquela linguagem.
construa um AFD equivalente ao autómato finito definido na alínea anterior.
construa um AFD mínimo equivalente ao AFD obtido na alínea anterior.

Exercício 21

Repita o exercício anterior para a linguagem das palavras sobre $\set{a,b,c}$ que têm $ababc$ como subpalavra.

Exercício 22

✓ Construa um AFND que aceita a linguagem das palavras

binárias com, pelo menos, três ocorrências de $010$;
binárias com subpalavras $010$ e $101$;
binárias (com subpalavra $010$ ou $101$) e (com sufixo $111$ ou $000$);
binárias em que o $3n$-ésimo símbolo é $0$, para $n\geq 1$;
binárias, de tamanho $3n$, e em que, para cada $1\leq k \leq n$, algum dos $3k-2$, $3k-1$ ou $3k$-ésimo símbolo é $0$;
$0^n 1 0^m 1 0^q$ em que $q\equiv nm \bmod 3$;

Exercício 23

Encontre um AFND que aceite as palavras…

com prefixo $010$ ou sufixo $110$.
com pelo menos, duas ocorrências de $01$ e sufixo $11$.
$0^n 1 0^m$ em que $n \equiv m\del{\bmod 3}$.

Exercício 24

Sejam $A_1$ e $A_2$ dois AFND. Encontre um AFND $A$ tal que $L\at{A} = L\at{A_1}L\at{A_2}$.
Seja $A$ um AFND. Encontre um AFND $B$ tal que $L\at{B} = L\at{A}^\ast$.

Exercício 25

Seja $A=\del{\set{p,q,r,s},\set{0,1},\delta,p,\set{q,s}}$ um AFND em que

$$\begin{array}{c|cc} \delta & 0 & 1 \cr \hline p & \set{q,s} & \set{q} \cr q & \set{r} & \set{q,r} \cr r & \set{s} & \set{p} \cr s & \emptyset & \set{p} \end{array}$$

Construa um AFND que aceite a linguagem complementar de $L\at{A}$.

Exercício 26

Construa um AFD que aceite a linguagem binária das palavras em que o quinto símbolo a partir do fim é $0$.
Converta (simule) cada um dos AFND seguintes num AFD:
1. $N = \del{ \set{p,q,r}, \set{0,1}, \delta,p, \set{q,r} }$ com transição $$ \begin{array}{c|cc} \delta & 0 & 1 \cr \hline p & p & pq \cr q & r &\emptyset \cr r & \emptyset & \emptyset \end{array}$$
2. Dados nos diagramas abaixo:

26.2 A	26.2 B	26.2 C

Exercício 27

Construa um AFD que aceite a linguagem das palavras que:

Contêm as sub-palavras $010$ e $101$;
Com sufixo $00$ ou $01$ ou $10$ (de duas maneiras);
Ou (contêm as sub-palavras $001$ e $110$) ou (não contêm nem $001$ nem $110$);
A quarta letra a partir do fim, e a quarta letra a partir do princípio são ambas $0$ (nota: $0110$ e $10101$ estão nesta linguagem);

O Pumping Lemma

Exercício 28

Mostre que as seguintes linguagens não são regulares:

✓ $L = \set{1^n+1^m=1^{n+m} \st n,m \geq 0}$.
A linguagem das palavras capicua sobre $\set{a,b}$.
$L = \set{aa^n b^n \st n \geq 0}$.
$L = \set{0^n 1^{n+1} \st n \geq 0}$.
$L = \set{a^n c b^n \st n \geq 0}$.
$L = \set{a^nb^m \st m > n \geq 0}$.

Implementação

As indicações gerais para os exercícios de implementação são válidas aqui.

Uma Biblioteca para AFD

A biblioteca para AFD tem de verificar as condições indicadas a seguir.

Os estados são números inteiros, os símbolos de entrada são string e as palavras são listas de símbolos.
Represente. Um AFD é representado por uma estrutura de dados FSA (pode ser uma classe, uma struct, etc) com os seguintes atributos, que devem ser visíveis mas não modificáveis:
- initialState o estado inicial.
- finalStates o conjunto dos estados finais.
- delta uma lista de triplos (q, s, p) que define a transição $\delta(q,s) = p$.
Construção. Um AFD é construidos pela função/método makeFSA(t,i,f) em que:
- t é uma lista de triplos (q, s, p) como acima.
- i é o estado inicial.
- f é a lista dos estados finais.
Sanidade. A função wellFormed(fsa) ou fsa.wellFormed() testa se os atributos t,i,f do argumento definem, de facto, um AFD. Quais são essas condições?
Implemente. A função step(fsa, q, s) ou fsa.step(q, s) devolve o estado p quando fsa está no estado q e lê s.

Se não existe transição para (q, s) esta função devolve “não definido”.

Em python “não definido” é None, em java/kotlin é null, em rust é Option::None, outras linguagens podem ou não definir “não definido” :D
Implemente. A função proc(fsa, q, w) ou fsa.proc(q, w) devolve o estado em que fsa termina se começar em q e ler a palavra w. Use o critério de step se a computação não continuar até ao fim.
Implemente. A função accepts(fsa, q, w) ou fsa.accepts(q, w), testa se w é aceite por fsa. Esta função deve devolver sempre um booleano.
Escrita. A função repr(fsa) ou fsa.repr() devolve uma string com várias linhas:
- A primeira linha tem o formato i <Q>; em que <Q> é o estado inicial.
- A segunda linha tem o formato f <Q1> ... <Qn>; em que os <Qi> são os estados finais.
- As restantes linhas têm o formato <Q> <S> <P>; para representar a transição $\delta(q, s) = p$ do fsa. Deve existir uma linha destas para cada “aresta” do autómato.
- N.B. todas as linhas terminam em “;” e valores na mesma linha são separados por espaços.
† Leitura. A função parseFSA(s) tem como argumento uma string no formato acima e devolve o FSA correspondente. A leitura do argumento deve descartar carateres “espaço” (\n\r\t) mas com cuidado.
† Escrita. Consulte a documentação da linguagem dot usada para definir grafos. Implemente uma função reprDOT(fsa) ou fsa.reprDOT() para gerar um grafo numa string em dot.
† Sanidade. As funções repr e parseFSA devem ser “inversas” uma da outra, no sentido em que parseFSA(s).repr() == s e parseFSA(fsa.repr()) == fsa. Embora estas igualdades não sejam exatamente igualdades, nem fáceis de implementar, teste-as com alguns casos simples.

Autómatos e Linguagens de Programação