LINGUAGENS FORMAIS E AUTÔMATOS
O objetivo deste curso é formalizar a idéia de linguagem e definir os tipos de sintaxe e semântica. Para
cada sintaxe, analisamos autômatos, que são abstrações de algoritmos. Dentre as classes de linguagens
temos:
Regulares ⊆ Livres de contexto ⊆ Sensíveis ao contexto ⊆ Recursivas ⊆ Recursivamente
enumeráveis
O curso de Linguagens Formais e Autômatos se ocupa principalmente dos primeiros, enquanto os dois
últimos são objetivo de um curso de Computabilidade.
Uma linguagem comum é um conjunto de três aspectos:
• Aspecto léxico – Define os símbolos (signos) que compõe a linguagem.
• Aspecto Sintático – Define regras para símbolos que indicam que seqüências de símbolos são
aceitas.
• Aspecto Semântico – Dá o significado das seqüências de símbolos.
Nosso curso se concentra nos dois primeiros aspectos, que são vitais para a construção de compiladores.
Podemos definir linguagem como:
1. Linguagem é um conjunto de sentenças.
2. Sentença sobre um vocabulário é uma seqüência finita de símbolos do vocabulário.
3. Vocabulário é um conjunto finito de símbolos.
Por enquanto, definimos uma linguagem só definindo seu aspecto léxico. Assim, se queremos definir uma
linguagem para uma calculadora, definimos o alfabeto (vocabulário):
∑
= {+ , - , * , / , NUM}
Sentenças sobre esse vocabulário são:
W1 = NUM * NUM + NUM
W2 = + * NUM
Uma linguagem é um subconjunto do conjunto das sentenças. Podemos considerar somente:
L = { NUM , NUM + NUM , NUM * NUM ...}
A linguagem pode ser definida de forma recursiva:
NUM ∈ L
α β ∈ L ⇒ α + β , α - β , α * β , α / β ∈L
E
E
E
E
E
→
→
→
→
→
NUM
E+E
E-E
E*E
E/E
Assim também:
E → E + E → E * E + E → E * E + NUM → E * NUM + NUM → NUM * NUM + NUM
Definimos sobre o conjunto de sentenças a operação de concatenação. Por exemplo:
W1 = ++*
W2 = NUM
W1 W2 = ++*NUM
Dado um alfabeto (vocabulário)
∑
, definimos
∑
*
como o conjunto de todas possíveis sentenças,
incluindo ε que representa a sentença vazia. Dessa forma, toda linguagem é:
L⊆ ∑ *
Definimos também
∑
+
= ∑ */{ε } , ou seja, o conjunto de todas possíveis sentenças não vazias. No
nosso exemplo do vocabulário da calculadora:
∑ * = {ε , +, −, +,*, /, +−, +*, ++, + NUM , −−,...}
Em seguida, vamos definir o que é uma gramática, uma linguagem gerada por uma gramática. A cada tipo
de linguagem (definida pelo seu tipo de gramática) e a cada um dele vamos associar um autômato.
Linguagem
Regulares
Livres de Contexto
Sensíveis ao Contexto
Sem Restrição
Autômato
Autômato Finito
Autômato com pilha
Máquina de Turing Linearmente Limitada
Máquina de Turing
Definimos uma gramática G como uma 4-tupla G = 〈
∑
∑
, N , P , S 〉 , onde:
= Alfabeto de símbolos terminais.
N = Conjunto de símbolos não terminais.
P = Conjunto de regras de produção, da forma: α → β , α , β ∈ (∑ ∪ N )* e α tem ao menos um símbolo
de N.
S = Símbolo inicial. S ∈ N.
Para a linguagem que definimos, uma gramática adequada seria:
∑
= {+ , - , * , / , NUM}.
N = {E}
P ={ E → NUM , E → E + E , E → E – E , E → E * E , E → E / E}
S=E
Dada uma gramática, definimos em (∑ ∪ N )* a relação binária __________ em um passo (⇒G ) como:
⎧ w1 = γ 1.α .γ 2
⎪
( w1 ⇒G w2) ⇔ ⎨ w2 = γ 1.β .γ 2
⎪(α → β ) ∈ P
⎩
Onde γ 1, γ 2, α , β ∈ (∑ ∪ N )* . Seja (⇒G ) * o fecho reflexivo de (⇒G ) . Assim definimos a linguagem
gerada pela gramática G como
L(G) = {w ∈ ∑ */ s ⇒G *w}
Por exemplo, a linguagem composta pelas seqüências binárias ε , 0, 1, 00, 01, 10, 11, 000, 001,... pode
ser gerada pela seguinte gramática:
∑ = {0,1}
N = {S }
P = {S → S1, S → S 0, S → 0, S → 1}
S=S
Assim, 010 ∈ L(G ) .
Um problema é, dada um alfabeto ∑ e uma gramática G, como decidir se uma sentença w ∈ ∑ * pertence
ou não à linguagem L(G). Isso normalmente é feito usando autômatos. Analisemos alguns antes de definir
formalmente o que é um autômato sobre ∑ ={0, 1}.
1. O seguinte autômato reconhece todas as sentenças com um número par de zeros:
Onde
representa um estado e
“máquina” pode parar.
um estado final, ou seja, um ponto em que o funcionamento da
2. Seqüências de 0’s e 1’s que têm um número par de 0’s ou um número ímpar de 1’s.
3. Seqüências que terminam em 01
4. Seqüências que tem o comprimento múltiplo de 3.
5. O antepenúltimo caractere é 1. Para organizar o raciocínio, vamos chamar os estados de qa ,b ,c , onde
a,b,c ∈ {x, 1}, onde x representa qualquer coisa diferente de 1, seja 0 ou nenhum resultado.
Definição: Um autômato finito determinístico é uma 5-upla M = {Q, ∑, δ , q0 , F } onde:
•
•
•
Q é o conjunto finito de estados
∑ é o alfabeto de entrada
q0 ∈ Q é o estado inicial
•
F ⊆ Q é o conjunto de estados finais.
No exemplo das linguagens que terminam em 0 e 1 temos:
∑ = {0,1}
Q = {q0 , q1 , q2 }
F = {q2 }
A função δ : Q × ∑ → Q é dada pela seguinte tabela:
⇒ q0
0
q1
1
q0
q1
q1
q2
* q2
q1
q0
^
Definamos recursivamente a função δ : Q × ∑* → Q sobre o conjunto das seqüências como:
^
δ ( q, ε ) = q
^
^
δ (q, aω ) = δ (δ (q, a), ω ), onde a ∈ ∑, ω ∈ ∑ *
Assim, para o exemplo que estávamos discutindo:
^
^
^
δ (q0 ,101) = δ (δ (q0 ,1), 01) = δ (q0 , 01) =
^
^
^
^
= δ (δ (q0 , 0),1) = δ (q1 ,1) =
= δ (δ (q1 ,1), ε ) = δ (q2 , ε ) = q2
^
Na prática, δ (q, ω ) representa o estado alcançado a partir de q pelo caminho ω . Assim, definimos o
conjunto de linguagens reconhecidas por M como:
^
T ( M ) = {ω ∈ ∑ *, δ (q0 , ω ) ∈ F }
Exercícios
Fazer um autômato finito que reconheça
i. ω ∈ {0,1}*, tal que termina em 01 ou tem um número par de 0’s.
ii. ω ∈ {0,1}*, tal que ω é a representação binária de um número múltiplo de 5.
iii. ω ∈ {0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F,x}, tal que ω é um inteiro positivo na linguagem C. Por
exemplo:
235 – inteiro
075 – octal
0x7FF – hexadecimal
O problema i tem uma solução com somente 4 estados que é:
q0 : número par de 0’s
qix 0 : número ímpar de 0’s terminando em 0
qi 01 : número ímpar de 0’s terminando em 01
qi11 : número ímpar de 0’s terminando em 11
Uma pergunta natural seria qual a gramática reconhecida pelo autômato finito do problema iii, ou seja,
que linguagem descreve os números inteiros da linguagem C? Dando nome aos estados temos:
S → 0Z
S → D ec * D
D → D ec D
Isso nos dá uma receita para a construção de uma gramática que gera a linguagem
reconhecida por um autômato finito. Isso nos dá uma prova construtiva para:
Teorema: Dado um autômato finito M = {Q, ∑, δ , q0 , F } , construo um não
D → ε
Z → xX
terminal N q para cada q e considero a gramática G = 〈
X → H ex H
H → H ex H
N = {N q / q ∈ Q} e
H → ε
Z → O ct O
~
∑
, N , P , S 〉 , onde
~
P = {N q → aN q / δ (q, a ) = q} ∪ {N q → ε / q ∈ F } .
Assim, nestas condições L(G) = T(M).
O → O ct O
O → ε
Classificação das gramáticas
Gramática Regular
Dizemos que uma gramática é regular quando todos os elementos de P são da forma:
A→a
A → aB
A →ε
para A ∈ ∑ e A,B ∈ N
Gramática Livre de Contexto
Dizemos que uma gramática é livre de contexto se todas as regras são da forma:
A → ω , com A ∈ N e ω ∈ ( N ∪ ∑) *
Gramática Sensível ao Contexto
Dizemos que uma gramática é sensível ao contexto quando todos os elementos de P são da forma:
ω1 → ω2 , com ω1 , ω2 ∈ ( N ∪ ∑) *
e ω1 ≤ ω2
Note que, por essa definição, Regulares são Livres de contexto, mas não
são necessariamente sensíveis ao Contexto, pois elas podem ter a regra
A → ε , onde 1= A > ε = 0 . Para corrigir esse defeito, redefinimos
gramática sensível ao contexto como gramáticas cujas sentenças têm a
forma:
ω1 → ω2 , ω1 ≤ ω2 ou
S → ε , onde S é um símbolo não terminal, que não aparece do lado
direito de nenhuma regra. Isso permite que linguagens sensíveis ao
contexto tenham a sentença vazia.
Dizemos que uma linguagem L é regular (respectivamente sensível ao contexto, livre de contexto) se
existe uma gramática regular (respectivamente sensível ao contexto, livre de contexto) tal que L = L(G),
ou seja, L é a linguagem gerada pela gramática.
Quando passamos para linguagens, passamos a ter inclusões.
O diagrama da direita é chamado hierarquia de Chomsky. Dois fatos interessantes: nem toda gramática
livre de contexto é sensível ao contexto, mas toda linguagem livre de contexto é sensível ao contexto. Isso
acontece pois, dada uma gramática G livre de contexto mas com alguma regra do tipo A → ε , ou seja,
~
que não seja sensível ao contexto, então, como provaremos mais tarde, existe uma gramática G livre de
contexto e sensível ao contexto tal que:
~
L(G) = L( G )
Assim, provaremos que toda linguagem livre de contexto é sensível ao contexto. Isso será feito mais
tarde.
Outro fato interessante: nem todas as linguagens podem ser descritas por gramáticas. Provemos isso.
Dado um alfabeto finito ∑ , o conjunto das possíveis sentenças ∑ * é um conjunto infinito e enumerável.
Uma linguagem L é um subconjunto de ∑ * , logo o conjunto das possíveis linguagens é o conjunto das
partes de ∑ * , ou seja, o conjunto de todos os subconjuntos de ∑ * . Mas esse é um conjunto não
enumerável (Prova diagonal de Cantor).
Como toda gramática pode ser definida por uma cadeia finita de caracteres, o conjunto das possíveis
gramáticas é enumerável. Assim, existem linguagens que não podem ser descritas por gramáticas.
Queremos resolver o problema da análise sintática, isto é, dada uma gramática G e uma sentença
ω determinar se ω ∈ L(G) e, em caso afirmativo, saber qual a derivação.
Vimos que, dado um autômato finito podemos construir uma gramática G regular tal que L(G) é a
linguagem reconhecida pelo autômato. Será que vale a recíproca? Ou seja, dada uma gramática G, existe
um autômato finito cuja linguagem reconhecida por ele é L(G)?
Considere a linguagem L(G), formada pelas seqüências em {0,1}* que terminam em 0 ou 01. Temos que
a gramática pode ser dada por:
S → 0S
S → 1S
S →0
S → 0A
A →1
Tentando aplicar o algoritmo para transformar autômatos em linguagens, chegamos a:
Isso não é um autômato finito, pois a função de transição δ não está bem determinada. Assim, o que
temos é um autômato finito não determinístico.
Outro exemplo de autômato finito não determinístico é o seguinte, que reconhece todas as cadeias com
um número ímpar de 0’s ou um número ímpar e1’s.
Para que um autômato finito não determinístico reconheça uma sentença, deve existir um caminho que
leve ao estado final partindo do estado inicial. Vejamos nos exemplos:
i. Seqüências que terminam em 01.
ii. Seqüências cujo antepenúltimo caractere é 0.
iii. Seqüências que terminam em 01 ou têm um número par de 0’s.
Outra maneira é tomar
Assim, se temos dois autômatos finitos não determinísticos, podemos criar um autômato que reconheça a
linguagem de um ou de outro, que pode ser gerado por:
Onde o novo estado inicial q0 se liga aos estados dos dois autômatos da mesma forma que os estados
iniciais dos autômatos 1 e 2 se ligavam
Assim, se temos autômatos M 1 e M 2 com m1 e m2 estados, respectivamente, um autômato finito não
determinístico que reconhece M 1 ou M 2 tem no máximo m1 + m2 + 1 estados, enquanto um autômato
finito determinístico deveria ter no máximo m1 • m2 estados. Assim, a cota superior é menor para
autômatos finitos não determinísticos.
A definição formal de autômato finito não determinístico é uma 5 – upla M = {Q, ∑, δ , q0 , F } onde:
• Q é o conjunto finito de estados
• ∑ é o alfabeto de entrada
• δ : Q × ∑ → P(Q) : Função de transição
• q0 ∈ Q é o estado inicial
F ⊆ Q é o conjunto de estados finais.
•
Note que o AFND (Autômato Finito Não Determinístico) é bastante semelhante ao determinístico, porém
um estado q e um símbolo a ∈ ∑ levam, não a um estado, mas a um conjunto de estados. Dessa forma,
definimos a linguagem reconhecida por um AFND M = {Q, ∑, δ , q0 , F } como:
^
T ( M ) = {ω ∈ ∑ */ δ (q0 , ω ) ∩ F ≠ 0}
^
Onde δ : Q × ∑ → P(Q) é definido recursivamente como:
^
δ (q, ε ) = {q}
^
^
δ (q, aω ) = ∪ δ (r , ω )
r∈δ ( q , a )
Por exemplo, para o AFND ao lado calculamos:`
^
^
^
δ (q0 , 01) = δ (q0 ,1) ∪ δ (q1 ,1)
^
^
= δ (q0 , ε ) ∪ δ (q2 , ε )
= {q0 } ∪ {q2 } = {q0 , q2 }