itc-aula3(Ellen Souza)

Prévia do material em texto

30/03/2012
1
LINGUAGENS REGULARES
INTRODUÇÃO À TEORIA DA 
COMPUTAÇÃO
1
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Linguagens Regulares
� Hierarquia de Chomsky é a classificação hierárquica 
de linguagens
2
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Fonte: (Menezes,1999)
Linguagens Regulares
� Correspondência entre as classes de linguagens,
gramáticas e reconhecedores
3
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Linguagem Gramática Reconhecedor
Tipo 0: enumerável recursivamente irrestrita máquinas de Turing
Tipo 1: sensível ao contexto sensível ao 
contexto
autômato limitado 
linearmente
Tipo 2: livre do contexto livre do 
contexto
autômatos com pilha
Tipo 3: regular regular autômatos finitos
30/03/2012
2
Linguagens Regulares
� De acordo com a Hierarquia de Chomsky, trata-se da
classe de linguagens mais simples
� Possibilita o desenvolvimento algoritmos de
reconhecimento ou de geração de:
� Pouca complexidade,
� Grande eficiência e de
� Fácil implementação.
4
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Linguagens Regulares
� O estudo das Linguagens Regulares ou Tipo 3, pode
ser abordado através de formalismos:
� Operacional ou reconhecedor (máquina):
� Autômato Finito, (Determinístico, Não-Determinístico ou com
Movimentos Vazios)
� Axiomático ou gerador (gramática):
� Gramática Regular
� Denotacional:
� Expressão Regular
� Também considerado formalismo gerador
5
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Sistema de Estados Finitos
� Um Sistema de Estados Finitos é um modelo
matemático de sistema com entradas e saídas
discretas.
� Pode assumir um número finito e pré-definido de
estados.
� Cada estado resume somente as informações do
passado necessárias para determinar as ações para a
próxima entrada.
6
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
30/03/2012
3
Sistema de Estados Finitos
� Um forte motivacional para o estudo de Sistemas de
Estados Finitos é o fato de poderem ser associados a
diversos tipos de sistemas naturais e construídos
� Um exemplo clássico e de simples entendimento é um
elevador.
� Um sistema que não memoriza as requisições anteriores.
� Cada "estado" sumariza as informações "andar corrente" e
"direção de movimento".
� As entradas para o sistema são requisições pendentes.
7
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Autômato Finito Determinístico
� Um Autômato Finito Determinístico (AFD) ou
simplesmente Autômato Finito pode ser visto como
uma máquina composta, basicamente, de três partes:
� Fita
� Fita de entrada e de saída (resultado)
� Unidade de Controle:
� Estado corrente
� Programa ou Função de Transição
� Define o estado
8
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Autômato Finito Determinístico
� A fita é um dispositivo de entrada que contém a
informação a ser processada
� A fita é finita (à esquerda e à direita), sendo dividida em células,
onde cada uma armazena um símbolo.
� Os símbolos pertencem a um alfabeto de entrada.
� Não é possível gravar sobre a fita (e não existe memória auxiliar).
� Inicialmente, a palavra a ser processada (ou seja, a informação de
entrada para a máquina) ocupa toda a fita.
9
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
30/03/2012
4
Autômato Finito Determinístico
� A unidade de controle reflete o estado corrente da
máquina.
� A unidade de controle possui um número finito e predefinido de
estados
� A unidade de leitura lê o símbolo de uma célula de cada vez
� Após a leitura, a cabeça da fita move-se uma célula para a direita.
� Inicialmente, a cabeça está posicionada na célula mais à
esquerda da fita
10
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Autômato Finito Determinístico
� Programa ou Função de Transição é a função que
comanda as leituras e define o estado da máquina
� O programa é uma função parcial que, dependendo do estado
corrente e do símbolo lido, determina o novo estado do
autômato.
� O Autômato Finito não possui memória de trabalho. Portanto,
para armazenar as informações passadas necessárias ao
processamento, deve-se usar o conceito de estado.
11
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Autômato Finito Determinístico
� Um Autômato Finito Determinístico (AFD) ou
simplesmente Autômato Finito (AF) M é uma 5-upla:
� ∑ alfabeto de símbolos de entrada
� Q conjunto de estados possíveis do autômato o qual é finito
� δ função programa ou função de transição:
� δ : Q X ∑ →Q
� É uma função parcial
� q0 estado inicial tal que q0 é elemento de Q
� F conjunto de estados finais tal que F está contido em Q
12
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
M = (∑ , Q, δ, q0, F)
30/03/2012
5
Autômato Finito Determinístico
� A função programa pode ser representada como um
grafo finito direto
� Neste caso, os estados iniciais e finais são
representados, respectivamente:
13
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Autômato Finito Determinístico
� O processamento de um Autômato Finito 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
14
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Autômato Finito Determinístico
� Um Autômato Finito sempre pára ao processar
qualquer entrada pois, como qualquer palavra é finita
e como um novo símbolo da entrada é lido a cada
aplicação da função programa, não existe a
possibilidade de ciclo (loop) infinito.
� A parada de um processamento pode ser de duas
maneiras: aceitando ou rejeitando uma entrada w.
15
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
30/03/2012
6
Autômato Finito Determinístico
� As condições de parada são as seguintes:
� Após processar o último símbolo da fita, o Autômato Finito
assume um estado final: o autômato pára e a entrada w é aceita;
� Após processar o último símbolo da fita, o Autômato Finito
assume um estado não final: o autômato pára e a entrada w é
rejeitada;
� A função programa é indefinida para o argumento (estado
corrente e símbolo lido): a máquina pára e a palavra de entrada
w é rejeitada.
16
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Autômato Finito Determinístico
� Exemplo 1: Autômato Finito
� Considere a linguagem L1 = {w | w possui aa ou bb como
subpalavra }
� O Autômato Finito: M1 = ({ a, b}, {q0, q1, q2, qf}, δ1, q0, { qf })
� Onde δ1 é como abaixo, representada, reconhece a linguagem L1.
� δ1(q0,a) = q1 δ1(q0,b) = q2
� δ1(q1,a) = qf δ1(q1,b) = q2
� δ1(q2,a) = q1 δ1(q2,b) = qf
� δ1(qf,a) = qf δ1(qf,b) = qf
17
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
δ1 a b
q0 q1 q2
q1 qf q2
q2 q1 qf
qf qf qf
Autômato Finito Determinístico
� Exemplo 1: Autômato Finito
18
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
δ1 a b
q0 q1 q2
q1 qf q2
q2 q1 qf
qf qf qf
30/03/2012
7
Autômato Finito Determinístico
� Exemplo 1: Autômato Finito
� Considere a palavra w = abba
� δ1(q0,a) = q1
� δ1(q1,b) = q2
� δ1(q2,b) = qf
� δ1(qf,a) = qf
19
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
a b b a
a b b a
a b b a
a b b a
Autômato Finito Determinístico
� Utilizando a ferramenta JFLAP - JAVA Formal Language
and Automata Package
� Construa o autômato abaixo
� Informe como entrada as seguintes palavras:
� abab
� aabb
� Qual o resultado final?
20
Profa. Ellen Souza - https://sites.google.com/site/ellenuastLinguagens Regulares
� Exemplo 2: Autômato Finito
� Dado o autômato abaixo, especifique sua quintupla
21
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
M = (∑ , Q, δ, q0, F)
30/03/2012
8
Linguagens Regulares
� A linguagem associada a um autômato é o conjunto de
todas as cadeias aceitas pelo autômato:
� Uma linguagem L é dita regular se, e somente se existe
um autômato finito determinístico M, tal que
22
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
L(M) = (w ∈ ∑* : δ*(q0, w) ∈ F)
L = L(M)
Autômato Finito Determinístico
� Dois Autômatos Finitos M1 e M2 são ditos equivalentes
se, e somente se reconhecem a mesma linguagem:
23
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
L(M1) = (L(M2)
Autômato Finito Determinístico
� Exemplo 3: Autômato Finito
� Construa dois autômatos para reconhecer a linguagem
L={w1 : w ∈ {0,1}*}
� Especifique a quintupla de cada um deles
24
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
30/03/2012
9
Autômato Finito Não Determinístico
� O Autômatos finitos podem ser determinísticos (AFD)
e não determinísticos (AFN)
� No AFD, cada movimento é determinado de uma única forma
� No AFN, existem várias possibilidades de transição para um
mesmo símbolo
25
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
AFD AFN
Autômato Finito Não Determinístico
� Um Autômato Finito Não Determinístico (AFN) M é
uma 5-upla:
� ∑ alfabeto de símbolos de entrada
� Q conjunto de estados possíveis do autômato o qual é finito
� δ função programa ou função de transição:
� δ : Q X ∑ →2Q (representa os subconjuntos de Q)
� É uma função parcial
� q0 estado inicial tal que q0 é elemento de Q
� F conjunto de estados finais tal que F está contido em Q
26
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
M = (∑ , Q, δ, q0, F)
Autômato Finito Não Determinístico
� Algumas referências citam que um Autômato Finito
Não Determinístico (AFN) pode ter movimentos
vazios. Um movimento vazio é uma transição sem
leitura de símbolo algum
� A função de transição para AFN com movimento vazio
é dada por:
27
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
δ : Q x { ∑ ∪ λ } →2Q
δ : Q x { ∑ ∪ ε } →2Q
30/03/2012
10
Autômato Finito Não Determinístico
� Exemplo 4: Autômato Finito Não Determinístico
� Construa um AFN que reconheça a linguagem L={w :
w ∈ possui aa ou bb como subcadeia} e tem ∑ = {a,b}
28
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Autômato Finito Não Determinístico
� Exemplo 5: Autômato Finito Não Determinístico
� Construa um AFN que reconheça a linguagem L={w |
w possui aaa sufixo} e tem ∑ = {a,b}
29
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Equivalência entre Autômatos
� Sabe-se que um autômato M1 é equivalente a um
autômato M2 se, e somente se, L(M1) = L(M2), então
pode-se transformar um AFN em AFD
� Q’ é o conjunto de todas as combinações, sem repetições, de estado Q,
as quais são denotadas por <q1,q2…qn>
� δ’ representa uma imagem de todos estados de todos os caminhos
alternativos, tal que δ’ (<q1….qn>,a) = <p1…pm>
� <q0> estado inicial
� F’ conjuntos de todos os estados <q1,q2…qn> pertencentes a Q’ tal que
algum componente de qj pertence a F
30
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Seja M = (∑ , Q, δ, q0, F) um AFN,
M’ = (∑’ , Q’, δ’, <q0>, F) é um AFD construído a partir de M
30/03/2012
11
Equivalência entre Autômatos
� Exemplo 5: Conversão de um AFN em AFD
� Passo 1 – Função de Transição
31
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
δ a b
q0 q0, q1 q0
q1 q2 ∅
q2 qf ∅
qf ∅ ∅
Equivalência entre Autômatos
� Exemplo 5: Conversão de um AFN em AFD
� Passo 2 – <q0> estado inicial = q0
32
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
δ a b
q0 q0, q1 q0
q1 q2 ∅
q2 qf ∅
qf ∅ ∅
Equivalência entre Autômatos
� Exemplo 5: Conversão de um AFN em AFD
� Passo 3 – transições a partir de <q0>
� Vértice <q0> e símbolo a
� δ'(<q0>,a)=<q0,q1>, já que δ(q0,a)={q0,q1}
� Vértice <q0> e símbolo b
� δ'(<q0>,b)=<q0>, já que δ(q0,b)={q0}
33
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
δ a b
q0 q0, q1 q0
q1 q2 ∅
q2 qf ∅
qf ∅ ∅
30/03/2012
12
Equivalência entre Autômatos
� Exemplo 5: Conversão de um AFN em AFD
� Passo 4 –transições a partir de <q0,q1>
� Vértice <q0,q1> e símbolo a
� δ'(<q0,q1>,a)=<q0,q1,q2>, já que δ(q0,a)={q0,q1} e δ(q1,a)={q2}
� Vértice <q0,q1> e símbolo b
� δ'(<q0,q1>,b)=<q0>, já que δ(q0,b)={q0}
34
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
δ a b
q0 q0, q1 q0
q1 q2 ∅
q2 qf ∅
qf ∅ ∅
Equivalência entre Autômatos
� Exemplo 5: Conversão de um AFN em AFD
� Passo 5 –transições a partir de <q0,q1,q2>
� Vértice <q0,q1,q2> e símbolo a
� δ'(<q0,q1,q2>,a)=<q0,q1,q2,qf>,
� já que δ(q0,a)={q0,q1}, δ(q1,a)={q2} e δ(q2,a)={qf}
� Vértice <q0,q1,q2> e símbolo b
� δ'(<q0,q1,q2>,b)=<q0>, já que δ(q0,b)={q0}
35
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
δ a b
q0 q0, q1 q0
q1 q2 ∅
q2 qf ∅
qf ∅ ∅
Equivalência entre Autômatos
� Exemplo 5: Conversão de um AFN em AFD
� Passo 6 –transições a partir de <q0,q1,q2,qf>
� Vértice <q0,q1,q2,qf> e símbolo a
� δ'(<q0,q1,q2,qf>,a)=<q0,q1,q2,qf>,
� já que δ(q0,a)={q0,q1}, δ(q1,a)={q2} e δ(q2,a)={qf}
� Vértice <q0,q1,q2,qf> e símbolo b
� δ'(<q0,q1,q2,qf>,b)=<q0>, já que δ(q0,b)={q0}
� F’={<q0,q1,q2,qf>}
36
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
δ a b
q0 q0, q1 q0
q1 q2 ∅
q2 qf ∅
qf ∅ ∅
30/03/2012
13
Equivalência entre Autômatos
� Portanto o AFD M’ = (∑’ , Q’, δ’, <q0>, F) a partir de AFN é:
� ∑’ = {a,b}
� Q’= {<q0>, <q0,q1>,<q0,q1,q2>,<q0,q1,q2,qf>}
� F’={<q0,q1,q2,qf>}
� δ’(<q0>,a)=<q0,q1>
� δ'(<q0>,b)=<q0>
� δ’(<q0,q1>,a)=<q0,q1,q2>
� δ’(<q0,q1>,b)=<q0>
� δ’(<q0,q1,q2>,a)=<q0,q1,q2,qf>
� δ’(<q0,q1,q2>,b)=<q0>
� δ’(<q0,q1,q2,qf>,a)=<q0,q1,q2,qf>
� δ’(<q0,q1,q2,qf>,b)=<q0>
37
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Equivalência entre Autômatos
� Exemplo 6: Converta o AFN abaixo em um AFD
38
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Linguagens Regulares
� Exercícios
� Pesquise outras formas (algoritmos) que façam a transformação 
de um AFN em AFD
� Utilize a ferramenta JFLAP - JAVA Formal Language and 
Automata Package para validar suas transformações
39
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
30/03/2012
14
Redução de Estados de um Autômato
� Também conhecido como o processo de minimização
dos estados de um autômato
� Tem como objetivo gerar um autômato finito
equivalente, porém com um número menor de estados
40
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Um autômato mínimo de uma Linguagem Regular L é 
um AFD M = (∑ , Q, δ, q0, F), tal que L=L(M) e que, para 
qualquer outro AFD M’ = (∑’ , Q’, δ’, q0’, F’) tal que 
L=L(M’), tem-se que #Q’<=#Q
Redução de Estados de um Autômato
� A minimização do número de estados é adotada em
muitas soluções práticas
� Exemplo: desenho de circuitos eletrônicos
� Contudo, em algumas aplicações, minimizar o número
de estados de um autômato pode não implicar no
menor custo de implementação
� A minimização de AF distintos que aceitam a mesma
linguagem geram o mesmo AF mínimo, ou seja, o
autômato mínimo é único
41
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Redução de Estados de um Autômato
� Idéia básica do algoritmo de minimização é unificar os
estados equivalentes:
1. Identificar os estados equivalentes por exclusão2. A partir de uma tabela de estados, são marcados os estados
não-equivalentes
3. Ao final do algoritmo, as referências não-marcadas
representam os estados equivalentes a serem unificados
� Estados são equivalentes quando no processamento de
uma entrada qualquer, a partir de estados
equivalentes, geram o mesmo resultado aceita/rejeita
42
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
30/03/2012
15
Redução de Estados de um Autômato
� Um autômato finito a ser minimizado deve satisfazer
os seguintes pré-requisitos:
1. Deve ser determinístico (AFD)
� Ser um AFN, gera um AFD equivalente
2. Não pode ter estados inacessíveis, isto é estados não atingíveis
a partir do estado inicial)
� Eliminar os estados inacessíveis e suas transições correspondentes
3. A função programa deve ser total, ou seja, a partir de qualquer
estado, são previstas transições para todos os símbolos do
alfabeto
� Criar um estado “d”, incluir transições não previstas tendo “d” como
destino, incluir um ciclo em “d” para todos os símbolos do alfabeto
43
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Redução de Estados de um Autômato
� Algoritmo de minimização:
� Passo 1: construir tabela relacionando os estados distintos, onde
cada par ocorre somente uma vez
� Passo 2: marcar na tabela todos os estados trivialmente não
equivalentes {estado final, estado não-final}
� Supor q1 é estado final, logo temos
as transições {q1, q0}, {q1,q2}
44
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
q0
q1
q2
q0 q1 q2
q0
q1 X
q2 X
q0 q1 q2
Redução de Estados de um Autômato
� Algoritmo de minimização:
� Passo 3: marcar na tabela os estados não equivalentes
� Para cada par (qu, qv) não marcado para o símbolo a ∈ ∑, suponha
que δ(qu, a) = pu e δ(qv, a) = pv
� Se pu = pv, então qu é equivalente a qv para o símbolo a e não deve
ser marcado;
� Se pu ≠ pv e o par {pu, pv} não está marcado, então {qu, qv} entra
num lista para posterior análise
� Se pu ≠ pv e o par {pu, pv} está marcado, então {qu, qv} não é
equivalente e deve ser marcado. Se {qu, qv} encabeça uma lista de
pares, então marcar todos os pares da lista (recursivamente)
45
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
30/03/2012
16
Redução de Estados de um Autômato
� Algoritmo de minimização:
� Passo 4: os estados de pares não marcados são equivalentes e
podem ser unificados
� A equivalência é transitiva;
� Pares de estados não finais equivalentes podem ser unificados como
um único estado não final;
� Pares de estados finais equivalentes podem ser unificados como um
único estado final;
� Se algum dos estados equivalentes é inicial, então o correspondente
estado unificado é inicial
46
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Redução de Estados de um Autômato
� Algoritmo de minimização:
� Passo 5: exclusão dos estados inúteis . Um estado q é inútil se é
não final e a partir de q não é possível atingir um estado final. O
estado “d” (se incluído) é sempre inútil
47
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Redução de Estados de um Autômato
� Exemplo 7: Minimizar um AFD
� Considere um AFD como segue:
� M={{q0,q1,q2,q3,q4,q5}, {a,b}, δ, q0, {q0,q4,q5}}
� O Autômato satisfaz todos os requisitos para ser minimizado
48
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
δ(q0,a)=q2 δ(q2,a)=q4 δ(q4,a)=q3
δ(q0,b)=q1 δ(q2,b)=q5 δ(q4,b)=q2
δ(q1,a)=q1 δ(q3,a)=q5 δ(q5,a)=q2
δ(q1,b)=q0 δ(q3,b)=q4 δ(q5,b)=q3
30/03/2012
17
Redução de Estados de um Autômato
� Exemplo 7: Minimizar um AFD
� Passo 1: tabela
49
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
q0
q1
q2
q3
q4
q5
q0 q1 q2 q3 q4 q5
Redução de Estados de um Autômato
� Exemplo 7: Minimizar um AFD
� Passo 2: marcação dos estados trivialmente não equivalentes
(estado final {q0,q4,q5}, estado não final {q1,q2,q3})
� {q0, q1}, {q0, q2}, {q0, q3}
� {q4, q1}, {q4, q2}, {q4, q3}
� {q5, q1}, {q5, q2}, {q5, q3}
50
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
q0
q1 X
q2 X
q3 X
q4 X X X
q5 X X X
q0 q1 q2 q3 q4 q5
Redução de Estados de um Autômato
� Exemplo 7: Minimizar um AFD
� Passo 3: marcação dos estados não equivalentes, percorrendo os
pares não marcados na tabela {q0, q4}, {q0, q5}, {q1,q2}, {q1,q3},
{q2, q3}, {q4, q5}
51
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
q0
q1 X
q2 X
q3 X
q4 X X X
q5 X X X
q0 q1 q2 q3 q4 q5
δ(q0,a)=q2 δ(q2,a)=q4 δ(q4,a)=q3
δ(q0,b)=q1 δ(q2,b)=q5 δ(q4,b)=q2
δ(q1,a)=q1 δ(q3,a)=q5 δ(q5,a)=q2
δ(q1,b)=qo δ(q3,b)=q4 δ(q5,b)=q3
30/03/2012
18
Redução de Estados de um Autômato
� Exemplo 7: Minimizar um AFD
� Passo 3: marcação dos estados não equivalentes, percorrendo os
pares não marcados na tabela {q0, q4}, {q0, q5}, {q1,q2}, {q1,q3},
{q2, q3}, {q4, q5}
� {q0, q4}
� δ(q0,a)=q2 δ(q4,a)=q3
� q2 ≠ q3 e o par não está marcado –
aguarda na lista
� δ(q0,b)=q1 δ(q4,b)=q2
� q1 ≠ q2 e o par não está marcado –
aguarda na lista
52
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
q0
q1 X
q2 X
q3 X
q4 X X X
q5 X X X
q0 q1 q2 q3 q4 q5
δ(q0,a)=q2 δ(q2,a)=q4 δ(q4,a)=q3
δ(q0,b)=q1 δ(q2,b)=q5 δ(q4,b)=q2
δ(q1,a)=q1 δ(q3,a)=q5 δ(q5,a)=q2
δ(q1,b)=qo δ(q3,b)=q4 δ(q5,b)=q3
Redução de Estados de um Autômato
� Exemplo 7: Minimizar um AFD
� Passo 3: marcação dos estados não equivalentes, percorrendo os
pares não marcados na tabela {q0, q4}, {q0, q5}, {q1,q2}, {q1,q3},
{q2, q3}, {q4, q5}
� {q0, q5}
� δ(q0,a)=q2 δ(q5,a)=q2
� q2 = q2 e o par é descartado
� δ(q0,b)=q1 δ(q5,b)=q3
� q1 ≠ q3 e o par não está marcado –
aguarda na lista
53
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
q0
q1 X
q2 X
q3 X
q4 X X X
q5 X X X
q0 q1 q2 q3 q4 q5
δ(q0,a)=q2 δ(q2,a)=q4 δ(q4,a)=q3
δ(q0,b)=q1 δ(q2,b)=q5 δ(q4,b)=q2
δ(q1,a)=q1 δ(q3,a)=q5 δ(q5,a)=q2
δ(q1,b)=qo δ(q3,b)=q4 δ(q5,b)=q3
Redução de Estados de um Autômato
� Exemplo 7: Minimizar um AFD
� Passo 3: marcação dos estados não equivalentes, percorrendo os
pares não marcados na tabela {q0, q4}, {q0, q5}, {q1,q2}, {q1,q3},
{q2, q3}, {q4, q5}
� {q1,q2}
� δ(q1,a)=q1 δ(q2,a)=q4
� q1 ≠ q4 e o par está marcado, marca
� {q1,q2}
� δ(q1,b)=q0 δ(q2,b)=q5 ....
� Como vai marcar {q1, q2}, marca
{q0 e q4} � esperando {q1,q2}
54
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
δ(q0,a)=q2 δ(q2,a)=q4 δ(q4,a)=q3
δ(q0,b)=q1 δ(q2,b)=q5 δ(q4,b)=q2
δ(q1,a)=q1 δ(q3,a)=q5 δ(q5,a)=q2
δ(q1,b)=qo δ(q3,b)=q4 δ(q5,b)=q3
q0
q1 X
q2 X X
q3 X
q4 X X X X
q5 X X X
q0 q1 q2 q3 q4 q5
30/03/2012
19
Redução de Estados de um Autômato
� Exemplo 7: Minimizar um AFD
� Passo 3: marcação dos estados não equivalentes, percorrendo os
pares não marcados na tabela {q0, q4}, {q0, q5}, {q1,q2}, {q1,q3},
{q2, q3}, {q4, q5}
� {q1,q3}
� δ(q1,a)=q1 δ(q3,a)=q5
� q1 ≠ q5 e o par está marcado, marca
� {q1,q3}
� δ(q1,b)=q0 δ(q3,b)=q4 ....
� Como vai marcar {q1, q3}, marca
{q0 e q5} � esperando {q1,q3}
55
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
δ(q0,a)=q2 δ(q2,a)=q4 δ(q4,a)=q3
δ(q0,b)=q1 δ(q2,b)=q5 δ(q4,b)=q2
δ(q1,a)=q1 δ(q3,a)=q5 δ(q5,a)=q2
δ(q1,b)=qo δ(q3,b)=q4 δ(q5,b)=q3
q0
q1 X
q2 X X
q3 X X
q4 X X X X
q5 X X X X
q0 q1 q2 q3 q4 q5
Redução de Estados de um Autômato
� Exemplo 7: Minimizar um AFD
� Passo 3: marcação dos estados não equivalentes, percorrendo os
pares não marcados na tabela {q0, q4}, {q0, q5}, {q1,q2}, {q1,q3},
{q2, q3}, {q4, q5}
� {q2,q3}
� δ(q2,a)=q4 δ(q3,a)=q5
� q4 ≠ q5 e o par não está marcado –
aguarda na lista� δ(q2,b)=q5 δ(q3,b)=q4 ....
� q5 ≠ q4 e o par não está marcado –
aguarda na lista
56
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
δ(q0,a)=q2 δ(q2,a)=q4 δ(q4,a)=q3
δ(q0,b)=q1 δ(q2,b)=q5 δ(q4,b)=q2
δ(q1,a)=q1 δ(q3,a)=q5 δ(q5,a)=q2
δ(q1,b)=qo δ(q3,b)=q4 δ(q5,b)=q3
q0
q1 X
q2 X X
q3 X X
q4 X X X X
q5 X X X X
q0 q1 q2 q3 q4 q5
Redução de Estados de um Autômato
� Exemplo 7: Minimizar um AFD
� Passo 3: marcação dos estados não equivalentes, percorrendo os
pares não marcados na tabela {q0, q4}, {q0, q5}, {q1,q2}, {q1,q3},
{q2, q3}, {q4, q5}
� {q4,q5}
� δ(q4,a)=q3 δ(q5,a)=q2
� q3 ≠ q2 e o par não está marcado –
aguarda na lista
� δ(q4,b)=q2 δ(q5,b)=q3 ....
� q2 ≠ q3 e o par não está marcado –
aguarda na lista
57
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
δ(q0,a)=q2 δ(q2,a)=q4 δ(q4,a)=q3
δ(q0,b)=q1 δ(q2,b)=q5 δ(q4,b)=q2
δ(q1,a)=q1 δ(q3,a)=q5 δ(q5,a)=q2
δ(q1,b)=qo δ(q3,b)=q4 δ(q5,b)=q3
q0
q1 X
q2 X X
q3 X X
q4 X X X X
q5 X X X X
q0 q1 q2 q3 q4 q5
30/03/2012
20
Redução de Estados de um Autômato
� Exemplo 7: Minimizar um AFD
� Passo 4: unificação dos estados equivalentes {q0, q4}, {q0, q5},
{q1,q2}, {q1,q3}, {q2, q3}, {q4, q5}
� Como {q2,q3} não foi marcado,
então q3 é equivalente a q2
Cria-se o estado q23 (unificado)
� Como {q4,q5} não foi marcado,
então q4 é equivalente a q5
Cria-se o estado q45 (unificado)
58
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
q0
q1 X
q2 X X
q3 X X
q4 X X X X
q5 X X X X
q0 q1 q2 q3 q4 q5
Redução de Estados de um Autômato
� Exemplo 7: Minimizar um AFD
� Passo 5: exclusão dos estado inúteis : q2, q3, q4, q5
� Então:
� M’={{q0,q1,q23,q45}, {a.b}, δ, q0, {q0, q45}}
� δ(q0,a)=q23 δ(q23,a)=q45
� δ(q0,b)=q1 δ(q23,b)=q45
� δ(q1,a)=q1 δ(q45,a)=q23
� δ(q1,b)=q0 δ(q45,b)=q23
59
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
q0
q1 X
q2 X X
q3 X X
q4 X X X X
q5 X X X X
q0 q1 q2 q3 q4 q5
δ(q0,a)=q23 δ(q23,a)=q45 δ(q45,a)=q23
δ(q0,b)=q1 δ(q23,b)=q45 δ(q45,b)=q23
δ(q1,a)=q1 δ(q3,a)=q5 δ(q5,a)=q2
δ(q1,b)=q0 δ(q3,b)=q4 δ(q5,b)=q3
Redução de Estados de um Autômato
� Exemplo 7: Minimizar um AFD
� Considere um AFD como segue:
� M={{q0,q1,q2,q3,q4}, {0,1}, δ, q0, {q4}}
� O Autômato satisfaz todos os requisitos para ser minimizado
60
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
δ(q0,0)=q1 δ(q2,0)=q1 δ(q4,0)=q4
δ(q0,1)=q3 δ(q2,1)=q4 δ(q4,1)=q4
δ(q1,0)=q2 δ(q3,0)=q2
δ(q1,1)=q4 δ(q3,1)=q4 
30/03/2012
21
Redução de Estados de um Autômato
� Exemplo 7: Minimizar um AFD
� Então:
� M’={{q0,q123,q4}, {0,1}, δ, q0, {q4}}
61
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
δ(q0,0)=q123 δ(q2,0)=q1 δ(q4,0)=q4
δ(q0,1)=q123 δ(q2,1)=q4 δ(q4,1)=q4
δ(q123,0)=q123 δ(q3,0)=q2
δ(q123,1)=q4 δ(q3,1)=q4 
Expressões Regulares
� Expressão regular é uma maneira de descrever os 
conjuntos regulares
� Usa-se a expressão regular na construção de:
� Compiladores, editores, sistemas operacionais, protocolos
� É um formalismo denotacional, também considerado 
gerador, pois se pode inferir como construir ou “gerar” 
as palavras de uma linguagem 
62
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Expressões Regulares
� Uma Expressão Regular (ER) sobre um alfabeto ∑ é 
definida como:
� ɸ (lê-se phi) é uma ER e denota uma linguagem vazia
� λ é uma ER e denota a linguagem contendo a palavra vazia {λ}
� x (sı́mbolo do alfabeto ∑) é uma ER e denota a linguagem 
contendo a palavra {x}
� Se r e s são ER e denotam as linguagens R e S, respectivamente 
como:
� (r) é uma ER
� (r + s) é uma ER e denota a linguagem R ∪ S
� (r . s ) é uma ER e denota a linguagem RS={uv | u ∈ R e v ∈ S}
� r* é uma ER e denota a linguagem R* 
63
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
30/03/2012
22
Expressões Regulares
� Propriedades
� Concatenação sucessiva (*) tem precedência sobre a 
concatenação (.) e a união (+)
� A concatenação (.) tem precedência sobre e a união (+)
� Se r e s são ER e denotam as linguagens R e S, respectivamente, 
então:
� L(r + s) = L(r) ∪ L(s)
� L(r . s ) = L(r) . L(s) ou L(rs) = L(r)L(s)
� L((r)) = L(r)
� L(r*) = (L(r))*
64
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Expressões Regulares
� Exemplo 8: seja L = {anbm | n ≥ 0, ≥0}, então
� L = {λ,a,b,aa,bb,aab,ab,abb….}
� Considere as Linguagens:
� L1={a} 
� L2={b}
� L3={ak | k ≥ 0}
� L4={bl | l ≥ 0}
� L4={ak bl | k ≥ 0, l ≥ 0}
65
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
L1 e L2 são conjuntos sobre o ∑ = {a,b} e, 
por definição são é uma ER
L3 e L4 são obtidas por concatenação 
sucessiva. L3 = L1* e L4 = L2* e portanto 
são ER
L5 é obtida pela concatenação de L3 e L4 e 
portanto é uma ER denotada por a*b*
Expressões Regulares
� Exemplos de ER e suas linguagens:
66
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
ER Linguagem Representada
aa Somente a cadeia aa
ba* Cadeias que iniciam com b, seguidas por zero ou mais a
(a+b)* Todas as cadeias sobre {a,b}
(a+b)*aa(a+b)* Todas as cadeias contendo aa como subcadeia
a*ba*ba* Todas as cadeias contendo exatamente dois b
(a+b)*(aa+bb) Todas as cadeias que terminam com aa ou bb
(a+λ)(b+ba)* Todas as cadeias que não possuem dois a consecutivos
30/03/2012
23
Principais Leis Algébricas da ER
� Associatividade
� União: (R + S) + T = R + (S + T)
� Concatenação: (R . S) . T = R . (S . T)
� Comutatividade
� União: R + S = S + R
� Concatenação: não se aplica
� Elemento neutro
� União: R + ɸ = ɸ + R = R
� Concatenação: R . ɸ = ɸ . R = R
� Distribuição da concatenação sobre a união
� À esquerda: R . (S + T) = R.S + R.T
� À direita: (R + S) . T = R.T + S.T
67
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
R, S e T são ER 
Gramática Regular
� Uma Gramática Regular é qualquer gramática linear
� Seja G = ( V, T, P, S ) uma gramática e sejam A e B
elementos de V e w uma palavra de T*, então G é:
� Gramática Linear à Direira (GLD) se todas as produções são da forma:
� A � w B ou A � w
� Gramática Linear à Esquerda (GLE) se todas as produções são da forma:
� A � B w ou A � w
� Gramática Linear Unitária à Direira (GLUD) se todas as produções são
como na GLD e | w | ≤ 1.
� Gramática Linear Unitária à Esquerda (GLUE) se todas as produções são
como na GLE e | w | ≤ 1:
68
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Gramática Regular
� Exemplos:
� Seja G = ({S}, {x, y}, P, S ), 
P = { S � xyS, S � x}
� Seja G = ({S1, S2, S3}, {a, b}, P, S1 ), 
P = { S1 � S2ab, S2 � S2ab | S3, S3 � a}
� Seja G = ({S, A, B}, {a, b}, P, S ), 
P = { S � A, A � aB | λ, B � Ab}
69
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
G é uma GLD
G é uma GLE
G não é Linear, então 
não é regular
30/03/2012
24
Gramática Regular
� Se L é uma linguagem gerada por uma Gramática
Regular, então L é uma Linguagem Regular
� Se L é uma Linguagem Regular gerada por uma
Gramática Regular, então existe um Autômato que
reconhece a linguagem gerada
� Se L é uma Linguagem Regular, então existe uma
Gramática Regular que gera L
70
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Gramática Regular
� Exemplo 9: Construir o Autômato capaz de reconhecer
a linguagem gerada por uma Gramática Regular G
� Considere a GLUD, G = ({S, A, B}, {a, b}, P, S), onde P é
S � aA, A � bB | λ, B � aA
� O autômato que reconhece a linguagem gerada por G é:
M = ({S, A, B, qf}, {a, b}, δ, S, {qf}), tal que δ é:
71
Profa. Ellen Souza - https://sites.google.com/site/ellenuastProdução Transição Gerada
S � aA δ (S, a) = A
A � bB δ (A, b) = B
A � λ δ (A, λ) = qf
B � aA δ (B, a) = A
Linguagens Regulares
� Vários caminhos para descrever linguagens regulares:
� AFD, AFN, ER, Gramática Regular
72
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Expressões Regulares
Autômatos Finitos
Gramáticas Regulares
30/03/2012
25
Operações fechadas sobre as Linguagens Regulares
� Diz-se que um conjunto é fechado sobre uma operação
se o elemento obtido como aplicação da operação
pertence ao conjunto. A classe de linguagens regulares
é fechada para:
� União: (L1 ∪ L2) = L3, então L3 é regular
� Concatenação: (L1 . L2) = L3, então L3 é regular
� Complemento: L(M’) = L’, então L’ é regular
� Intersecção: : (L1 ∩ L2) = L3, então L3 é regular
73
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Linguagens Regulares
� Referências
� MENEZES, Paulo Blauth. Linguagens Formais e Autômatos. Série 
Livros Didáticos, 2ª Ed. - Porto Alegre: Sagra Luzzatto, 1999.
� Wikepedia, <pt.wikipedia.org/wiki/Hierarquia_de_Chomsky>
74
Profa. Ellen Souza - https://sites.google.com/site/ellenuast