Expressões Regulares e Autômatos

Prévia do material em texto

AULA 06
Disciplina: Teoria da Computação
Aula 06: Linguagens Regulares E Livres De Contexto
Teoria da Computação, Aula 06 – Conceito de gramáticas livres de contexto, Gramáticas regulares, Autômatos de pilha, Linguagens livres de contexto e suas propriedades, Determinismo, Introdução à análise léxica e sintática.
Orientações
Antes de iniciar a produção do conteúdo, assista atentamente ao vídeo, com orientações de como preencher corretamente os templates de disciplina e de aula: https://goo.gl/NNF8o6 
Apresentação 
Essa aula consiste em apresentar as expressões regulares e suas propriedades, expandir esse conceito com as linguagens regulares e suas particularidades.
Objetivos
· Entender o conceito de expressões regulares
· Definir as características de gramáticas regulares
· Relacionar as propriedades com os autômatos de pilhas e gramáticas livre de contexto
Conteúdo
Expressões Regulares 
Como visto anteriormente, autômatos finitos podem aceitar determinadas linguagens. Dizemos que as linguagens aceitas por um Autômato Finito podem ser descritas por expressões regulares. A definição de expressões regulares envolve operações de união, concatenação e fecho (operações estas que serão descritas a frente). Em álgebra sua definição pode ser descrita como um conjunto A e uma coleção de operações sobre A, operações que podem ser k-árias:
· 0-árias 
· exemplo: constantes, 2, x, y 
· 1-árias 
· exemplo: -10
· 2-árias 
· exemplo: 2+2, 3*y
Operações Regulares
Um autômato finito pode ser definido pelos seguintes conceitos:
Operações Regulares são operações que aplicadas sobre elementos de linguagens regulares resultam em linguagens regulares. São 3 as operações regulares: 
· União
· A ∪ B = {x | x ∈ A ou x ∈ B}
· Concatenação 
· A.B = {xy | x ∈ A e y ∈ B}
· Estrela (ou fechamento, ou fechamento de Kleene)
· A* = {x1x2...xk | k ≥ 0 e cada xi ∈ A}
A união e concatenação são operações binárias, estrela é uma operação unária. 
Exemplos das operações regulares:
União
L = {001, 10, 111} e M = {ε, 001}
L ∪ M = {ε, 10, 001, 111}
Concatenação
L = {001, 10, 111} e M = {ε, 001}
L.M (ou LM) = {001,10,111,001001,10001,111001}
Estrela
L = {0, 11}
L* = {ε, 0, 00, 000, 000, 11, 011, 1111, 00011011, ...
(não há uma ordem lógica aqui)}
Se ∑ é um alfabeto, então ∑* representa todas as sequências formadas com símbolos de ∑.
As expressões regulares relativas a um alfabeto ∑ são definidas recursivamente:
· Ø é uma expressão regular e representa o conjunto Ø
· Є é uma expressão regular e representa {Є}
· Para cada a em ∑, a é uma expressão regular e representa {a}
· Se r e s são expressões regulares, representando as linguagens R e S respectivamente, então (r + s), (rs) e r* são expressões regulares e representam os conjuntos R U S, RS e R*.
A precedência dos operadores é fecho > concatenação > união, onde:
· rr* pode ser abreviada para r+
· quando necessário L(r) é utilizada como notação para a linguagem representada pela expressão regular r.
· exemplos:
· 00 é uma expressão regular representando {00}
· (0 + 1)* representa todas as sequências de 0’s e 1’s
· {0,1}* = {Є, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, 111, ...}
· (0 + 1)* 00 (0 + 1)* representa todas as sequências de 0’s e 1’s com pelo menos dois zeros consecutivos
· (0 + 1)* 011 representa todas as sequências de 0’s e 1’s, terminando em 011
· Constantes:
· ε e Ø são expressões regulares 
· L(ε) = {ε}
· L(Ø) = Ø
· Se a é um símbolo qualquer, a é uma expressão regular
· L(a) = {a}
· União
· Se E e F são expressões regulares, E + F é uma expressão regular
· L(E+F) = L(E) ∪ L(F)
· Concatenação
· Se E e F são expressões regulares, EF é uma expressão regular
· L(EF) = L(E) . L(F)
· Estrela
· Se E é uma expressão regular, E* é uma expressão regular
· L(E*) = (L(E))*
· Parêntesis
· Se E é uma expressão regular, (E) é uma expressão regular
· L((E)) = L(E)
Leis Algébricas para Expressões Regulares
É possível simplificar expressões regulares
Exemplo:	1*0 + 1*0(ε+0+1)*(ε+0+1) = 1*0(0+1)*
Existem algumas leis algébricas que facilitam esse processo como:
· Associatividade e comutatividade 
· L+M=M+L
· Exemplo: 0+1 = 1+0 
· (L+M) + N=L+(M+N)
· Exemplo: (a* + bc) + a = a* + (bc + a) 
· (LM)N=L(MN)
· Exemplo: (00(1+0))111=00((1+0)111)
· Identidades (elemento neutro) e aniquiladores 
· Ø+L=L+Ø=L (Ø é identidade para união) 
· ԐL=LԐ=L (Ԑ é identidade para concatenação) 
· ØL=LØ=Ø (Ø é aniquilador para concatenação)
· Exemplos: 	Ԑa(b + c) + aaԐ = a(b + c) + aa
· 		Ø(Ԑ+1)* (1+0(01* 10(0+1))) + 01 = Ø + 01 = 01
· Leis distributivas 
· L(M+N) = LM+LN 
· (M+N)L= ML+NL
· Exemplos:	0(0+1) = 00 + 01
· 		(0+1)(0+1) = (0+1)0 + (0+1)1
· 		(0+1)(0+1) = 0(0+1) + 1(0+1)
· Lei da idempotência
· L+L=L
· Exemplos:	
· (0+1+ε)+(0+1+ε)=(0+1+ε)
· (0+1+ε)+01*0+(ε+0+1)+(ε+1+0)=(0+1+ε)+01*0
· Leis envolvendo fechamentos
· (L*)*=L*
· Exemplos:	
· ((01)*)*=(01)*
· Ø*=ε 
· ε*=ε
· Operadores de fechamento adicionais
· Exemplos:
· L+= LL*= L*L 
· L*= L++ε 
· L? = ε+L
Autômatos Finitos e Expressões Regulares
Autômatos finitos e expressões regulares representam exatamente o mesmo conjunto de linguagens, as linguagens regulares.
1. Toda linguagem definida por um autômato finito também é definida por uma expressão regular
2. Toda linguagem definida por uma expressão regular é definida por um autômato finito
Para fazer a conversão de um para o outro é necessário seguir o seguinte Teorema:
Se L = L(A) para algum autômato finito determinístico de A, então existe uma expressão regular R tal que L = L(R)
A conversão é complicada e possui dois métodos base:
· Método 1: n3 expressões, com 4n símbolos (dizemos que pior “caso” - método)
· Método 2: eliminação de estados
· Mais simples, porém também trabalhosa 
· Envolve uma notação mista: autômatos + Expressões Regulares
· Autômato finito não-determinístico generalizado 
· Transições são expressões regulares
Conversão entre Autômatos Finitos e Expressões Regulares
Método da eliminação de estados. Todos os estados são eliminados, um por um. Ao eliminar um estado s, todos os caminhos que passam por s não mais existem no autômato. Símbolos são substituídos por Expressões Regulares nas transições para representar as transições eliminadas
Passo-a-passo
Para cada estado de aceitação q, elimine todos os estados, com exceção de q e q0(estado inicial). O resultado será um autômato para cada estado de aceitação.
Cada autômato terá uma Expressão Regular equivalente
Basta fazer a união de todas as expressões
Eliminando um estado s (caso não haja um determinado arco, considerar que existe um arco com rótulo Ø)
Repetir esse procedimento para todos os estados. Ao final, existem duas possibilidades:
· q0=q
· Resta um único estado, com uma transição R 
· R é a expressão regular equivalente
· q0≠q
· Restam dois estados, no formato:
Logo a expressão regular final é (R+SU* T)* SU*
Exemplo:
Passo 1:
Substituir as transições rotuladas 0,1 por 0 + 1
Passo 2: 
Eliminando B (assim ele será reaproveitado em outras reduções)
Q1=1 
P1=0+1 
R11=Ø 
S=Ø
Arco de A para C = R11+Q1S*P1 = Ø+1Ø*(0+1) 
Simplificando: 1(0+1)
Passo 3: 
Eliminando C 
Q1=1(0+1) 
P1=0+1 
R11=Ø 
S=Ø
Arco de A para D = R11+Q1S*P1 = Ø+1(0+1)Ø* (0+1)
Simplificando: 1(0+1)(0+1)
Passo 4:
Restou um autômato de 2 estados 
R=0+1
S=1(0+1)(0+1) 
U=Ø
T=Ø
Fórmula: (R+SU* T)* SU*
Resultado: (0+1+1(0+1)(0+1)Ø*Ø)* 1(0+1)(0+1)Ø*
Simplificando: (0+1)* 1(0+1)(0+1)
Passo 4:
Eliminando D
· Não há sucessor, portanto não haverá mudanças de arcos
· Da mesma forma, restou um autômato de 2 estados.
· Expressão regular resultante: (0+1)*1(0+1)
Resultado:
Haviam dois estados de aceitação, foram obtidos dois autômatos, duas expressões regulares equivalentes. A expressão regular final é a união dessas duas: 
(0+1)* 1(0+1)+(0+1)* 1(0+1)(0+1)
Linguagens Não Regulares
As linguagens regulares são aquelas reconhecidas por autômatos finitos, porém não foi realizada nenhuma definição do que é uma linguagem regular
· Um ser humano, ao olhar para uma linguagem, dificilmenteconsegue dizer se é ou não regular
· Na verdade, não existe definição, mas existe uma distinção
· Linguagens regulares vs não-regulares 
· A linha divisória é o fato de que autômatos finitos não conseguem contar
Linguagens que exigem um contador
São exemplos de linguagens que exigem contador:
· comentários dentro de comentários, escopos aninhados em uma linguagem, parêntesis aninhados.
· (1+2*(3-5+(7*7)) - 6)
· É preciso contar quantos parêntesis são abertos e quantos são fechados
· Logo, para reconhecer infinitos níveis de parêntesis aninhados seriam necessários infinitos estados. Para resolver esse problema surge o lema de bombeamento para linguagens regulares, permitindo definir exatamente quais linguagens não são regulares
Bombeamento para Linguagens Regulares
Se a linguagem é regular, então ela é aceita por um autômato finito determinístico que possui um número finito n de estados. Porém se o autômato finito determinístico aceita uma cadeia w de comprimento maior que n, obrigatoriamente o autômato tem algum estado q que é percorrido mais de uma vez (formando um ciclo). Logo, w = uvz e tem-se que uviz pertencerá a linguagem para todo i>=0.
Se L é uma linguagem regular, então existe uma constante n (o comprimento de bombeamento) tal que para qualquer cadeia w de L de comprimento no mínimo n (|w|>=n), então w pode ser dividida em três partes, w=uvz, satisfazendo as seguintes condições:
· Para cada i ≥ 0, uviz ∈ L
· |v| > 0
· |uv| ≤ n
Informalmente toda cadeia da linguagem contém uma parte que pode ser repetida um número qualquer de vezes (bombeada), com a cadeia resultante permanecendo na linguagem. Essa repetição ou bombeamento é a característica que faz com que seja sempre possível definir um número finito de estados para um autômato que reconheça a linguagem
Uso do lema do bombeamento: 
· Provar que B não é regular
· Contradição: suponha que B seja regular
1. Encontre um p de forma que todas as cadeias de comprimento p ou maiores possam ser bombeadas
2. Encontre uma cadeia s em B que tenha comprimento p ou mais, mas que não possa ser bombeada
3. Demonstre que s não pode ser bombeada considerando todas as maneiras de dividir s em x, y e z, conforme o lema.
Operações Fechadas sobre as Linguagens Regulares
Utilizadas para construir novas linguagens regulares a partir de linguagens regulares conhecidas, como provar propriedades, construir algoritmos.
A classe das linguagens regulares é fechada para diversas operações, com destaque para:
· União
· Concatenação
· Complemento
· Intersecção
Linguagem Regular Vazia, Finita ou Infinita
Uma linguagem regular L aceita por um autômato finito M=(Q,Ʃ,δ,q0,F) com n estados, então L é:
a) Vazia se e somente se M não aceita qualquer palavra w tal que |w| < n;
b) Finita se e somente se M não aceita alguma palavra w tal que n <= |w| <= 2n;
c) Infinita se e somente se M aceita uma palavra w tal que n <= |w| <= 2n.
	
