Aspectos Teóricos da
Computação
Linguagens Formais - 1
Prof. Luiz Fernando R B Corrêa
Agenda







Breve introdução da Hierarquia de
Chomsky
Definição de linguagens regulares
Autômatos Finitos Determinísticos
Gramática  AFD / AFD  Gramática
Autômatos Finitos Não-determinísticos
Equivalência entre AFND e AFD
Autômatos Finitos com Movimentos
Vazios
Hierarquia de Chomsky
Breve Introdução

Classifica as linguagens 4 tipos:
 Tipo 0: Linguagens Enumeráveis
Recursivamente
 Maior nível de liberdade em suas
regras
 Tipo 1:Linguagens Sensíveis ao
Contexto
 Tipo 2:Linguagens Livres do Contexto
 Tipo 3:Linguagens Regulares
Hierarquia de Chomsky
Breve Introdução


Os dois últimos níveis são amplamente utilizados
na descrição de linguagens de programação e na
implementação de compiladores e interpretadores
Cada nível é um super conjunto do próximo. Logo,
uma gramática de tipo n é conseqüentemente uma
linguagem de tipo n - 1.
Linguagens Regulares
Linguagens Regulares ou Tipo 3 pode
ser representada por:
 Autômato Finito


• Expressão Regular


basicamente, um sistema de estados
finitos (determinístico, não-determinístico
ou com movimentos vazios)
conjuntos (linguagens) básicos +
concatenação e união
• Gramática Regular

gramática com restrições da forma das
regras de produção
Linguagens Regulares
Hierarquia de Chomsky
 classe de linguagens mais simples
 algoritmos de reconhecimento,
geração ou conversão entre
formalismos
 pouca complexidade
 grande eficiência
 fácil implementação
Linguagens Regulares

Universo de aplicações das
linguagens regulares



Exemplo típico e simples


Muito grande
Constantemente ampliado
Análise léxica
Exemplos mais recentes



Sistemas de animação
Hipertextos
Hipermídias
Sistema de Estados Finitos

Sistema de Estados Finitos


modelo matemático de sistema com
entradas e saídas discretas
número finito e pré-definido de estados


podem ser definidos antes de iniciar o
processamento
Estado

somente informações do passado
necessárias para determinar as ações para
a próxima entrada
Sistema de Estados Finitos



Motivacional
 Podem ser associados a diversos tipos de
sistemas naturais e construídos
Exemplo: Elevador
 Não memoriza as requisições anteriores
 Estado: sumariza "andar corrente" e
"direção de movimento"
 Entrada: requisições pendentes
Exemplo: Analisador Léxico, Processador de
Texto
 Estado: memoriza a estrutura do prefixo da
palavra em análise
 Entrada: texto
Autômato Finito




Reconhecedor de palavras ou cadeia de
caracteres, que sempre pára retornando uma
resposta sim (cadeia reconhecida) ou não
(cadeia não reconhecida)
Bons modelos para computadores com
capacidade de memória reduzida
Fazem parte de vários dispositivos eletromecânicos do dia-a-dia
Podem ser classificados em:
 Autômatos Finitos Determinísticos (AFD)
 Autômatos Finitos Não-Determinísticos
(AFND)
Autômato Finito
Exemplo - 1

Interruptor de Luz


Se estiver apagada e pressionar, acende
Se estiver acessa e pressionar, apaga
Autômato Finito
Exemplo - 2

Palavra AMOR


Tentativa de
ler a palavra
AMBIENTE
Em q2 não é
mais possível
andar, logo
dizemos que o
autômato na
reconhece a
palavra
Autômato Finito Determinístico

Máquina composta basicamente de três partes:
 Fita: dispositivo de entrada
 contém informação a ser processada
 Unidade de Controle: reflete o estado corrente
da máquina
 possui unidade de leitura (cabeça da fita)
 acessa uma célula da fita de cada vez
 movimenta-se exclusivamente para a direita
 Programa, Função Programa ou Função de
Transição
 comanda as leituras
 define o estado da máquina
Autômato Finito Determinístico

Fita
 Finita
 dividida em células
 cada célula armazena um símbolo
 símbolos pertencem a um alfabeto de
