Linguagens Formais e Autamatos

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.


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:


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)


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


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


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:


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


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.

Documents

Linguagens Formais e Autamatos