Atividades 
Atividade do objetivo 1:
Descreva a Expressão Regular equivalente ao autômato representado pelo diagrama descrito a seguir:
Gabarito comentado: 
Resposta: 		 
a(aa)* bc* d
Atividade do objetivo 2:
Descreva a Expressão Regular equivalente ao autômato representado pelo diagrama descrito a seguir:
Gabarito comentado: 
Resposta:
a(cd)* ba(ba)*
Atividade do objetivo 3:
Construa o autômato finito determinístico para a Expressões Regular ab(bb)*cc*
Gabarito comentado: 
Resposta:
O Autômato Finito gerado com base na expressão regular dada foi realizado
Atividade do objetivo 4:
Construa o autômato finito determinístico para a Expressões Regular cc*b*+ab*cc*
 
Gabarito comentado
Resposta:
O Autômato Finito gerado com base na expressão regular dada foi realizado
Atividade do objetivo 5:
Construa o autômato finito determinístico para a Expressões Regular bcc*(b+a)*
Gabarito comentado
Resposta:
O Autômato Finito gerado com base na expressão regular dada foi realizado
Referências
Introdução à teoria dos Introdução À Teoria Dos Autômatos, Linguagens E Computação by Hopcroft, Ullman and Motwani; tradução da 2.ed. original de Vandenberg D. de Souza. – Rio de Janeiro : Elsevier, 2002 (tradução de: Introduction to automata theory, languages, and computation – ISBN 85-352-1072-5 )
Introdução à teoria da Computação / Michael Sipser; tradução técnica Rui José Guerra Barretto de Queiroz ; revisão técnica Newton José Vieira. – São Paulo: Thomson Learning, 2007 (Título original : Introduction to the theory of computation. “Tradução da segunda edição norte-america” – ISBN 978-85-221-0499-4)
Próxima aula
· Igualdade de Linguagens Regulares, Minimização de Autômato Finitos Determinísticos e Autômato Finito com saída
· Linguagens Livre de Contexto e Autômatos com Pilha
· Análise Léxica
Explore +
MENEZES, P. B., Linguagens Formais e Autômatos, 4a. ed., Editora Sagra Luzzatto,2001.
ANDERSON, J. A., Automata Theory with Modern Applications, 1st. ed., Cambridge University Press, 2006.
3
image2.png
image3.png
image4.png
image5.png
image6.png
image7.jpg
image8.jpeg
image9.jpg
image10.jpeg
image11.jpg
image12.jpeg
image13.jpg
image14.jpeg
image15.png
image16.jpg
image17.jpeg
image18.png
image19.png
image20.png
image21.png
image22.png
image23.png
image1.png
image24.jpeg