entrada
 não é possível gravar sobre a fita (não existe
memória auxiliar)
 palavra a ser processada ocupa toda a fita
Autômato Finito Determinístico


Unidade de controle
 número finito e predefinido de estados
Leitura
 lê o símbolo de uma célula de cada vez
 move a cabeça da fita uma célula para a direita
 posição inicial da cabeça célula mais à esquerda
da fita
Autômato Finito Determinístico

Programa: função parcial
 dependendo do estado corrente e do símbolo lido
determina o novo estado do autômato
 Não possui memória de trabalho, logo, para
armazenar as informações passadas necessárias
ao processamento, deve-se usar o conceito de
estado
Autômato Finito Determinístico
Definição Formal






Autômato Finito Determinístico (AFD), é definido
pela 5-upla:
M=(Σ,Q, δ,qo,F), onde:
Σ : Alfabeto de símbolos de entrada
Q : conjunto de estados possíveis do autômato o
qual é finito
δ : função programa ou função transição: δ:QxΣQ
,a qual é uma função parcial. Significa dizer que
permanecendo em um estado e lendo um símbolo
do alfabeto faz o autômato passar para outro estado
ou mesmo ficar no mesmo
 transição do autômato: δ(p, a) = q
q0 : estado inicial tal que q0 é um elemento de Q
F : conjunto de estados finais tal que F está contido
em Q
Autômato Finito Determinístico
Definição Formal

Autômato finito como um diagrama: δ(p, a) = q
Autômato Finito Determinístico
Definição Formal

Estados iniciais e finais

Transições paralelas: δ(q, a) = p e δ(q, b) = p

Os arcos que vão de um estado para outro
são chamados de transições
Autômato Finito Determinístico
Definição Formal

Função programa como uma tabela de dupla
entrada
Autômato Finito Determinístico
Definição Formal


Computação de um autômato finito
 sucessiva aplicação da função programa para
cada símbolo da entrada (da esquerda para a
direita) até ocorrer uma condição de parada
Lembre-se que um autômato finito
 não possui memória de trabalho para
armazenar as informações passadas deve-se
usar o conceito de estado
Autômato Finito Determinístico
Definição Formal
Exemplo: Autômato Finito: aa ou bb como
subpalavra
L1 = { w | w possui aa ou bb como subpalavra }

Autômato finito:
M1 = ({ a, b }, { q0, q1, q2, qf }, δ1, q0, { qf })

*
Obs.: Para facilitar, o estado inicial vamos
marcar com  e os finais com *
Autômato Finito Determinístico
Definição Formal – Gramática AFD



q1: "símbolo anterior é a“
q2: "símbolo anterior é b“
após identificar aa ou bb
 qf (final): varre o sufixo da entrada terminar o processamento
Autômato Finito Determinístico
Definição Formal

Lendo a palavra abba
Autômato Finito Determinístico
Definição Formal

Lendo a palavra abba
Autômato Finito Determinístico
Definição Formal – AFD  Gramática



