Mecanismos para
Verificação de
Linguagens
Diferentes máquinas reconhecedoras para cada nível
da Hierarquia de Chomsky
Sistemas de estados finitos: São
modelos matemáticos com entradas
e saídas discretas, podendo assumir
um número sempre finito e
pré-definido de estados.
Formalismos
para
verificação
Aplicações: Analisadores léxicos,
processadores de texto, etc.
Autômato finito: Também chamado Autômato Finito
Determinístico, pode ser visto como uma máquina composta,
basicamente, de três partes:
1. Fita: Entrada da máquina, contendo a informação a ser
processada (memória).
2. Controle: Reflete o estado corrente da máquina, possui uma
cabeça de leitura / gravação que atua sobre a fita
3. Função de transição: Função que modifica os estados da
máquina e o conteúdo da fita (programa).
AFD
• Um Autômato Finito Determinístico (AFD) M, é
uma 5-upla M=(∑,Q,δ,q0,F), onde:
– ∑ = Alfabeto de símbolos de entrada
– Q = Conjuntos de estados possíveis
– δ = Função de transição δ: Q x ∑ → Q
– q0 = Estado inicial
– F = Conjunto de estados finais; F ⊂ Q
Autômato de Estados Finitos
Abstração do AF como uma máquina com controle finito
A Fita
Estrutura finita
Dividida em células
Cada célula armazena um único símbolo por vez.
Símbolos pertencem a um alfabeto de entrada ∑.
Não é possível editar os símbolos na fita.
Não existe memória auxiliar.
Cada palavra a ser processada ocupa toda a fita
Pode ser representada
A função Programa por um GRAFO FINITO
DIRETO:
Processamento
O processamento de
um AF M para uma
palavra de entrada w,
consiste na sucessiva
aplicação da função
programa para cada
símbolo de w, da
esquerda para a direita,
até ocorrer uma
condição de parada.
Exemplo
• Considere a linguagem L={w|w δ1 a b
possui aa ou bb como
subpalavra} q0 q1 q2
• O AF M=({a,b},{q0,q1,q2,qf},
δ1,q0,{qf}) q1 qf q2
q2 q1 qf
Com δ1 definido pela tabela
ao lado, reconhece L. qf qf qf
Grafo do AFD
Funcionamento:
Inicia-se em q0,
admitindo entrada “a”
ou “b”; quando lê dois
símbolos consecutivos,
entra no estado final e
“varre” a cadeia de
entrada até o final
Notas
• O AFD sempre para após processar cada símbolo
(discreto)
• Não existe a possibilidade de loop.
• Condições de parada:
– Para após o último símbolo e aceita w
– Para após o último símbolo e não aceita w
– A função é indefinida (erro lógico); pára e rejeita w
Exercício
• Construa um AFD que reconheça as seguintes
entradas (indique o grafo associado)
– 0,14E02
– $1000101001X
– BEGIN
Função programa estendida
• A função programa δ:Q × ∑→ Q pode ser estendida
para palavras, como
δ:Q × ∑*→ Q
definida como segue:
– δ(q,ε) = q
– δ(q,aw) = δ(δ(q,a),w)
Exemplo
• Considere o AF M=({a,b},{q0,q1,q2,qf}, δ1,q0,{qf}),
definido no exemplo anterior. A função programa δ
pode ser estendida para δ e aplicada à entrada “abaa”
a partir de q0, como segue:
δ(q0,abaa) = Função estendida sobre abaa
δ(δ(q0,a),baa) = Processa abaa
δ(q1,baa) = Função estendida sobre baa
δ(δ(q1,b)aa)
δ(q2,aa)
δ(δ(q2,a),a)
δ(q1,a)
δ(δ(q1,a),ε)
δ(qf, ε) = qf Função estendida sobre ε
(FIM da indução)
Exercícios
• Construir AFDs que aceitem as linguagens:
– La={w|w possui um número par de a e b}
– La={w|w possui um número ímpar de a e b}
– La={w|w possui o mesmo número de a e b}
Aceitação de linguagens
• Considere uma função programa δ e sua extensão δ
denotadas simplesmente por δ.
• A Linguagem Aceita por um Autômato Finito M={Σ,Q,
δ,qo,F}, denotada por ACEITA(M) ou L(M), é o
conjunto de todas as palavras pertencentes a Σ*
aceitas por M, ou seja:
ACEITA(m) = {W| δ(qo,w) ∈ F}
Relações de complemento
• ACEITA(M) ∩ REJEITA(M) ∩ LOOP (M) = ∅
• ACEITA(M) ∪ REJEITA(M) ∪ LOOP (M) = Σ*
• ACEITA(M) é complemento de REJEITA(M), e
vice-versa
Autômatos Finitos Equivalentes
Dois AFs M1 e M2 são denominados Autômatos Finitos
Equivalentes se, e somente se:
ACEITA (M1) = ACEITA (M2)
DEFINIÇÂO: Uma linguagem
Linguagem Regular (ou Tipo 3) é uma
Regular (Tipo 3) linguagem reconhecida por um
AFD.
Autômatos Finitos
Não-Determinísticos
• Representam uma generalização dos modelos de
máquinas, aumentando o poder de reconhecimento
de linguagens.
Não-Determinísticos?
Ao processar uma entrada composta pelo estado
corrente e pelo símbolo lido (qi,wj), a função programa
(δ) tem como resultado um conjunto de novos
estados.
É como se a máquina possuísse várias unidades de
controle, uma para cada alternativa, processando
independentemente, sem compartilhar recursos com
os demais.
Não-Determinismo
• Constitui-se em uma importante generalização dos
modelos de máquinas
• É de importância fundamental no estudo da teoria da
computação
• Não necessariamente aumenta o poder de
reconhecimento de linguagens de uma classe de
autômatos (um AFND pode ser simulado por um AFD)
Definição
Um Autômato Finito Não-Determinístico
(AFND) M, é uma 5-upla M=(∑,Q,δ,q0,F),
onde:
– ∑ = Alfabeto de símbolos de entrada
– Q = Conjuntos finito de estados possíveis
– δ = Função de transição δ: Q x ∑ → 2Q
– q0 = Estado inicial ∈ Q
– F = Conjunto de estados finais; F ⊂ Q
Representação gráfica da função
programa do AFND
Estado anterior
q
Símbolo lido
s s s
p1 p2 pn
Conjunto de novos
δ(q,a) = {p1,p2,...,pn} estados
• O processamento de um AFND M,
para um conjunto de estados, ao
ler um símbolo, é a união dos
resultados da função programa
aplicada a cada um dos estados
Processamento alternativos.
do AFND • Para definir formalmente o AFND,
precisamos estender a definição da
função programa, usando como
argumento, um conjunto finito de
estados e uma palavra.
Função Programa Estendida
• Seja M=(∑,Q,δ,q0,F), um AFND M. A função programa
estendida de M, denotada por:
δ: 2Q x ∑*→ 2Q
é a função programa δ: Q x ∑ → 2Q estendida para
palavras, e é indutivamente definida como segue:
δ(P,ε) = P
δ(P,aw) = δ(∪ q∈P δ(q,a),w)
Função Programa Estendida
Assim, para um dado conjunto de estados {q1,q2,...,qn}, e
um símbolo dado “a”:
δ({q1,q2,...,qn}, a)= δ(q1,a) ∪ δ(q2,a) ∪ ... ∪ δ(qn,a)
Linguagem aceita por um AFND
• A linguagem aceita por um AFND, denotada por
ACEITA(M) ou L(M), é o conjunto de todas as palavras
pertencentes a ∑*,tais que existe pelo menos um
caminho alternativo que aceita a palavra, ou seja:
L(M)={w | ∃ q∈ δ(q0,w), tal que q ∈ F }
Linguagem aceita por um AFND
• A linguagem rejeitada por um AFND, denotada por
REJEITA(M), é o conjunto de todas as palavras
pertencentes a ∑*, que não são reconhecidas por
nenhum dos caminhos alternativos do autômato a
partir de q0:
Exemplo
• Considere a linguagem
L={w|w possui aa ou bb
como subpalavra}
• O AFND
M=({a,b},{q0,q1,q2,qf},
δ1,q0,{qf}), onde δ1
definido pela tabela
ao lado, reconhece L.
a,b
Grafo do AFND do q0
exemplo a b
L={w|w possui aa ou bb como q1 q2
subpalavra}
a b
qf
a,b
AFD x AFND
• O poder computacional do AFND não é superior
ao do AFD.
• Podemos dizer que o AFND é mais eficiente que
o AFD
• Por isso, podemos afirmar que qualquer AFND
pode ser construído a partir de AFDs.
Simulação de um AFND por um AFD
• Considere a linguagem do exemplo visto L={w|w
possui aa ou bb como subpalavra}.
δ1 a b
• O AFD que reconhece L, tem
sua função programa expressa
q0 q1 q2
pela tabela ao lado: q1 qf q2
q2 q1 qf
qf qf qf
Grafo do AFD do exemplo
q0
a b
b
q1 q2
a
a b
qf
a,b
Comparação dos AFs
q0
a b
b a,b
q0
q1 q2
a b
a
a q1 q2
b
qf a b
qf
a,b a,b
Exercícios
• Implemente AFNDs que reconheçam as seguintes
linguagens:
• L1={w|existe um número par de “a” e “b”}
• L2={w|existe um número ímpar de “a” e “b”}
• L3={w|existe um número par de “a” e um número
ímpar de “b”}
• Construa AFDs que simulem os AFNDs
implementados.
AFε - Autômato Finito com movimentos
vazios
• Movimento vazio é uma transição que ocorre sem a
leitura de qualquer símbolo na fita.
• Pode ser interpretado como um Não-Determinismo
interno a autômato.
• É “encapsulado” – Nada pode ser notado, a não ser
uma eventual mudança de estados.
• Não aumenta o poder de reconhecimento de
linguagens
AFε - Representação Gráfica
ε a1 an
p0 p1 pn
AFε - Definição
Um Autômato Finito Com Movimentos Vazios
(AFε) M, é uma 5-upla M=(∑,Q,δ,q0,F), onde:
– ∑ = Alfabeto de símbolos de entrada
– Q = Conjuntos finito de estados possíveis
– δ = Função de transição δ: Q x (∑∪{ε}) → 2Q
– q0 = Estado inicial ∈ Q
– F = Conjunto de estados finais; F ⊂ Q
Exemplo
Considere a linguagem:
L(M)={w | qualquer símbolo a antecede qualquer
símbolo b }
O AFε M=({a,b},{q0, qf},δ, q0,{qf}),
com δ definido pela tabela ao δ a b ε
Lado, reconhece L. q0 q0 - qf
q1 - qf
Grafo associado
a b
ε
q0 qf
Exemplo 2
q1
a,b, ε a
c
ε b b
q0 q2 q3 qf
ε c
c c
q4 q5 q6
L(M)={w | possui como sufixo a ou bb ou ccc}
Novo formalismo reconhecedor de
linguagens Tipo 3 - Regulares
• Além dos autômatos, outros formalismos são
utilizados para reconhecer gerar linguagens
regulares.
• Como já mencionamos, a Expressão Regular
também é adequada para esta tarefa.
Expressão Regular
• Toda linguagem regular pode ser descrita por
uma expressão regular.
• É considerada um formalismo gerador.
• É definida a partir de conjuntos básicos e
operações de concatenação e união.
• São consideradas bastante adequadas para
comunicação homem-máquina
Definição Formal
• Uma Expressão Regular Er sobre um alfabeto
∑,é definido indutivamente...
∅ É uma ER e denota a linguagem vazia
ε É uma ER e denota a linguagem contendo
unicamente, a palavra vazia {ε}
Σ É o alfabeto, qualquer x ∈ Σ é uma ER e
denota a linguagem contando a palavra
unitária {x}
Se r e s são ER e denotam as linguagens R e S,
então:
. (r+s) é ER e denota a linguagem R∪S
. (rs) é ER e denota a linguagem RS={uv| u ∈ R e v
∈S}
. (r*) é ER e denota a linguagem R*
Convenções:
. Concatenação sucessiva precede concatenação e união
. Concatenação precede união.
Exemplo de linguagens geradas
Expressão Linguagem Representada
Regular
aa Somente a palavra “aa”
ba* Todas iniciadas por b seguido de a (1 / +)
(a+b)* Todas sobre (a,b)
(a+b)*aa(a+b)* Todas com subpalavra “aa”
a*ba*ba* Todas com exatamente 2 “b”
(a+b)*(aa+bb) Todas que terminam com “aa” ou “bb”
(a+ε)(b+aa)* Todas sem “a”s consecutivos
Exercícios
• Construir AFNDs, AFεs e AFDs que
reconheçam as linguagens acima listadas.