02.LFA.LingRegulares.AFD.AFND 2014-3

Prévia do material em texto

DCC013 
 
Linguagens Formais 
e Autômatos 
Linguagens Regulares 
 Tipos de Gramáticas – segundo a hierarquia de 
Chomsky existem quatro tipos: 
 Tipo 0 ou Irrestritas: 
 P = {  | (NT)+, (NT)* } 
 Tipo 1 ou Sensível ao Contexto 
 P = {  | ||||, (NT)+, (NT)+}.Exceto S 
 Tipo 2 ou Livre de Contexto 
 P = { A | AN, (NT)+}. Exceto S 
 Tipo 3 ou Regular 
 AaB ou Aa, ou seja: 
 P = { AaX | AN, aT, XN{}} 
Linguagens Regulares - Preliminares 
2 
 Tipo 3  Tipo 2  Tipo 1  Tipo 0  T+ 
 (GR) (GLC) (GSC) (GI) 
Linguagens Regulares - Preliminares 
3 
 Esquematicamente: 
Regulares(3) 
Livres de Contexto(2) 
Sensíveis ao Contexto(1) 
Irrestrita(0) 
 Exemplo 
G = ({S, A, B}, {a, b}, P, S), onde 
 P = { S  aB | bA 
 A  a | aS | bAA 
 B  b | bS | aBB } 
 
1) Qual o tipo de G? 
2) L(G)? 
Linguagens Regulares - Preliminares 
4 
Livre de contexto; 
L(G) é o conjunto de todas as palavras 
em T+ que tem o mesmo número de a’s e 
b’s. 
 Exemplo 
G = ({S, B}, {a, b}, P, S), onde 
 P = { S  aS | bB | a | b 
 B  bB | b } 
 
1) Qual o tipo de G? 
2) L(G)? 
Linguagens Regulares - Preliminares 
5 
Regular 
L(G) é o conjunto de todas as palavras 
em T+ onde todos a’s precedem todos os 
b’s. 
 O autômato finito (AF) é uma máquina abstrata 
que reconhece linguagens regulares; 
 Modelo matemático com entradas e saídas. Se é 
fornecido ao AF uma sequência de símbolos 
como entrada, ele responderá se esta sequência 
pertence a linguagem ou não; 
 O AF pode assumir um número finito de estados; 
 Um estado resume os estados anteriores pelos 
quais passou e os símbolos que já foram lidos na 
entrada. 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
6 
 Um autômato finito, pode ser vista como uma 
máquina composta basicamente por três partes 
 Fita: Dispositivo de entrada que contém a 
informação a ser processada. A fita é finita à 
esquerda e à direita 
 Unidade de Controle: Reflete o estado corrente da 
máquina. Possui uma unidade de leitura (cabeça de 
leitura), que acessa uma unidade da fita de cada 
vez. Após cada leitura a cabeça move-se uma célula 
para a direita 
 Programa ou Função de Transição: Função que 
comanda as leituras e define o estado da máquina. 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
7 
 Autômato Finito como uma máquina com 
controle finito (fita, controle e função de 
transição): 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
8 
Fita a a b c c b a a 
q 
 
Controle 
Cabeçote de leitura 
Estado corrente 
Função de transição 
 Def. Formal de autômato finito determinístico 
(AFD). Um AFD é um quíntupla (, Q, , q0, F): 
 Q  : conjunto finito de estados 
 : alfabeto 
 q0  Q: estado inicial 
 F  Q: conjunto de estados finais 
  : função de transições,  :Q  Q 
 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
9 
 A função programa de um AFD pode ser 
representada como um grafo orientado finito 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
10 
Uma transição 
Estado inicial Estado final 
p q 
Estado 
anterior 
Novo 
estado 
a 
q0 
qf 
qf 
 Exemplo: autômato finito determinístico 
M1 = ({a, b}, {q0, q1, q2, qf}, 1, q0, {qf}) 
 
 
 
 
 
 
 L(M1) = {w | w possui aa ou bb como 
subpalavra} 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
11 
 1 a b 
 
 
 
 
 
* 
q0 
q1 
q2 
qf 
q1 
qf 
q1 
qf 
q2 
q2 
qf 
qf 
q1 q2 
b 
a 
q0 
qf 
a 
a 
a b 
b 
b 
1 
 Exemplo: M2 = ({0, 1}, { q1, q2, q3}, 2, q1, {q2}). 
 
 
 
 
 
 
 L(M2) = {w | w contém pelo menos um 1 e um 
número par de 0s segue o último 1} 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
12 
2 0 1 
q1 
q2 
q3 
q1 
q3 
q2 
q2 
q2 
– 
q1 
1 
0 
0 1 
0 
q2 q3 * 
2 
 Exemplo: M3 = ({0, 1}, { q1, q2}, 3, q1, {q2}) 
 
 
 
 
 
 
 L(M3) = {w | w termina com um 1} 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