Seja o AFD:
A gramática é:
G={{a,b},{q0,q1,q2}, δ,{q0},{q2}
δ
a
b
q0
q1
∅
q1
∅
q2
q2
∅
∅
Autômato Finito Determinístico
Definição Formal


Autômato Finito Sempre Para
 Como
 qualquer palavra é finita
 novo símbolo é lido a cada aplicação da função
programa
 não existe a possibilidade de ciclo (loop) infinito
Parada do processamento
 Aceita a entrada
 após processar o último símbolo, assume um
estado final
 Rejeita a entrada. Duas possibilidades
 após processar o último símbolo, assume um
estado não-final
 programa indefinido para argumento (estado e
símbolo)
Autômato Finito Determinístico
Resumindo

Definir um AFD engloba definir
 Um conjunto finito de estados;




Um alfabeto de entrada que indica os símbolos
de entrada permitidos;
Um conjunto de regras de movimento que
indicam como ir de um estado p/ outro,
dependendo do símbolo de entrada;
Um estado escolhido como estado inicial;
Um conjunto de estados escolhidos como
estados finais (de reconhecimento);
Autômato Finito Determinístico

Para definir formalmente o comportamento de
um Autômato Finito (ou seja, dar semântica à
sintaxe de um Autômato Finito), é necessário
estender a definição da função programa
usando como argumento um estado e uma
palavra
Autômato Finito Determinístico
Função Programa Estendida (FPE), Computação
Seja M = (Σ, Q, δ, q0, F) AFD. A função programa
estendida denotada por:
δ*: Q × Σ* → Q
é a função prog δ: Q × Σ → Q estendida para
palavras - indutivamente definida
δ*(q, ε) = q
δ*(q, aw) = δ*(δ(q, a), w)
 Observe
sucessiva aplicação da função programa para
cada símb da palavra a partir de um dado estado
se a entrada for vazia, fica parado
aceita/rejeita: função programa estendida a
partir do estado inicial
Autômato Finito Determinístico
Função Programa Estendida (FPE), Computação
Exemplo:
Função estendida= fe









δ*(q0, abaa) =
δ*(δ(q0, a), baa) =
δ*(q1, baa) =
δ*(δ(q1, b), aa) =
δ*(q2, aa) =
δ*(δ(q2, a), a) =
δ*(q1, a) =
δ*(δ(q1, a), ε) =
δ*(qf, ε) =
ACEITA
fe sobre abaa
processa abaa
fe sobre baa
processa baa
fe sobre aa
processa aa
fe sobre a
processa a
qf fe sobre ε: fim da indução;
Autômato Finito Determinístico
Linguagem Aceita, Linguagem rejeitada
Seja M = (Σ, Q, δ, q0, F) um AFD
 Ling Aceita ou Ling Reconhecida por M
L(M) = ACEITA(M) = { w | δ*(q0, w) ∈ F }


Ling Rejeitada por M:
REJEITA(M) = { w | δ*(q0, w) ∉ F ou δ*(q0, w) é
indefinida }
Supondo que Σ* é o conjunto universo




ACEITA(M) ∩ REJEITA(M) = ∅
ACEITA(M) ∪ REJEITA(M) = Σ*
~ACEITA(M) = REJEITA(M) Complemento
~REJEITA(M) = ACEITA(M) Complemento
Autômato Finito Determinístico
Autômatos Finitos Equivalentes


Diferentes autômatos finitos podem aceitar uma
mesma linguagem
M1 e M2 são Autômatos Finitos Equivalentes se e
somente se
ACEITA(M1) = ACEITA(M2)
Autômato Finito Determinístico
Linguagem Regular ou Tipo 3

L é uma Linguagem Regular ou Linguagem Tipo 3
 existe pelo menos um autômato finito
determinístico que aceita L
Autômato Finito Determinístico
Exercício

Autômato Finito: número par de cada
símbolo:


L4 = { w | w possui um número par de a e um número
par de b }
Desenhar o AFD
Autômato Finito Não-Determinístico
Definições

Não-determinismo
 Importante generalização dos modelos de
máquinas.
 Fundamental no estudo de teoria da
computação e teoria das linguagens formais
 Não é sempre que aumenta o poder de
reconhecimento de linguagens de uma classe
de autômatos
 Qualquer AFND pode ser representado por um
AFD. O contrário também é verdade
Autômato Finito Não-Determinístico
Definições


Não-determinismo no programa, é uma função
parcial
 dependendo do estado corrente e do símbolo
lido, determina um conjunto de novos estados
do autômato.
Assume um conjunto de estados alternativos
 como uma multiplicação da unidade de
controle uma para cada alternativa
 processando independentemente sem
compartilhar recursos
 Podemos ter zero, uma ou mais transições de
estado com o mesmo símbolo de entrada.
Autômato Finito Não-Determinístico
M = (Σ, Q, δ, q0, F)





Σ - alfabeto (de símbolos) de entrada
Q - conjunto de estados possíveis (finito)
δ - (função) programa ou função de transição
(função parcial)
δ: Q × Σ → 2Q
transição: δ(p, a) = { q1, q2, …, qn }
q0 é um elemento distinguido de Q: estado inicial
F é um subconjunto de Q: conjunto de estados
finais
Autômato Finito Não-Determinístico
Autômato como Diagrama
Autômato Finito Não-Determinístico


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 estado alternativo.
Para definir formalmente o comportamento de
um AFND é necessário estender a definição da
função programa usando como argumento um
conjunto finito de estados e uma palavra
Autômato Finito Não-Determinístico
Função Programa Estendida, Computação
Seja M = (Σ, Q, δ, q0, F) um AFND. A função
Programa Estendida(FPE) denotada por:
δ*: 2Q × Σ* → 2Q
indutivamente definida como
δ*(P, ε) = P
δ*(P, aw) = δ*(∪q∈P δ(q, a), w)
Transição estendida (a um conjunto de estados):
dado um conjunto de estados {q1,q2,...,qn} e para
um símbolo a:
δ*({ q1, q2,…, qn }, a) = δ(q1, a) ∪ δ(q2, a) ∪…∪
δ(qn, a)
Autômato Finito Não-Determinístico
Parada do processamento


Aceita a entrada
 após processar o último símbolo da fita, existe
pelo menos um estado final pertencente ao
conjunto de estados alternativos atingidos
Rejeita a entrada. Duas possibilidades
 após processar o último símbolo da fita, todos
os estados alternativos atingidos são nãofinais
 programa indefinido para o argumento
(conjunto de estados e símbolo)
Autômato Finito Não-Determinístico
Linguagem Aceita, Linguagem Rejeitada
Seja M = (Σ, Q, δ, q0, F) um autômato finito nãodeterminístico
 Ling Aceita ou Linguagem Reconhecida por M


L(M) = ACEITA(M) = { w | δ*({ q0 }, w) ∩ F ≠ ∅ }
Linguagem Rejeitada por M

REJEITA(M) = { w | δ*({ q0 }, w) ∩ F = ∅ ou δ*({ q0 },
w) é indefinida }
Autômato Finito Não-Determinístico
Linguagem Aceita, Linguagem Rejeitada



Exemplo: AFND: aa ou bb como subpalavra
L5 = { w | w possui aa ou bb como subpalavra }
AFND:
M5 = ({ a, b }, { q0, q1, q2, qf }, δ5, q0, { qf })
Desenhar o AFD
Representar δ5 em tabela, tal que ACEITA(M5)=l5



Autômato Finito Não-Determinístico
Linguagem Aceita, Linguagem Rejeitada



o ciclo em q0 realiza uma varredura em toda a entrada
o caminho q0/q1/qf garante a ocorrência de aa
o caminho q0/q2/qf garante a ocorrência de bb
Autômato Finito Não-Determinístico
Linguagem Aceita, Linguagem Rejeitada

*
Autômato Finito Não-Determinístico
Linguagem Aceita, Linguagem Rejeitada


Exemplo2: AFND: aaa como sufixo
L6 = { w | w possui aaa como sufixo }
Autômato finito não-determinístico:
 M6 = ({ a, b }, { q0, q1, q2, qf }, δ6, q0, { qf })
Autômato Finito Não-Determinístico
Exercício

Exemplo3: AFND:
Dado M = ({q0,q1,q2}, {a,b}, δ, qo, {q2})
Diga se a palavra bab é aceita ou rejeitada e justifique!
a
b
q0
{q1}
{q0,q1}
q1
{}
{q2}
*q2
{q2}
{q2}
Relação entre AFD e AFND


Não-determinismo
 aparentemente, um significativo acréscimo ao poder
computacional autômato finito
 na realidade não aumenta seu poder computacional
Teorema: Equivalência entre AFD e AFND
 Classe dos Autômatos Finitos Determinísticos é
equivalente à Classe dos Autômatos Finitos NãoDeterminísticos
Relação entre AFD e AFND
Transformação de AFND em AFD

Seja o AFND
Relação entre AFD e AFND
Transformação de AFND em AFD

Transições do estado vazio + estados resultantes da junção
de dois ou mais estados da transição...
Relação entre AFD e AFND
Transformação de AFND em AFD
Relação entre AFD e AFND
Transformação de AFND em AFD

{q2} = estado de aceitação, então todos os estados que
tiverem q2 também serão estados de aceitação
Relação entre AFD e AFND
Transformação de AFND em AFD



Será que temos estados inacessíveis que podem ser
removidos?
Para facilitar a identificação, renomear os estados.
Quem acessa o estado C? Retirando o estado C, quem
acessará o estado D? ...
Relação entre AFD e AFND
Transformação de AFND em AFD

Após simplificação
=
Relação entre AFD e AFND
Algoritmo de conversão de AFND em AFD
1.
2.
3.
4.
5.
Tome o diagrama de transição do AFND e crie para cada
conjunto de estados, um novo estado onde o rótulo é o
próprio conjunto.
Complete as transições de cada novo estado acompanhando o
comportamento de cada estado individualmente e tomando a
união dos estados acessados.
Adicione como estados finais aqueles estados que tem como
rótulo um estado final.
Elimine os estados nunca acessados a partir do estado inicial.
Complete o AFD da seguinte forma:
1.
Q do AFD são os estados resultantes dos passos até este
ponto.
2.
O alfabeto não é alterado
3.
A construção do delta já foi mencionada.
4.
O estado inicial não se altera
5.
Os estados finais são a união de todos os estados finais do
delta resultante.
Exercícios

Transformar de AFND para AFD
Exercícios

Transformar de AFND para AFD
Exercícios

Transformar de AFND para AFD
Autômatos Finitos com Mov. Vazios



AFNε ou AFε
Movimentos vazios

generalizam os movimentos não-determinísticos
Movimento vazio

transição sem leitura de símbolo algum da fita

interpretado como um não-determinismo interno ao
autômato

transição encapsulada

excetuando-se por uma eventual mudança de
estados, nada mais pode ser observado
Autômatos Finitos com Mov. Vazios


Algumas vantagens

facilita algumas construções e demonstrações
Poder computacional p/ autômatos finitos

não aumenta o poder de reconhecimento de linguagens

qualquer AFNε pode ser simulado por um AFD
Autômatos Finitos com Mov. Vazios

O autômato vai do estado p para o estado q sem ler um
símbolo de entrada.
p
q
Autômatos Finitos com Mov. Vazios
Exemplo 1

Suponha um autômato que reconhece a soma de um inteiro
positivo ou negativo com um decimal positivo
Autômatos Finitos com Mov. Vazios
Exemplo 1

Acompanhar este autômato com a expressão -12+2.6
Autômatos Finitos com Mov. Vazios
Exemplo 2


Mostre como o autômato finito não-determinístico com
transições vazias (AFND-ε) se comporta ao receber a
palavra abc.
Para isso, mostre os conjuntos de estados atingidos após a
leitura de cada símbolo da palavra. Lembre-se de
considerar as transições ε antes e depois de fazer a
transição para os símbolos da palavra.
Autômatos Finitos com Mov. Vazios
Exemplo 2
Autômatos Finitos com Mov. Vazios
Exemplo 3
AFNε: a’s antecedem b’s
M7 = ({ a, b }, { q0, qf }, δ7, q0, { qf })
Autômatos Finitos com Mov. Vazios
Exemplo 4


L8 = { w | w possui como sufixo a ou bb ou ccc }
M8 = ({ a, b, c }, { q0, q1, q2, q3, q4, q5, q6, qf }, δ8,
q0, { qf })
Autômatos Finitos com Mov. Vazios
Exemplo 3


ee
s
t
p
q
u
bebeb
r

Estando no estado s e recebendo o símbolo b:
ler b e ir para p
ir para t e então ler b e ir para q
ir para t, ir para u e então ler b e ir para r.

O conjunto {b, bb, bbb} é aceito pelo autômato.



Referências da Aula



Material de aula: Linguagens Formais e
Autômatos Expressões Regulares. Professor
Eduardo Araújo Oliveira.
http://sites.google.com/site/eaoufpe
Licenciatura em Engenharia Informática – DEI/ISEP,
Linguagens de Programação 2006/07, Ficha 4,
Autómatos Finitos Determinísticos
http://www.dei.isep.ipp.pt/~goreti/ficha4.pdf
Capítulo 3 - Autómatos e respectivas
linguagens. Carlos Barrico.
http://www.di.ubi.pt/~cbarrico/Disciplinas/Compilad
ores/Downloads/Capitulo3.pdf