I - Noções dum compilador
•
•
•
•
Linguagens formais
Autómatos finitos
Expressões regulares
Bibliografia aconselhada:
– Apontamentos
Jorge Morais
LFA 1999/2000 - 1
Monóide
• Grupóide:
– Par (A, . ), onde A é um conjunto, e . Representa
uma operação binária em A.
• Semigrupo:
– Grupóide em que . é associativa, isto é,
a (b c) = (a b) c
• Monóide:
– Semigrupo com elemento neutro e:
aA : a e = e a = a
Jorge Morais
LFA 1999/2000 - 2
Palavras
• Alfabeto:
–  conjunto finito
• Palavra (sequência finita de elementos de )
–  é a palavra vazia
– a1 a2 ... an (ai  ) representa uma palavra não
vazia
– Convenção: an = a a ... a (n vezes, n>0); a0 = 
Jorge Morais
LFA 1999/2000 - 3
Palavras (cont.)
• Comprimento duma palavra
– |a1 a2 ... an| = n
– || = 0
• Conteúdo duma palavra:
– cont(a1 a2 ... an) = {a1, a2, ..., an}
– cont() = 
Jorge Morais
LFA 1999/2000 - 4
Monóide livre
•  * - Monóide livre em 
–  * (conjunto das palavras em )
– Concatenação (operação binária associativa)
• (a1 a2 ... an)(an+1 an+2 ... an+k)=a1 a2...an an+1 an+2...an+k
–  (elemento neutro)
• (a1 a2 ... an)  =  (a1 a2 ... an) = a1 a2 ... an
•  + =  * \{} - Semigrupo livre em 
Jorge Morais
LFA 1999/2000 - 5
Prefixo, sufixo, factor
•
•
•
•
Sejam u, v  *
u é prefixo de v  v = uw  w  *
u é sufixo de v  v = wu  w  *
u é factor de v  v = wuz  w,z  *
Jorge Morais
LFA 1999/2000 - 6
Autómato finito
• Um autómato é um vector (S, , i, F, ):
–
–
–
–
–
S   - conjunto finito de estados
 - alfabeto
i  S - estado inicial
F  S - conjunto de estados finais
 : S x   S (função parcial) - conjunto de
transições
Jorge Morais
LFA 1999/2000 - 7
Representação gráfica
Jorge Morais
LFA 1999/2000 - 8
Tipos de autómatos
• Seja A=(S, , i, F, ) um autómato finito.
• A diz-se autómato finito determinístico se, perante
um símbolo x de , puder transitar, no máximo,
para um único estado, isto é:
– ( (s, x, s’)   (s, x, s’’)  )  s’ = s’’
• Caso contrário, A diz-se não determinístico
• A diz-se autómato finito  se é possível transitar
de estado sem usar nenhum símbolo de , isto é:
•   S x ({}) x S
Jorge Morais
LFA 1999/2000 - 9
Caminho e rótulo
• Seja A=(S, , i, F, ) um autómato finito.
• Um caminho não trivial é uma sequência
(s0, a1, s1), (s1, a2, s2), ..., (sn-1, an, sn) onde
(si-1, ai, si)  
• Um caminho trivial é uma tripla da forma
(s, , s), com s  S
• O rótulo do caminho é a1 a2 ... an
Jorge Morais
LFA 1999/2000 - 10
Linguagem reconhecida
• Seja A=(S, , i, F, ) um autómato finito.
• Um caminho diz-se bem sucedido se
começa num estado inicial e termina num
estado final
• Linguagem reconhecida por A:
– L(A) = {u  * : u é o rótulo de um caminho
bem sucedido em A}
Jorge Morais
LFA 1999/2000 - 11
Exemplo de autómato
•
•
•
•
•
•
A=(S, , i, F, )
 = {0, 1}
S = {i,f}
F={f}
 = {(i,0,i), (i,1,i), (i,0,f)}
Este autómato finito (não determinístico)
reconhece todas as sequências terminadas
em 0 (números binários pares)
Jorge Morais
LFA 1999/2000 - 12
Exemplo de autómato (cont.)
•
•
•
•
•
•
A=(S, , i, F, )
 = {0, 1}
S = {i,f}
F={f}
 = {(i,0,f), (i,1,i), (f,0,f), (f,1,i)}
Este autómato finito também reconhece
todas as sequências terminadas em 0, mas é
determinístico
Jorge Morais
LFA 1999/2000 - 13
Expressões regulares
• Uma expressão regular E representa um
subconjunto de * que designamos por c(E)
• Sendo L  * uma linguagem. As seguintes
condições são equivalentes:
–
–
–
–
L é reconhecida por um autómato finito
L é reconhecida por um autómato finito determinístico
L é reconhecida por um autómato finito 
L é reconhecida por uma expressão regular
Jorge Morais
LFA 1999/2000 - 14
Expressões regulares (cont.)
• Uma expressão regular tem uma das
seguintes formas:
–
–
–
–
  c() = 
  c() = {}
a    c(a) = {a}
Sendo E1 e E2 expressões regulares:
• E1 + E2  c(E1 + E2) = c(E1)  c(E2)
• E1 E2  c(E1 E2) = c(E1) c(E2)
• E1*  c(E1*) = {a1 a2 ... an : n  0, a1, a2, ..., an  E1}
Jorge Morais
LFA 1999/2000 - 15
Exemplo de expressões regulares
• Considerando  = {0, 1}
• (0 + 1)* 0 - sequências terminadas em 0
• 0* (100*)* (1 + ) - sequências em que não
aparecem 1’s consecutivos
• (0 + 1)* 101 (0 + 1)* - sequência que contem
o factor 101
• 10 (0 + 1)* - sequência com prefixo 10
Jorge Morais
LFA 1999/2000 - 16