13 
3 0 1 
q1 
q2 
q1 
q1 
q2 
q2 * 
3 
q1 
0 
0 1 
q2 1 
 Exemplo: M4 = ({a, b}, {s, q1, q2, r1, r2}, 4, s, {r1, 
q1}) 
 
 
 
 
 
 
 L(M4) = {w | w começa e termina com o mesmo 
símbolo} 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
14 
q2 
b 
b a 
a 
4 
s 
r1 q1 
r2 
a 
a b 
b 
b a 
 Exemplo: N = ({a, b}, {q0, q1, q2}, , q0, {q2}) 
 Transições: (q0, a) = q1, (q1, a) = q1, 
 (q1, b) = q2. 
 
 
 
 
 
 Logo, L(N) = {anb | n1} 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
15 
q0 
a 
a 
b 
q2 q1 
 
 Exemplo: Que linguagem aceita A2? 
 
 
 
 
 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
16 
A2 
q2 
1 
0 0 
1 
q3 q1 
q2 
0 0 
1 
1 
 Exemplo: Que linguagem aceita A3? 
 
 
 
 
 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
17 
q0 
0 
1 1 
q2 q1 
A3 
q0 
1 
0 
0 
0 
1 
 Definição Formal de Computação: 
Sejam 𝐴 = 𝑄,, 𝛿, 𝑞0, 𝐹 um AFD e 𝑤 = 𝑤1𝑤2𝑤3 … 𝑤𝑛 uma 
palavra sobre . 
Dizemos que A aceita 𝑤 se existe uma sequência de estados de 
𝑄, 𝑟 = 𝑟0, 𝑟1, … , 𝑟𝑛, tal que: 
1. 𝑟0 = 𝑞0; e 
2. 𝛿 𝑟𝑖 , 𝑤𝑖+1 = 𝑟𝑖+1 para todo 0 ≤ 𝑖 ≤ 𝑛 − 1; e 
3. 𝑟𝑛 ∈ 𝐹. 
 A sequência 𝑟 é chamada de trajetória de 𝐴 sobre 
𝑤. Ou computação de 𝑤 sobre A. 
 A linguagem aceita por um AFD A é 
 𝐿 𝐴 = 𝑤|𝐴 aceita 𝑤 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
18 
 Extensão da função  para o domínio 𝑄 × Σ∗ 
1. 𝛿 𝑞, 𝜀 = 𝑞; 
2. 𝛿 𝑞, 𝑎𝑢 = 𝛿 𝛿 𝑞, 𝑢 , 𝑎 para 𝑎 ∈ Σ e 𝑢 ∈ Σ∗. 
 𝛿 𝑞, 𝑢 = 𝑝 significa que M, iniciando no estado 𝑞, e 
tendo a sequência 𝑢 na fita de entrada, entrará no 
estado 𝑝, após o cabeçote mover-se para a direita 
𝑢 células; 
 Uma sentença é aceita por 𝑀 se 𝛿 𝑞0, 𝑢 = 𝑝 para 
algum 𝑝 ∈ 𝐹, ou seja 
 𝐿 𝑀 = 𝑢|𝛿 𝑞0, 𝑢 = 𝑝 com 𝑝 ∈ 𝐹 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
19 
 Exemplo: Seja 𝐴2 = 𝑄, Σ, 𝛿, 𝑞0, 𝐹 , onde: 
 Q = 𝑞0, 𝑞1, 𝑞2, 𝑞3 , Σ = 0,1 , F = 𝑞0 
𝛿 𝑞0, 0 = 𝑞2 
𝛿 𝑞1, 0 = 𝑞3 
𝛿 𝑞2, 0 = 𝑞0 
𝛿 𝑞3, 0 = 𝑞1 
𝛿 𝑞0, 1 = 𝑞1 
𝛿 𝑞1, 1 = 𝑞0 
𝛿 𝑞2, 1 = 𝑞3 
𝛿 𝑞3, 1 = 𝑞2 
 
 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
20 
𝐴2 
q2 
1 
0 0 
1 
q1 q0 
q3 
0 0 
1 
1 
 Exemplo: Reconhecimento da cadeia 𝑤 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
