Linguagens Formais e Autômatos – Profº André Mendes Garcia Página.: 1
LINGUAGENS FORMAIS E AUTÔMATOS
Introdução
A teoria das linguagens formais foi originariamente desenvolvida na década de 1950 com o
objetivo de desenvolver teorias relacionadas com as linguagens naturais. Entretanto, logo foi
verificado que esta teoria era importante para o estudo de linguagens artificiais e, em especial,
para as linguagens originárias na Ciência da Computação. Desde então, o estudo das linguagens
formais desenvolveu-se significativamente e com diversos enfoques, com destaque para
aplicações em Análise Léxica1 e Sintática2 de linguagens de programação, modelos de sistemas
biológicos, desenhos de circuitos e relacionamentos com linguagens naturais.
Conceitos Básicos de Linguagens Formais
Alfabeto
É qualquer conjunto finito, não vazio, de símbolos (ou letras). Um alfabeto geralmente é
denotado por ∑ Exemplos:
∑ = {0, 1}, o alfabeto binário;
∑ = {a, b, c, ......,z}, o conjunto das letras minúsculas.
Palavra
Palavra ou cadeia, é qualquer seqüência finita de símbolos de um alfabeto ∑. A palavra
vazia contém zero ocorrências de símbolos e é habitualmente denotada por ε.
Denota-se o comprimento da palavra w por |w| e |ε| = 0.
1 Análise Léxica: É o estágio na tradução de um programa quando o software de compilação ou tradução substitui palavras-chave do programa por instruções de código de máquina 2 Análise Sintática: Trata da verificação gramatical de programas.
Linguagens Formais e Autômatos – Profº André Mendes Garcia Página.: 2
Potências de um Alfabeto
Denotamos ∑k o conjunto de todas as palavras de comprimento K, sobre um alfabeto
∑ .
Exemplos, para o alfabeto ∑ = {0,1}:
∑0 = {ε}
∑1 = {0,1}
∑2 = {00,01,10,11,}
∑3 = {000,001,010,011,100,101,110,111}
O conjunto de todas as palavras sobre o alfabeto ∑ denota-se habitualmente por ∑* ,
∑* = ∑0 ∪ ∑1 ∪ ∑2 ∪ .......
ou seja,
∑* = {ε, 0, 1, 00, 01, 10, 11, 000, 001,.......}
Excluindo a palavra vazia, obtemos ∑+ , ou seja,
∑+ = ∑1 ∪ ∑2 ∪ .......
∑* = ∑+ ∪ {ε}
Prefixo, Sufixo, Subpalavra
Um prefixo de uma palavra é qualquer seqüência inicial desta palavra. Um sufixo é
qualquer seqüência final desta palavra. Uma subpalavra de é qualquer seqüência de símbolos
contínua desta palavra.
Exemplo:
Linguagens Formais e Autômatos – Profº André Mendes Garcia Página.: 3
Sendo w = abcb uma palavra do alfabeto {a, b, c}
Então
ε, a, ab, abc, abcb são os prefixo de w ;
ε, b, cb, bcb, abcb são os sufixos de w ;
Qualquer prefixo ou sufixo de uma palavra é uma subpalavra.
Concatenação
Justapondo duas palavras v e w obtemos vw. A palavra vazia é o elemento identidade da
operação, isto é, wε = εw = w
A concatenação sucessiva de uma palavra (com ela mesma), representada na forma de
um expoente wn onde w é uma palavra e n indica o número de concatenações sucessivas.
Exemplo:
Sendo a palavra w = ab
W1 = ab, w2 = abab, w3 = ababab, ……
Linguagem Formal
Uma Linguagem Formal é um conjunto de palavras sobre um alfabeto.
Exemplo1: Suponha o alfabeto ∑ = {a, b}. Então:
a) O conjunto vazio e o conjunto formado pela palavra vazia são linguagens sobre ∑.
b) O conjunto de palíndromos (palavras que têm a mesma leitura da esquerda para a direita
e vice-versa) sobre ∑ é um exemplo de linguagem infinita. Assim, ε, a, b, aa, bb, aaa, aba,
bab, bbb, aaaa, ..... são palavras desta linguagem.
Exemplo de Linguagens
- Português
- C (o conjunto de todos os programas em C, sintaticamente corretos)
Linguagens Formais e Autômatos – Profº André Mendes Garcia Página.: 4
Exemplo2:
Para o alfabeto ∑ = {0, 1}, define-se as seguintes linguagens:
- L = {w | w contém o mesmo número de 0’s e 1’s}
- L = {w | w representa um número primo em binário}
MÁQUINAS DE ESTADO-FINITO
As máquinas de estado-finito são máquinas abstratas que capturam as partes essenciais
de algumas máquinas concretas. Estas últimas vão desde máquinas de vender jornais e de verder
refrigerantes, passando por relógios digitais e elevadores, e até programas de computador, como
alguns procedimentos de editores de textos e compiladores.
Existem, basicamente, dois tipos de máquinas de estado-finito: os tradutores e
reconhecedores (ou aceitadores) de linguagens. Os tradutores são máquians com entrada e
saída, e os reconhecedores são máquinas com apenas duas saídas possíveis (Aceitação,
Rejeição).
As máquinas de estado-finito que começaremos a estudar são os reconhecedores
(aceitadores) de linguagens regulares. São máquinas que dada uma linguagem, sobre um
alfabeto, e uma palavra desta linguagem, aceitam ou rejeitam esta palavra para tal linguagem, ou
seja, determinam se esta palavra pertence ou não a linguagem.
Os tradutores são mais conhecidos por Autômatos Finitos com Saída e os
reconhecedores de linguagens são mais conhecidos por Autômatos Finitos.
Para dar uma idéia do que vem a ser autômato finito antes de sua definição formal, e
também para introduzir os principais conceitos e a terminologia associada, serão usados alguns
exemplos bem simples.
Um quebra-cabeças: Um homem, um leão, um coelho e um repolho devem atravessar um
rio usando uma canoa, com a restrição de que o homem deve transportar no máximo um dos três
de cada vez de uma margem à outra. Além disso, o leão não pode ficar na mesma margem que o
coelho sem a presença do homem, e o coelho não pode ficar com o repolho sem a presença do
homem.
Para tanto, algumas notações devem ser levadas em consideração para a facilitação do
entendimento do autômato. As letras h significa o homem, l – leão, c – coelho, r – repolho. Por
exemplo, {h, c, r} representa a situação em que o homem, o coelho e o repolho estão na margem
esquerda e o leão na margem direita. Uma outra notação que devemos levar em consideração é a
Linguagens Formais e Autômatos – Profº André Mendes Garcia Página.: 5
movimentação de estados, por exemplo, s representa o homem atravessando o rio sozinho, l –
levando o leão, c – levando o coelho, r – levando o repolho.
Para economizar tempo não vamos passar pela construção do autômato e vamos direto à
sua representação final.
O objetivo do autômato-finito acima é reconhecer as palavras do alfabeto {s, l, c, r} que
respeitam as condições básicas do quebra-cabeça, portanto as condições básicas do quebra
cabeça seria a linguagem para a qual este autômato reconheceria palavras.
Qual é o procedimento para o reconhecimento da linguagem ?? Partindo-se do estado
inicial, se chagar ao estado final a palavra é aceita, portanto a linguagem é reconhecida, caso não
é rejeitada.
Portanto, o conjunto de todas as soluções para o quebra-cabeças é o conjunto das
palavras correspondentes aos caminhos do estado inicial ao estado final. Cada palavra é formada
concatenando-se os rótulos das arestas percorridas no caminho do estado inicial ao estado final.
Pela figura acima, fica evidente que existe um conjunto infinito de soluções, e que existem duas
soluções de tamanho mínimo: cslcrsc e csrclsc.
Dada uma palavra w de {s, l, c,r}*, como saber se w é solução ? Evidentemente, deve-se
verificar se o “caminho correspondente” a w par partindo do estado inicial chega ao estado final; se
chegar, w é solução, caso contrário, não é.
Estado Inicial
Estado Final
Linguagens Formais e Autômatos – Profº André Mendes Garcia Página.: 6
AUTÔMATOS FINITOS DETERMINÍSTICOS (AFD)
Um Autômato Finito Determinístico é um quíntuplo ordenado,
A = (Q, ∑, δ, q0, F) onde:
- Q é um conjunto finito, não vazio de estados
- ∑ é um conjunto finito (alfabeto) de símbolos de entrada
- δ : Q x ∑ → Q é a função (parcial) de transição ou de mudança de estado. Fornece para
cada par (estado, símbolo de entrada da palavra) um novo estado para onde o autômato finito
deve-se mover.
- q0 ∈ Q é o estado inicial
- F ⊂ Q é o conjunto dos estados finais ou de aceitação
É Finito porque o número de estados envolvidos no sistema é finito, e é Determinístico
porque a cada símbolo lido de uma palavra de entrada, apenas um estado novo é escolhido.
Exemplo1: Sobre o alfabeto ∑ = {0, 1}, consideremos a linguagem,
L = { w ∈ ∑* | a seqüência 01 é parte de w}
Pretendemos construir um Autômato Reconhecedor das palavras de L. Uma dada
palavra w ∈ ∑* pertence a L, se e somente se, partindo do estado inicial o Autômato atinge o
estado final, (de aceitação ou de reconhecimento) de w.
A linguagem de um AFD é o conjunto de todas palavras por ele reconhecida.
Representação do AFD: A = ( {q0, q1, q2}, {0, 1}, δ, q0, {q1} )
O Autômato Finito pode ser representado por um Diagrama de Transições (que é um grafo
dirigido) ou pela Tabela de Transições.
Diagrama de Transições: Tabela de Transições:
Linguagens Formais e Autômatos – Profº André Mendes Garcia Página.: 7
O processamento de uma dada palavra é feito lendo símbolo a símbolo da esquerda para a
direita. A cada símbolo lido a função de transição δ fornece um novo estado dependendo do
símbolo lido.
Por exemplo, a palavra w = 1100111 é reconhecida pelo autômato acima. Pois chega-se ao estado
final do autômato;
δ(q0,1) = q0
δ(q0,1) = q0
δ(q0,0) = q2
δ(q2,0) = q2
δ(q2,1) = q1
δ(q1,1) = q1
δ(q1,1) = q1
Exemplo2: Também sobre o alfabeto ∑ = {0, 1}, consideremos a linguagem,
L = { w ∈ ∑* | a seqüência 001 é parte de w}
FUNÇÃO DE TRANSIÇÃO ESTENDIDA ( δ* ou δ̂ ou δ )
É uma forma compacta de descrever um conjunto de transições resultantes de leitura de
uma cadeia (palavra) de entrada.
Em contraposição à função de transição do autômato, ao invés de seu segundo argumento
ser um símbolo da cadeia, é uma cadeia (palavra).
O seu valor de saída dá o estado do autômato depois de ler a cadeia toda.
Por exemplo: δ(q0, a) = q1 , δ(q1, b) = q2 então δ*(q0, ab) = q2.
Note que para cada símbolo lido é gerado um novo estado. Quando se lê
o último símbolo da palavra “1”, o autômato chega ao seu estado final.
Portanto o autômato reconhece a palavra e portanto pertence à
linguagem especificada
Linguagens Formais e Autômatos – Profº André Mendes Garcia Página.: 8
Definição
- δ*(q, ε) = q
- δ*(q, ab) = δ*( δ(q, a), b)
De acordo com o nosso primeiro exemplo:
δ*(q0, ε) = q0
δ*(q0, 1) = δ( δ*(q0, ε), 1) = δ(q0, 1) = q0
δ*(q0, 11) = δ( δ*(q0, 1), 1) = δ(q0, 1) = q0
δ*(q0, 110) = δ( δ*(q0, 11), 0) = δ(q0,0) = q2
δ*(q0, 1100) = δ( δ*(q0, 110), 0) = δ(q2, 0) = q2
δ*(q0, 11001) = δ( δ*(q0, 1100), 1) = δ(q2, 1) = q1
δ*(q0, 110011) = δ( δ*(q0, 11001), 1) = δ(q1, 1) = q1
δ*(q0, 1100111) = δ( δ*(q0, 110011), 1) = δ(q1, 1) = q1
LINGUAGEM ACEITA POR UM ( AFD )
A linguagem aceita por um AFD M=(Q, ∑, δ, q0, F) é o conjunto de todas as cadeias em ∑
aceitas por M.
L(M) = {w ∈ ∑* | δ*(q0, w) ∈ F}
LINGUAGUAGENS REGULARES
Uma linguagem diz-se regular se e somente se, existir um AFD M que a aceite.
L = L(M)
A família das linguagens regulares é composta por todas as linguagens que são aceitas
por um qualquer AFD.
Uma forma de demonstrar que uma linguagem é regular é encontrar um AFD que a aceite.