21 
𝑤 = 110101 
𝛿 𝑞0, 110101 ⇒ 
𝛿 𝑞1, 10101 ⇒ 
𝛿 𝑞0, 0101 ⇒ 
𝛿 𝑞2, 101 ⇒ 
𝛿 𝑞3, 01 ⇒ 
𝛿 𝑞1, 1 ⇒ 
𝛿 𝑞0, 𝜀 ⇒ 𝑞0 
𝑤 = 1011 
𝛿 𝑞0, 1011 ⇒ 
𝛿 𝑞1, 011 ⇒ 
𝛿 𝑞3, 11 ⇒ 
𝛿 𝑞2, 1 ⇒ 
𝛿 𝑞3, 𝜀 ⇒ 𝑞3 
Logo, 𝟏𝟎𝟏𝟏 ∉ 𝐋 𝐀𝟐 . Logo, 𝟏𝟏𝟎𝟏𝟎𝟏 ∈ 𝐋 𝐀𝟐 . 
 Discussão: o que é Determinismo? 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
22 
4 
2 1 
0 
3 
0 
1 1 1 
1 0 
0 
Para todo AFD A e para 
toda palavra 𝑤 ∈ Σ∗ , 
existe exatamente uma 
trajetória de A sobre 𝑤. 
 Definição: Linguagens Regulares ou do Tipo 
3. 
 Uma linguagem aceita por um autômatofinito é 
uma Linguagem Regular ou do Tipo 3. 
 Exercício. Desenvolver AFDs que reconheçam 
as seguintes linguagens sobre  = {a, b}: 
1. {w | termina com aa} 
2. {w | w possui aaa como subpalavra} 
3. {w | w possui um número ímpar de a e b} 
4. {w | w possui número par de a e ímpar de b ou vice-versa} 
5. {w | o quinto símbolo da esquerda para a direita de w é a} 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
23 
 Exercício. Desenvolver AFDs que reconheçam 
as seguintes linguagens sobre  = {a, b}: 
6. {w | w possui aa ou bb como subpalavra} 
7. {w | w não contém dois ou mais 1’s consecutivos} 
8. {w | |w| mod 3 = 0} 
 Desenvolver AFDs para as linguagens: 
1.Identificadores de linguagens de programação 
2.Inteiros com ou sem sinal (+ ou -) 
3.Reais com ou sem sinal (+ ou -). Pode haver ou não 
dígitos após a , (vírgula). Ex: 45; 58,6; -54.; +.859 
 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
24 
Autômato Finito Não-Determinístico (AFND ou 
AFN) 
 Não-determinismo é uma importante 
generalização dos AF’s, essencial para a teoria 
da computação e para a teoria das linguagens 
formais. 
 Qualquer AFND pode ser simulado por um 
autômato finito determinístico 
 Em AFNDs, a função programa leva de um par 
(estado, símbolo) a um conjunto de estados 
possíveis. 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
25 
 Pode-se entender que o AFN assume 
simultaneamente todas as alternativas de 
estados possíveis {p0, p1, ..., pn} a partir do 
estado atual q  Q e do símbolo recebido a  ; 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
26 
Exemplo de transições 
não determinística 
p 
p2 p3 
a 
p1 
a a 
⋯ 
 Definição: Autômato Finito Não-
Determinístico. Um AFN é uma quíntupla 
 𝑀 = Σ, 𝑄, 𝛿, 𝑞0, 𝐹 , onde: 
 Σ : alfabeto de símbolos de entrada; 
 𝑄 ≠ ∅ : conjunto finito de estados; 
 𝛿 : função programa ou função de transição 
 𝛿: 𝑄 × Σ → 2 𝑄 
 𝑞0 ∈ 𝑄: estado inicial; 
 𝐹 ⊂ 𝑄 - conjunto de estados finais. 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
27 
 Portanto, os componentes do AFND são os 
mesmos do AFD, com exceção da função 
programa: 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
28 
p 
p2 p3 
a 
p1 
a a 
⋯ 
 Exemplo: AFND M5 = ({a, b}, {q0, q1, q2, qf}, 5, q0, 
{qf}): 
 
 
 
 
 
 M5 reconhece a linguagem L(M5) = {w | w possui 
aa ou bb como sub-palavra} 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
29 
5 a b 
q0 
q1 
q2 
Qf 
{q0, q1} 
{qf} 
- 
{qf} 
{q0, q2} 
- 
{qf} 
{qf} * 
q0 
q1 
qf 
q2 
a 
a,b 
b 
a 
a,b 
b 
 Exemplo: AFN M6 = ({a,b}, {q0, q1, q2, qf}, 6, q0, 
{qf}): 
 
 
 
 
 M6 reconhece a linguagem : 
 𝐿 𝑀6 = 𝑤𝑎𝑎𝑎|𝑤 ∈ 𝑎, 𝑏
∗ 
 𝐿 𝑀6 = 𝑤|𝑤 ∈ 𝑎, 𝑏
∗ e 𝑤 termina com 𝑎𝑎𝑎 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
30 
q0 
a a 
qf q1 M6 q2 
a 
b 
a