Automatos

LICENCIATURA EM ENGENHARIA INFORMTICA

Antnio Dourado Pereira Correia

Advertncia. Este documento um texto de trabalho para apoio ao estudo da cadeira de Teoria da Computao.

No inclui toda a matria leccionada na disciplina e naturalmente no dispensa a consulta da bibliografia

complementar. O autor agradece qualquer comentrio ou sugesto que o tolerante e paciente leitor entenda por

bem fazer.

Departamento de Engenharia Informtica

Faculdade de Cincias e Tecnologia

Universidade de Coimbra

Setembro 2009

TEORIA DA COMPUTAO

ndice Geral

Captulo 1. Introduo e definies bsicas 1

Captulo 2. Autmatos finitos 43

Captulo 3. Expresses regulares, linguagens regulares e gramticas regulares 115

Captulo 4. Propriedades das linguagens regulares 153

Captulo 5. Linguagens livres de contexto 179

Captulo 6. Simplificao de gramticas e formas normais 213

Captulo 7. Autmatos de Pilha 245

Captulo 8. Propriedades das linguagens livres de contexto 273

Captulo 9. Mquinas de Touring 299

Teoria da Computao Captulo 1 Introduo e Definies Bsicas

LEI/DEI/FCTUC/2009/@ADC Documento de trabalho 1

CAPTULO 1

INTRODUO E DEFINIES BSICAS 1.1. Introduo 3

1.2. Linguagens formais 3 1.2.1. Alfabetos, cadeias e operaes sobre cadeias 5

1.2.2 .Operaes de conjuntos sobre linguagens 10

1.3 Gramticas 17

1.4 Autmatos 30

1.5. Os trs paradigmas da computao 37

Bibliografia 42

Anexo 42



1.1. Introduo

As cincias da computao, numa interpretao genrica, tm a ver com todos os aspectos

relacionados com os computadores e o seu funcionamento. H no entanto trs temas centrais

que so delas estruturantes: autmatos, computabilidade, complexidade. As trs visam dar

resposta questo primeira - quais so as capacidades e as limitaes fundamentais dos

computadores? O que se pode computar? Estas que tm ocupado intensamente os cientistas da

computao desde os anos 30 do sculo passado, quando a noo e o significado de

computao surgiu no panorama cientfico.

Nesta disciplina iremos abordar aqueles trs temas. Comearemos pelos autmatos e

veremos depois os elementos introdutrios fundamentais da computabilidade e da

complexidade.

A teoria dos autmatos compe o edifcio formal que sustenta solidamente todo o

desenvolvimento de processadores de texto, de compiladores e de hardware. Suporta tambm

(atravs das gramticas associadas aos autmatos) todo o desenvolvimento das linguagens de

programao. Assim linguagens, gramticas e autmatos so, com veremos, as trs faces de

um mesmo prisma. Vejamos formalmente em que consistem.

1.2.Linguagens formais

Tal como as linguagens humanas, as linguagens formais (assim chamadas por serem definidas

por um conjunto de formalismos matemticos abstractos) so faladas por autmatos, isto ,

um autmato compreende, e sabe interpretar uma dada linguagem, de uma forma que veremos

posteriormente. alis interessante constatar que os estudiosos das linguagens humanas (os

linguistas) deram uma contribuio muito importante para o desenvolvimento da teoria das

linguagens formais. Por exemplo Chomsky, de que falaremos no Captulo 6, um linguista.

Uma linguagem exprime-se atravs de smbolos de uma certa forma (tal como as

linguagens humanas ao longo da histria usaram smbolos diversos, desde os hieroglficos at

aos caracteres latinos, passando pelos chineses, pelos gregos e pelos rabes). Poderemos

definir formalmente esta realidade.



1.2.1 Alfabeto, cadeias e operaes sobre cadeias

Um alfabeto composto por um conjunto no vazio de smbolos, usualmente representada

pela letra grega (sigma), de smbolo.

={smbolos}, conjunto no vazio de smbolos (letras, algarismos,...)

Os smbolos de um alfabeto podem ser de qualquer natureza e assumir um aspecto

arbitrrio. Qualquer alfabeto um conjunto, e esta a nica caracterstica comum. A prpria

palavra alfabeto composta pela concatenao do primeiro e segundo smbolos grego, o alfa e

o beta.

Exemplos de alfabetos:

= {a,b}, alfabeto composto pelas duas letras a e b.

= {0,1}, alfabeto binrio composto pelos valores binrios 0 e 1.

= {(,),[,] } , alfabeto dos parnteses

= {0,1,2,3,4,5,6,7,8, 9 }, alfabeto dos algarismos rabes

={a,b,c, ..., z}, o alfabeto romano minsculo

={conjunto de todos as caracteres ASCII}, o alfabeto ASCII.

= {copos, facas, garfos, pratos, colheres, tachos}, o alfabeto dos instrumentos de cozinha

= {ma, pra, ameixa, banana, }, o alfabeto dos frutos.

Qualquer objecto pode pertencer a um alfabeto. Por isso um alfabeto pode ser um

conjunto de qualquer espcie de coisas.

Por razes de simplicidade usam-se normalmente apenas letras, algarismos e outros

caracteres comuns como #, $, &, etc.



Juntando-se vrios caracteres de um alfabeto obtm-se uma cadeia (string, em ingls),

w, formalmente definida como uma sequncias finitas de smbolos do alfabeto.

Exemplo 1.2.1

w= a, w=ab, w=abbaba, cadeias no alfabeto = {a,b}

Exemplo 1.2.2

w =1,w=2, w=23, w=5674, cadeias de algarismos rabes.

Por vezes uma cadeia tambm se chama palavra. De facto nas linguagens humanas as

palavras so cadeias de caracteres seguindo uma certa regra de formao a ortografia.

Alguns autores de lngua inglesa (por exemplo Linz) usam o termo phrase frase) como sinnimo de cadeia. De facto uma cadeia gerada aplicando as regras (produes) de uma gramtica,

tal como uma frase de uma linguagem humana se constri usando as regras da respectiva gramtica.

Nesse sentido as palavras so os elementos atmicos da linguagem humana que correspondem aos

smbolos de um alfabeto de uma linguagem formal. Para evitar confuses usaremos preferencialmente

o termo cadeia.

Fazendo a concatenao de duas cadeias w e v obtm-se uma terceira cadeia que por

isso se chama a concatenao de w e v.

Pode-se obter fazendo a concatenao direita (v direita de w), por exemplo sendo

w= a1a2a3 ....an v= b1b2b3bn

a concatenao direita de v com w , wv, ser

wv=a1a2a3anb1b2b3bn

e a concatenao esquerda, vw

vw=b1b2b3bna1a2a3an

Os caracteres numa cadeia seguem uma certa ordem. Por vezes estamos interessados em

alterar essa ordem, obtendo-se cadeias derivadas da original. Por exemplo a cadeia reversa,

obtm-se invertendo (da direita para a esquerda) a ordenao dos caracteres. A reversa da

cadeia w acima ser, revertendo w,



wR =an...a3a2a1

O nmero de caracteres de uma cadeia pode ser qualquer, sendo por isso umas longas

e outras curtas. Chama-se comprimento de uma cadeia, anotando-se pelo mdulo, |w|, o

nmero de posies, ou de casas, ocupadas pelos caracteres na cadeia. Por exemplo 011011

tem comprimento 6. Por vezes tambm se define comprimento como o nmero de caracteres

da cadeia, o que est certo se se inclurem as repeties nesse nmero. De outro modo a

cadeia anterior tem 2 caracteres (0 e 1) que, repetidos, ocupam 6 posies.

Se uma cadeia no tem qualquer carcter (note-se que o singular de caracteres

carcter, e no carater), ter 0 caracteres, sendo por isso vazia (um conjunto vazio), e denota-

se por (alguns autores denotam por ) . O seu comprimento ser nulo, ||=0, e pode escolher-se de qualquer alfabeto.

Se concatenarmos uma cadeia vazia com outra cadeia w qualquer, obtm-se

w = w = w, w,

para todo e qualquer w, tal como a unio de um conjunto com o conjunto vazio d o

conjunto original, qualquer que ele seja.

Certas cadeias tm formas especiais. Por exemplo abcdedcba ou abcdeedcba podem

ler-se igualmente da frente para trs ou de trs para a frente. Elas tm um ponto de simetria.

Em linguagem corrente chamam-se capicuas e mais formalmente chamam-se palndromos e

so tais que w = wR. Voltaremos a falar deles.

Subcadeia de uma cadeia w qualquer cadeia composta por caracteres sucessivos de

w . Se dividirmos qualquer cadeia w em duas partes u e v, tal que w=uv, diz-se que u um

prefixo e v um sufixo de w.

Se por exemplo

w=abbab

Poderemos definir os seguintes prefixos de w:

{, a, ab, abb, abba, abbab}

e os seguintes sufixos de w:



{abbab, bbab, bab, ab, b, }

Note-se que cada prefixo est associado a um sufixo. O prefixo a est associado ao sufixo

bbab e o sufixo ao prefixo abbab. A ordem por que esto escritos acima reflecte essa associao.

Potncia n de uma cadeia, wn, uma cadeia obtida pela concatenao n vezes da

cadeia w consigo prpria. Assim por exemplo

w2 = ww

w3 = www,

etc.

fcil de ver que

w1=w

Quanto a w0, ela ser a concatenao de w consigo prpria zero vezes. Se a

concatenao uma vez d a prpria cadeia, a concatenao zero vezes d nada, ou seja, a

cadeia vazia e portanto

w0={}

para todo e qualquer w.

O sinal de potncia tambm se usa para exprimir a concatenao de um carcter

consigo prprio. Por exemplo

a3=aaa,

1204=110000,

anbm=aaabbb.

Tambm se define potncia de um alfabeto, n, como o conjunto das cadeias desse alfabeto de comprimento n. Assim se ={0,1},

0={}, cadeia vazia



1={0,1} , cadeias com um carcter

2={00,01,10,11}, cadeias com dois caracteres

3={000, 001, 0010, , 111} cadeias com trs caracteres

etc.

(note-se que enquanto um conjunto de caracteres (smbolos), 1 um conjunto de cadeias, mesmo que tenham apenas um carcter).

Se definirmos o conjunto de todas as potncias possveis de um alfabeto, esse conjunto

ter todas as cadeias com zero, um, dois, , qualquer nmero de caracteres do alfabeto. Para

exprimir este facto usa-se o smbolo estrela, *, para significar qualquer, e chama-se a * o fecho estrela do alfabeto (star-closure). Assim * conjunto de todas as cadeias que se podem obter pela concatenao de zero ou mais smbolos de . Contm sempre a cadeia nula . simplesmente o conjunto de todas as cadeias possveis no alfabeto , e uma forma simples e elegante de denotar esse conjunto infinito.

Se excluirmos a cadeia vazia do fecho estrela, obtemos o fecho estrela positivo, +

+ =*-{}

fcil de ver, pela definio, que quer * quer + so sempre conjuntos infinitos, mesmo quando o alfabeto finito.

Chegamos agora finalmente definio de linguagem, um dos conceitos chave da

computao:

Definio 1.2.1. Linguagem : dado um alfabeto qualquer , linguagem L qualquer subconjunto de *.

Assim sendo, num alfabeto qualquer podem-se definir mltiplas linguagens. Elas tero

propriedades diferentes que lhes do caractersticas bem distintas, que estudaremos na ocasio

oportuna. Uma linguagem num alfabeto no precisa de ter todos os caracteres desse alfabeto,

pode ter apenas uma parte deles.

Define-se frase (ou sentena) como qualquer cadeia na linguagem formal L



A lngua portuguesa um conjunto de cadeias formadas pelas letras do nosso alfabeto

latino. Na linguagem corrente cada cadeia uma palavra e uma frase pode ter vrias palavras.

Na linguagem Java, um programa qualquer correctamente escrito um subconjunto de

todas as cadeias possveis que se podem formar com os caracteres da linguagem. O seu

alfabeto um subconjunto dos caracteres ASCII.

Seja por exemplo o alfabeto ={a,b}.

Nele *={,a,b,aa,ab,ba,bb,aaa,aab,aba,abb,baa,bab,bba,bbb, ...}, contm todas as combinaes possveis dos smbolos do alfabeto, incluindo a cadeia vazia.

(i) O conjunto L1={a, ab, abb} uma linguagem em . uma linguagem finita.

(ii) O conjunto L2={anbn: n0} uma linguagem em . uma linguagem infinita.

As cadeias ab, aabb, aaabb, pertencem a L2 porque se podem escrever na forma

respectivamente a1b1, a2b2, a3b3. Como veremos a gramtica da linguagem define as regras da

formao das cadeias.

J as cadeias aba, abb, aaababbab, no pertencem a L2 (tente escrev-las naquela

forma de potncias ).

Por vezes define-se uma linguagem exprimindo verbalmente as suas propriedades

especficas que a distinguem de outra qualquer. Por exemplo:

- o conjunto de cadeias em ={0,1} com um nmero de 0s igual ao nmero de 1s

L={, 01, 10, 0011, 1100, 0110, 0101, 1001, }

- o conjunto dos nmeros binrios cujo correspondente decimal primo

L={10,11,101,111,1011, 1101, 10001, }

Tambm se pode constatar que , a linguagem vazia, no tem qualquer cadeia, uma linguagem em qualquer alfabeto.

Tambm {}, a linguagem composta apenas pela carcter vazio, uma linguagem em qualquer alfabeto.



Note-se a diferena entre e {} : a primeira no tem qualquer cadeia e a segunda tem uma cadeia (a cadeia vazia de facto uma cadeia, mesmo que vazia).

1.2.2. Operaes de conjuntos sobre linguagens e suas propriedades

Uma linguagem , como vimos, um conjunto. Portanto aplicam-se-lhe todas as

operaes sobre conjuntos. Se tivermos duas linguagens L1 e L2, poderemos fazer com elas as

seguintes operaes:

Unio: todas as cadeias que pertencem ou a uma ou a outra,

L1L2 = {w: wL1 ou wL2},

Interseco: todas as cadeias que pertencem simultaneamente a uma e a outra,

L1L2 = {w: wL1 e wL2},

Diferena de duas linguagens: todas as cadeias que pertencem a uma e no pertencem

outra,

L1 - L2 = {w: wL1 e wL2},

L2 L1 = {w: wL1 e wL2}.

Complemento de uma linguagem: todas as cadeias possveis no alfabeto respectivo

(isto , *) menos as cadeias da linguagem complementada,

Compl(L) =L =* - L.

Reverso de uma linguagem: todas as cadeias que resultam da reverso das cadeias

originais de L constituem a linguagem reversa de L denotada por LR

LR = {wR : wL}.

Concatenao de duas linguagens: todas as cadeias em que uma parte (prefixo)

pertence primeira linguagem e a parte restante (sufixo), segunda

L1L2={uv: uL1, vL2},.



Dada a concatenao de L1 e L2 ser que L1 L1L2, para quaisquer L1 e L2 em quaisquer alfabetos 1 e 2 ?

Tal ser possvel se e s se L2. Vejamos as vrias situaes possveis.

(i) No caso em que os dois alfabetos so disjuntos, se no pertence a L2, ento a concatenao de uma qualquer cadeia de L1 com uma qualquer cadeia de L2 resulta numa

cadeia que no pertence a L1 e por isso nenhuma cadeia de L1 neste caso pertence

concatenao.

(ii) no caso particular em que as duas linguagens partilham o mesmo alfabeto, ao

concatenarmos a menor cadeia de L1 com a menor cadeia de L2, obtm-se uma cadeia maior

do que a primeira, e portanto no possvel obter em L1L2 a menor cadeia de L1. Pelo menos

essa no pertence a L1L2 e por isso o mesmo sucede a L1 (esta s pertence concatenao se

todas as suas cadeias pertencerem). No caso extremo em que L1=L2, verifica-se a mesma

situao.

Mutatis mutandis da anterior L2 L1L2 se e s se L1

Distributividade da concatenao em ordem unio

Considerem-se, a ttulo de exemplo, as linguagens

L1={a, ab, b},

L2={0, 01}

L3={11, 111, 1111}

Ento

L2L3={0,01,11,111,1111} e

L1 . (L2L3) ={a, ab, b}.{0,01,11,111,1111}=

={a0,a01, a11,a111,a1111,ab0,ab01,ab11,ab111,ab1111,b0,b01, b11,b111,b1111}

={( a0,a01, ab0,ab01, b0, b01), (a11,a111,a1111, ab11,ab111,ab1111, b11,b111,b1111)}



= {a,ab,b}.{0,01} {a,ab,b}{11, 111, 1111}=.{L1L2 L1L3 Este resultado pode-se generalizar: a concatenao distributiva em relao unio.

L1 . (L2L3)= L1L2 L1L3.

De facto se uma cadeia pertence unio de duas linguagens, ela ir entrar na

concatenao. Por outro lado, se uma cadeia no pertence unio, ela no entrar na

concatenao. Sero concatenadas todas as da unio e apenas elas.

Ser a unio distributiva em relao concatenao?

Uma propriedade definida assim genericamente tem que ser vlida para todos e

quaisquer casos. Se formos capazes de encontrar um s caso em que isso se no verifique, a

propriedade no geral e portanto a resposta no.

Considerem-se novamente as trs linguagens acima.

Faa-se

L2L3={0, 01}.{11, 111, 1111}={011,0111,01111,0111,01111,011111}

L1 (L2L3)={a, ab, b}{011,0111,01111,0111,01111,011111}=

={a, ab, b, 011,0111,01111,0111,01111,011111}

Por outro lado,

( L1L2) = L1={a, ab, b}{0, 01}= {a, ab, b, 0, 01}

(L1L3 ) = {a, ab, b} {11, 111, 1111}= {a, ab, b, 11, 111, 1111}

Concatenando estas duas,

( L1L2). (L1L3 ) = {a, ab, b, 0, 01}.{a, ab, b, 11, 111, 1111}

={aa, aab, ab, a11,a111,a1111, ...}

Ora as cadeias aa, aab, no pertencem a L1 (L2L3).

Logo



L1 (L2L3) ( L1L2) (L1L3 )

e conclumos que em geral a unio no distributiva sobre a concatenao.

A concatenao de uma linguagem com o conjunto vazio (linguagem vazia) resulta no

conjunto vazio (analogamente ao produto de um nmero real por zero).

L =

A concatenao de uma linguagem L qualquer com a cadeia vazia resulta na linguagem L

(analogamente ao produto de um nmero real pela unidade).

L = L

Na concatenao o conjunto vazio desempenha o papel de zero e a cadeia vazia o papel da

unidade.

Potncia de uma linguagem

Define-se a potncia n de uma linguagem a partir da concatenao da linguagem

com ela prpria (auto-concatenao) n vezes.

Se concatenarmos uma linguagem zero vezes com ela prpria , vem L0 .

Em que resulta ?

Para um qualquer nmero real, elevando-o a zero obtm-se a unidade. Ento aqui ser

natural considerar-se que a potncia zero de uma linguagem a unidade da concatenao, ou

seja, a cadeia vazia. Podemos tambm considerar que a potncia nula de uma linguagem consiste

em escolher zero cadeias dessa linguagem. Logo,

L0={}

L1=L

L2=LL

...



Chama-se fecho-estrela (star-closure, Kleene star) de uma linguagem L* ao conjunto

de todas as cadeias que se podem obter por concatenao da linguagem com ela prpria, um

nmero arbitrrio de vezes (incluindo zero vezes), ou seja,

L* = L0L1L2L3......

Se tivermos, por exemplo, a linguagem L={0,1}, o seu fecho estrela o conjunto de

todas as cadeias de 0s e 1s, incluindo a cadeia vazia. De facto

L0={} - todas as cadeias com zero caracteres

L1 ={0,1} - todas as cadeias de 0s e 1s com um carcter

L2 ={0, 1}.{0, 1}={00,01,10,11} - todas as cadeias de 0s e1s com dois caracteres

L3={0, 1}.{0, 1}.{0,1}={00,01,10,11}.{0,1}={000,001,010,011,110,111}

- todas as cadeias de 0s e 1s com trs caracteres

L4={0, 1}.{0, 1}.{0,1}.{0,1} - todas as cadeias de 0s e 1s com quatro caracteres,

E assim sucessivamente. Unindo agora todos os subconjuntos teremos o conjunto de

todas as cadeias de 0s e 1s com zero, um, dois, trs, , qualquer nmero de caracteres, ou

seja, todas as cadeias possveis de 0s e 1s. Assim o fecho estrela desta linguagem com duas

cadeias uma linguagem infinita. Note-se que L* contm sempre , independentemente de L o conter ou no.

Se considerarmos a linguagem L={0, 11}, o que dar o seu fecho estrela ?

L0={} - pelas razes anteriores

L1 ={0,11}

L2 ={0, 11}.{0, 11}={00,011,110,1111}

L3={0, 11}.{0, 11}.{0,11}={00,011,110,1111}.{0,11}=

={000,0011,0110,01111,1100,11011,11110,111111}



E assim sucessivamente. Obtm-se todas as cadeias de 0s e 1s em que os 1s

aparecem sempre aos pares. Por exemplo a cadeia 00110110, mas no 0010110 nem 0011010.

Como se poder obter 00110110 a partir de ? De L6 possvel: 0011 pertence a L3, e 0110 pertence tambm a L3.

Ainda neste exemplo o fecho estrela da linguagem finita com apenas duas cadeias

resulta numa linguagem infinita.

H algumas linguagens que tm a concatenao aparentemente estranhas.

Se considerarmos L a linguagem que contm todas as cadeias de 0s (incluindo zero

0), ento L*=L. Tal como se for a linguagem conjunto de todas as cadeias de 1s . L infinita,

tal como o seu fecho estrela.

E o fecho estrela da linguagem vazia, * ?

0={}

1=

2=

Unindo tudo vem

*={} ={}

Quanto linguagem com o carcter vazio, L={}, o seu fecho estrela L*={}.

A linguagem e a linguagem {} so as duas nicas linguagens que tm um fecho estrela finito.

Fecho-positivo (positive closure) de uma linguagem, L+ , o conjunto de todas as

cadeias que se podem obter por concatenao da linguagem com ela prpria uma ou mais

vezes. Se L no tem , + tambm no,

L+ : L1L2L3...... = L* - {}

Exemplo: Seja



L={anbn, n1}

Logo:

L={ab, aabb, aaabbb, aaaabbbb, ....}

L2= LL={ab, aabb, aaabbb, aaaabbbb, ...

abab, abaabb, abaaabbb, abaaaabbbb, ...

aabbab, aabbaabb, aabbaaabbb, aabbaaaabbbb, ...

........... }

Procurando uma forma compacta para L2, pode-se escrever

L2= {anbnambm, n1, m1}, n e m so independentes.

A reversa de L fcil de calcular: basta revertermos a expresso que a define:

LR={bnan, n1}

Se tivermos necessidade de escrever o complemento de L de uma forma sinttica,

como faz-lo? Trata-se de todas as cadeias que no obedeam regra de formao de L. Por

exemplo aab, baa, ababab, bababa, aaaa, aaaa, bbaab, bbbbaa, . Ser fcil encontrar uma

expresso compacta, em notao de conjuntos, que inclua todas as cadeias do complemento

de L ? Fica o desafio ao leitor.

E o fecho estrela L* ?

Nem sempre a notao de conjuntos a mais adequada para representar linguagens.

Por isso foram desenvolvidas representaes alternativas: as expresses regulares e as

gramticas. Estud-las-emos em captulos posteriores. Mas vejamos desde j algumas noes

bsicas de gramticas.



1.3. Gramticas

A gramtica de uma linguagem formal tem o mesmo objectivo da de uma linguagem humana:

ela fixa, de modo que todos possamos entender, as regras de formao das palavras e das

frases. Todas as linguagens escritas tm uma gramtica. a gramtica que d sentido

linguagem: sem ela as pessoas no se entenderiam

Uma gramtica tambm uma ferramenta para estudar matematicamente linguagens,

muito poderosa, que ultrapassa as limitaes da notao de conjuntos anterior.

Vejamos um exemplo da lngua portuguesa

Exemplo 1.3.1

H vrias gramticas da lngua portuguesa, normalmente identificadas pelo nome dos seus

autores. Se usarmos a de Mateus e outros (Gramtica da Lngua Portuguesa, Mateus, M,H.M,

A. M.Brito, I. Duarte, I. H Faria, Caminho Srie Lingustica, 1989), poderemos representar

simbolicamente as regras de formao de uma frase (aqui feita para fins ilustrativos, e

portanto muito simplificadas em relao riqueza da nossa lngua):

Regra: uma frase composta por um sintagma nominal e um sintagma verbal.

Pode no ter sintagma nominal ou o sintagma verbal; mas tem que ter pelo menos um

deles.

Simbolicamente escreve-se a regra de produo

frase sintagma nominal sintagma verbal (produo 1)

O sintagma nominal composto por um determinante e um nome (pelo menos um

deles) ou pode ser vazio:

sintagma nominal determinante nome | vazio (produes 2 e 3)

O determinante pode ter um artigo ou um dectico, ou nada:

determinante artigo | decticos | vazio (produes 4,5,6)



O sintagma verbal composto por um verbo e um sintagma nominal (pelo menos um

deles):

sintagma verbal verbo sintagma nominal (produo 7)

Para podermos formar (produzir) frases temos que ter palavras concretas e no apenas

categorias de palavras. Elas, as palavras concretas, so os elementos terminais da gramtica.

Por exemplo:

verbo estuda | ama | compra | dorme|chove (produes 8 a 12)

artigo o | a |um | uma| (produes 13 a 17)

decticos este | esse | aquele | meu | teu | seu | (produes 18 a 24)

nome Lus | Antnia | Isabel | livro | gelado | (produes 25 a 29)

Com as regras de produo e os elementos terminais dados, poderemos agora formar

frases.

Por exemplo para produzir a frase

a Antnia compra aquele gelado

usam-se as regras de produo na ordem adequada para o fim em vista:

frase sintagma nominal sintagma verbal produo 1

determinante nome sintagma verbal produo 2

determinante nome verbo sintagma nominal produo 7

determinante nome verbo determinante nome produo 2

determinante nome verbo dectico nome produo 5

a nome verbo dectico nome produo 13

a Antnia verbo dectico nome produo 26



a Antnia compra dectico nome produo 10

a Antnia compra aquele nome produo 20

a Antnia compra aquele gelado produo 29

Verifique o leitor se as seguintes frases obedecem gramtica dada:

(i) O Joo foi ao cinema

(ii) Chove

(iii) A Isabel ama o Lus

Este exemplo mostra como uma frase (ou orao), conceito geral e complexo, pode ser

definida custa de elementos simples (decomposio da complexidade). Comea-se no

conceito mais complexo (frase), e reduz-se sucessivamente at se obterem os elementos

irredutveis com que se constri a lngua.

A generalizao deste princpio leva-nos s gramticas formais isto , gramticas das

linguagens formais, as linguagens dos computadores.

As linguagens formais so construes matemticas (conjuntos) que obedecem a

certas regras. Para que no haja equvocos, as gramticas formais devem ter uma estrutura

clara, coerente, completa. Por isso usam-se notao e conceitos matemticos precisos para a

sua definio e manipulao.

Definio 1.3.1. Gramtica.

Uma gramtica G definida por um quarteto

G=(V, T, S, P)

em que

V : variveis, conjunto no vazio finito de objectos,

T: smbolos terminais, conjunto no vazio finito de objectos,



S V: varivel de inicializao, um smbolo especial, tambm chamado axioma,

P : um conjunto finito de produes

As variveis no podem ser smbolos terminais e vice-versa, isto V e T so conjuntos

disjuntos. No nosso estudo so em geral caracteres.

As regras de produo constituem o cerne da gramtica, pois atravs delas que uma

cadeia de caracteres se transforma noutra cadeia de caracteres. Por isso elas definem uma

linguagem associada gramtica.

Gramticas diferentes podem produzir a mesma linguagem. Nesse caso so gramticas

equivalentes. Mais frente estudaremos tcnicas e algoritmos para transformar uma gramtica

numa outra sua equivalente.

Embora uma linguagem possa ser produzida por vrias gramticas, uma gramtica

produz uma e uma s linguagem. Teremos a relao ilustrada na figura 1.3.1.

Figura 1.3.1 . Vrias gramticas podem produzir a mesma linguagem. Mas uma gramtica no

pode produzir duas linguagens.

As regras de produo de uma qualquer gramtica tm sempre a forma padro

x y

que se l (a cadeia) x produz (a cadeia) y .

A cadeia produtora x tem que ter qualquer coisa, no pode ser a cadeia vazia (se assim

no fosse produzir-se-ia a partir do nada, o que no teria significado). Este facto anota-se por

Linguagens Gramticas

G4

G1 G2

G3

L1

L2



x (V T)+

querendo-se dizer que a cadeia x pode ter variveis da gramtica e/ou smbolos terminais,

sem a cadeia vazia (por isso se escreve + e no *).

A cadeia produzida y, chamada o corpo da produo, pode conter variveis da

gramtica, e/ou smbolos terminais, podendo ser a cadeia vazia. Neste caso quer dizer que a

produo consiste simplesmente na anulao de x. Anota-se assim por

y (V T)*

sendo agora legtimo escrever ( * ) para admitir a possibilidade da cadeia vazia. De facto (V T)0 resulta na cadeia vazia.

A produo substitui, numa forma sentencial, a cadeia x pela cadeia y. Isto ,

dada uma cadeia w = uxv

e a regra de produo x y,

____________

por substituio de x por y em w, obtm-se a cadeia z = uyv

Diz-se que w produz z , ou que z produzida por w e anota-se com seta larga

w z

w e z podem variveis e/ou smbolos terminsais, dependendo do caso, como veremos.

As regras de produo podem aplicar-se por qualquer ordem e tantas vezes quantas as

necessrias. Este facto permite que com um nmero finito de produes se possa obter uma

linguagem infinita. Duas produes e um smbolo inicial so suficientes para produzir uma

linguagem infinita. Por exemplo as duas produes seguintes

S aS

S



geram qualquer cadeia no alfabeto ={a}, incluindo a cadeia vazia. Experimente o leitor gerar a cadeia aaa.

Ser possvel obter, com uma s produo, uma linguagem infinita? S em certas

gramticas especiais que estudaremos no Captulo 12.

Entre uma forma sentencial inicial w1 e uma final wn poderemos passar por um

grande nmero de formas sentencias intermdias, w1, w2, , ou seja,

w1 w2 wn

Diz-se que w1 produz wn ou, em escrita mais compacta (mais prtica), usando (*)

para significar uma sequncia de produes simples,

w1 wn

(* ) exprime o facto de que para derivar wn a partir de w1 so necessrios um nmero no

especificado de passos (incluindo eventualmente zero passos, como em w1 w1 ).

As regras de produo podem ser aplicadas numa ordem qualquer. Por cada ordem,

produz-se uma cadeia terminal. Ordens de derivao diferentes podem dar cadeias terminais

iguais ou diferentes, conforme a gramtica concreta.

O conjunto de todas as cadeias terminais que se podem obter por uma gramtica,

compem a linguagem gerada por essa gramtica. Exprime-se pela expresso L(G),

linguagem L da gramtica G. Em termos mais formais, dada a gramtica definida pelo

quarteto

G=(V, T, S, P)

a linguagem da gramtica (ou gerada pela gramtica) composta por todas as cadeias

terminais (sentenas, apenas com smbolos de T, ou eventualmente ) que se podem gerar a partir de S com as produes de P, por qualquer ordem qualquer nmero de vezes, ou seja,

L(G) = {wT*: S w}

Se uma dada cadeia pertence linguagem, w L(G), ento a sequncia



S w 1 w2 ... wn w

uma derivao da cadeia w. A cadeia w deve ter apenas smbolos terminais caracteres do

alfabeto da linguagem, incluindo eventualmente .

Qualquer derivao da gramtica comea sempre por S, que por isso tambm

chamado o axioma da gramtica. Desde S at w passa-se por diversas expresses que tm

variveis da gramtica ou uma mistura de variveis e de smbolos terminais. A essas

expresses chama-se formas sentenciais da derivao: so as cadeias S, w1, w2, ..., wn .

Exemplo 1.3.2.

Seja a gramtica definida pelo quarteto

G =({S}, {a,b}, S, P)

Comparando com a definio 1, identificam-se os elementos do quarteto:

Conjunto V das variveis: S

Smbolos terminais: a,b , as cadeias terminais tero apenas estes smbolos

Varivel de inicializao: S

As produes P dadas por

P1: S aSb : partindo do smbolo inicial S, coloca-se-lhe um a antes e um b depois.

P2: S : o smbolo S pode ser substitudo pela cadeia vazia (isto , por nada).

Uma derivao pode seguir o seguinte percurso:

S aSb aplicando a produo P1

aaSbb produo P1

aaaSbbb produo P1



...

pode-se continuar um nmero qualquer de vezes, at ao infinito. Vo-se obtendo sucessivas

formas sentenciais.

Em qualquer altura se pode aplicar a produo P2, substituindo S por , ou seja por nada. Nessa altura obtm-se uma frase da linguagem. Assim,

ao fim da 1 produo obtm-se ab

ao fim da 2 produo obtm-se aabb

etc.,

ao fim da nsima produo obtmse aaa....abbb...b = anbn

Se aplicarmos primeiro a produo P2 obtm-se a cadeia vazia e no se pode

prosseguir.

Conclui-se assim que esta gramtica produz a linguagem composta por cadeias em que

a primeira metade s tem as e a segunda metade s tem bs, ou seja, de uma forma

matematicamente elegante, usando as noes que vimos anteriormente,

L(G) = {anbn, n0}

Este resultado to evidente que se pode dizer que no carece de demonstrao. Mas

pode-se demonstrar formalmente, usando uma das tcnicas de prova conhecidas. Como se

trata de demonstrar uma frmula para um nmero infinito de casos, o mais natural ser usar a

prova por induo, associada noo de recursividade.

O caso , correspondente a n =0 tem que ser tratado parte. Demonstra-se que ele se obtm aplicando a produo P2 a partir de S.

Para os outros casos faamos a demonstrao por recursividade da produo P1 e

induo.

Queremos provar que qualquer que seja n 1, todas as formas sentenciais so da forma

wn = anSbn



- base da induo, n=1, verdade ?

sim, resultante de uma vez P1 a partir de S.

-hiptese indutiva: admitamos que verdade para n=k e para todos os anteriores, ou seja,

verdade que

wk = akSbk

-passo indutivo: em consequncia verdade para k+1 ou seja

wk+1 = ak+1Sbk+1

Prova do passo indutivo (nesta prova h-de entrar a hiptese indutiva):

Partindo de wk e por aplicao de P1 obtm-se wk+1

wk+1awkb

mas substituindo a hiptese indutiva nesta produo,

wk+1a(akSbk )b

Manipulando a expresso

wk+1 (aak)S(bkb)

ou ainda por definio de concatenao (potncia) de caracteres,

wk+1 ak+1 Sbk+1

Falta finalmente provar que aplicando P2 a qualquer forma sentencial na forma wn = anSbn,

n1, se obtm uma sentena na forma anbn.

anSbn anbn

o que verdade.

E a demonstrao est feita, quod erat demonstrandum (o que era preciso demonstrar)

q.e.d.



Exemplo 1.3.3:

Encontrar uma gramtica que gere a linguagem

L={an+1bn, n0}

Esta linguagem parecida com a do exemplo anterior, com a diferena de que

necessrio gerar um a adicional esquerda de b. Pode-se simplesmente ger-lo em primeiro

lugar, aplicar depois regras de produo como no caso anterior:

P1: S aS

P2: S aSb

P3: S

Teramos assim a gramtica definida exactamente como a anterior:

G = ({S}, {a,b}, S, P)

Como as produes de podem aplicar por ordem arbitrria e um nmero arbitrrio de

veses, aplicando P1, P1, P2, P3, obtm-se

S aS aaS aaaSb aaab

i.e. a3b, que no faz parte da linguagem.

Para que isto no acontea, P1 s se pode aplicar uma vez. Introduz-se com esse

objectivo uma varivel adicional, A, e definem-se as produes

P1: S aA

P2: A aAb

P3: A

em que S a varivel de inicializao. Note-se que partindo de S no se pode voltar a ele, e

por isso P1 s se aplica uma vez, sendo sempre a primeira. Poderemos agora definir a

gramtica G com o quarteto



G=({A}, {a,b}, S, P)

sendo P composto pelas trs produes P1, P2 e P3.

Para demonstrar que uma dada linguagem gerada por uma certa gramtica, tem que

se mostrar que:

(i) por um lado toda a cadeia w L pode ser derivada a partir de S usando as produes P da gramtica ou seja

(ii) por outro lado qualquer cadeia gerada pela gramtica G pertence linguagem L.

Nem sempre fcil fazer as duas demonstraes, sobretudo a primeira. Ver por

exemplo em Linz, exemplo 1.13. Recorre-se frequentemente prova por induo.

Uma linguagem pode ser gerada por muitas gramticas, que por isso se dizem

equivalentes ,

G1 e G2 so gramticas equivalentes se L(G1)=L(G2)

Na Fig. 1.1 as gramticas G2, G3 e G4 so equivalentes.

Os palndromos so cadeias que tm interesse especial para o estudo de gramticas e

autmatos. Vejamos mais em detalhe como se podem definir e gerar.

Definio formal de palndromos ( PAL) sobre um alfabeto

Seja PAL a linguagem constituda por todos os palndromos (capicuas) sobre um dado

alfabeto. Pode-se definir pelas trs regras seguintes

1. O carcter vazio simtrico, logo pertence aos palndromos.

PAL

2. Qualquer carcter isolado simtrico, logo um palndromo

Para todo o a, a PAL,

3. Se tivermos uma cadeia simtrica e lhe adicionarmos o mesmo carcter no princpio e no

fim, resulta uma cadeia simtrica,.



Para toda a cadeia w PAL , e todo o a, awa PAL

Uma cadeia s pertence a PAL se puder ser gerada por estas 3 regras. Por outro lado se

uma cadeia um palndromo, ento ela pode ser gerada por aquelas trs regras, aplicando-as

as vezes necessrias pela ordem conveniente.

Exemplo 1.3.4

Seja o alfabeto = { a, b }

Aplicando aquelas 3 regras,

1. PAL

2. a PAL, b PAL

3. Para qualquer wPAL, awa PAL

bwb PAL

Qualquer cadeia pertence a PAL se e s se for gerada pelas regras 1, 2 e 3.

Por exemplo:

b PAL , regra 2

aba PAL, regra 3

babab PAL regra 3

abababa PAL regra 3

Como se poder escrever uma gramtica para esta linguagem?

Poderemos tentar imitar as trs regras: primeiro gera-se um palndromo com a regra 1 ou a 2,e

depois geram-se sucessivos palndromo, cada vez maiores, com a regra 3.

Deste modo uma gramtica para esta linguagem pode ser obtida pelas derivaes seguintes:

1 P1: S (regra 1)



2 P2: S a (regra 2)

P3: S b (regra 2)

3 P4: S aSa (regra 3)

P5: S bSb (regra 3)

Por exemplo para gerar abba teremos a sequncia de produes

S aSa abSba abba abba

Pode-se escrever as 5 produes gramtica na forma compacta, usando | para o ou lgico

S | a | b |

S aSa | bSb

1.4.Autmatos

Os autmatos finitos so modelos abstractos de muitos dispositivos de hardware e de

software. Aplicam-se nomeadamente em (Hopcroft& col)

1- software para o projecto e o teste de circuitos digitais.

2- Analisadores lexicais dos compiladores (que verificam se uma palavra, por

exemplo um identificador, est bem escrita num programa).

3- Software para busca de texto em ficheiros, na web, etc.

4- Software de verificao de sistemas que tm um nmero finito de estados

distintos, tais como protocolos de comunicao, protocolos de segurana, etc.

Muitos componentes e sistemas digitais podem estar num entre um nmero finito de

estados, e por isso a noo de estado central num autmato a eles associado. O estado

permite lembrar o passado relevante do sistema (ele chegou l aps um certo nmero de

transies, que so o seu passado). Se o nmero de estados de um sistema finito, poderemos

represent-lo com uma quantidade limitada de recursos.



Considere-se por exemplo um interruptor on-off. Se est off e se se pressiona, passa a

on. Se est on e se se pressiona, passa a off . Ele ter por isso dois estados, o on (A) e o off (F)

Desenhando, teremos os dois estados como dois vrtices de um grafo, Fig.1.3.1.

Figura 1.4.1. Os dois estados do autmato que representa o interruptor on-off. F-fechado, A-

aberto.

Representando por arestas de um grafo as aces de pressionar ( Press) teremos a Fig. 1.4.2

Figura 1.4.2. As transies entre os estados do autmato, provocadas pelo accionamento do

interruptor.

Para se saber como se inicializou o interruptor, identifica-se o estado inicial por uma seta,

Figura 1.4.3. O autmato finito do interruptor.

e tem-se finalmente o desenho de um autmato finito (de dois estados) que representa o

funcionamento do interruptor, na Fig. 1.4.3.

F A

F A

Press

Press

F A

Press

Press



As etiquetas das arestas representam a aco exterior sobre o sistema (neste caso

pressionar o interruptor) e as arestas a evoluo do sistema em consequncia dessa aco, que

sempre uma transio entre dois estados (ou, como veremos, e generalizando a noo de

transio, de um estado para ele prprio).

Considere-se agora o autmato da figura 1.4.4.

Figura 1.4.4. Um autmato finito que transita de estado pela entrada de letras.

Inicializa-se no estado 1, recebe do exterior (l) a letra p e passa ao esto 2, depois com as

letras a e i passa sucessivamente aos estados trs e 4.

Poderamos nomear os estados de um modo mais sugestivo, tal que a sua etiqueta nos

sintetizasse o que se passou at a. Teramos por exemplo a Fig. 1.4.5.

Figura 1.4.5. O autmato anterior da Fig 1.4.4 com nova etiquetagem dos estados.mais

sugestiva.

Pode afirmar-se que o autmato de 4 estados capaz de reconhecer a palavra pai: se

chegou ao estado 4, ela pareceu-lhe, caso contrrio nunca chega ao estado 4. Por esta razo

diz-se que o autmato um aceitador da palavra pai. Para assinalar este facto o estado 4

desenha-se com uma dupla circunferncia, como na figura 1.4.6.

Figura 1.4.6. O autmato com estado final aceitador

E chama-se estado final, ou estado aceitador, conforme os autores. O primeiro

chama-se estado inicial.

1 2 3 4p a i

p pa pai p a i

p pa pai p a i



Vejamos um exemplo um pouco mais complexo.

Exemplo 1.4.3

Uma porta automtica de entrada de um servio pblico, rotativa, tem geralmente dois

sensores, um frontal, e um na retaguarda, conforme esquematizado na Fig. 1.4.7.. O frontal

detecta uma pessoa que se aproxima e o da retaguarda detecta a presena de uma pessoa na

sua rea de observao.

Figura 1.4.7. Uma porta de abertura automtica, rotativa.

Quanto uma pessoa se aproxima para entrar a porta abre-se, girando sobre o seu eixo

de fixao, se no estivar ningum detrs da porta, caso contrrio haveria um acidente. H um

dispositivo electrnico, o controlador, que recebe os sinais dos dois sensores e conforme o

caso manda abrir, fechar, ou manter-se como est. O controlador ter dois estados,

correspondentes a porta aberta, A, e porta fechada, F. Tal como no exemplo anterior,

poderemos desenhar dois vrtices de um grfico para esses dois estados.

Figura 1.4.8. Os dois estado do autmato abridor da porta.

Os dois sensores enviam, cada um, informao de presena ou ausncia de pessoas,

que poderemos representar por 0 (ausncia) e 1 (presena).Teremos quatro situaes

possveis, considerando simultaneamente os dois sensores:

00 : ausncia de frente e detrs

Sensor Fronta

Sensor Rectag

F A



01: ausncia de frente e presena detrs

10: presena de frente e ausncia detrs

11: presena de frente e presena detrs.

Em cada uma destas quatro situaes possveis o controlador tem que tomar uma

deciso: fecha, abre ou deixa ficar como est ?

Poderemos constatar que o alfabeto do autmato (o conjunto de informao externa

que ele sabe ler) composto por aquelas quatro situaes, que poderemos associar a 4

caracteres de um alfabeto, conforme a tabela

Tabela 1.4.1. Codificao do alfabeto ao autmato. PF- presena frontal, PR presena na

rectaguarda.

PF PR Carcter

0 0 00 a

0 1 01 b

1 0 10 c

1 1 11 d

Considerando as restries de segurana, teremos as transies possveis representadas na

tabela (de transies) seguinte:

Tabela 1.4.2. Transies entre os estados em funo dos caracteres de entrada lidos.

A A A F A

F A F F F

d 11

c 10

b 01

a 00

EntradaEstado



Agora fcil desenhar o grafo do autmato, com os dois ns correspondentes aos

estados e as arestas correspondentes 8 transies da tabela. Obtm-se a figura seguinte.

Figura 1.4.9. O autmato finito que representa o sistema de controlo de abertura da porta .

Como que o controlador fecha e abre a porta? Enviando um sinal a um actuador

mecnico. Poderemos assim considerar que o autmato tem uma sada que pode ter dois

valores: 1 para abrir, 0 para fechar. Poderemos introduzir essa informao colocando sob a

letra do estado o valor lgico correspondente da sada, como na figura seguinte

Figura 1.4.10. O autmato anterior com a representao da sada. Veremos no Cap. 2 que este

autmato se chama por isso de Mquina de Moore.

Depois deste dois exemplos muito simples, estamos em condies de definir um

autmato mais detalhadamente.

Um autmato genrico tem os seguintes componentes:

- um ficheiro de entrada, composto por uma cadeia num alfabeto

- um mecanismo para leitura do ficheiro de entrada de modo que

l a cadeia de entrada da esquerda para a direita, um carcter de cada vez,

detecta o fim da cadeia

A F

b,d,a

c

a

b,c,d

A/1 F/0

b,d,a

c

a

b,c,d



- uma sada, onde a unidade de controlo pode escrever

- um dispositivo de memria temporria

composto por um nmero ilimitado de clulas, cada uma capaz de armazenar

um smbolo de um alfabeto (que pode ser diferente do alfabeto de entrada). O

autmato pode ler e alterar o contedo dos registos de memria.

- uma unidade de controlo que

pode estar num de entre um certo nmero finito de estados internos,

pode mudar de estado segundo alguma regra.

Juntando tudo teremos a Fig. 1.4.11.

Figura 1.4.11. Representao genrica de um autmato finito.

O que lhe d a caracterstica de finito to s o nmero de estados da unidade de

controlo: ele finito.

Esta figura muito geral. Um autmato concreto pode no ter memria (como os

exemplos que vimos), ou pode no ter sada (como o aceitador de pai). Mas todos tm a

unidade de controlo e a entrada.

O autmato funciona em tempo discreto, sequencialmente. Num dado instante k est

num certo estado interno, k, e o mecanismo de entrada est a ler um smbolo sk no ficheiro de

Unidade de Controlo

qk

Ficheiro de entrada Mem r i a

S k

m k

y kFicheiro de sada



entrada. No prximo instante de tempo, o estado interno do autmato vai ser determinado

pelo estado actual, pelo smbolo lido entrada e pelo contedo da memria, mk. Essa

dependncia definida pela funo de transio de estado f, que depende por isso do estado

actual, da entrada actual e do contedo actual da memria, ou seja,

qk+1 = f(qk, sk, mk)

Entre dois instantes do tempo sucessivos pode produzir-se uma sada ou pode alterar-

se o contedo da memria.

Chama-se configurao do autmato ao conjunto composto por

- o estado interno da unidade de controlo,

- o ficheiro de entrada e

- o contedo da memria.

Chama-se um passo transio do autmato de uma configurao para a configurao

seguinte.

Todos ao autmatos que estudaremos se enquadram nesta descrio genrica. Os

diversos tipos que estudaremos distinguem-se por

i) a forma de produzir a sada , sendo

aceitadores se reconhecem ou no a cadeia de entrada; no tm sada informam pelo

estado final em que terminam a leitura da entrada

transdutores se produzem cadeias de caracteres na sada com alguma utilidade

ii) a natureza da memria temporria (o factor mais importante)sendo

autmatos finitos se no sem tm memria temporrio ou

autmatos de pilha se tm uma memria em pilha LIFO (em ingls pushdown

automata, de empurrar (a pilha) para baixo ),

mquinas de Turing se tm a memria em fita, de dimenso infinita, que pode

ser lida e alterada em qualquer ordem



iii) a natureza da funo de transio, dizendo-se

determinsticos se dada uma configurao, existe um e um s comportamento

futuro possvel ou

no determinsticos se dada uma configurao, o prximo passo pode ter vrias

alternativas.

1.5. Os trs paradigmas da computao

Quando falamos em computao, o que queremos dizer exactamente ?

Em primeiro lugar computao poder ser o clculo do valor numrico de uma

funo, como por exemplo da funo f(n), que calcula o n-sino nmero primo,

( )f n n simo nmero primo

trata-se de uma funo unria, ou da funo g, produto de dois nmeros,

( , )g n m n m

funo binria, de dois argumentos m e n ou ainda da funo h, soma de n nmeros,

1 2 ... nh a a a

funo n-ria (de n argumentos).

Este tipo de computao mais antigo do que os computadores digitais, alis to

antigo quanto a civilizao humana, dado que desde muito cedo o homem precisou de fazer

clculos matemticos (para calcular o calendrio, por exemplo).

Na era do computador digital h outros tipos de computao. Por exemplo, poderemos

ter uma cadeia de 0s e 1s e calcular a sua paridade, ou o nmero de zeros. Ou ento

queremos saber se uma cadeia um palndromo, ou se a palavra public est bem escrita

num programa de computador em Java.



Este tipo de computao parece nada ter ver, partida, com a computao do valor de

funes. Trata-se do reconhecimento, ou classificao, de cadeias de smbolos. Como as

cadeias de smbolos formam linguagens, este tipo de computao chama-se por isso

reconhecimento de linguagens, o segundo paradigma da computao.

O problema de reconhecimento de linguagens domina a teoria da computao.

Falaremos dele repetidamente at ao final da disciplina e ele ocupa a maior parte dos livros de

teoria da computao.

Porque assim to importante?

Em primeiro lugar porque muito representativo: pode-se reduzir qualquer problema

de deciso a um problema de reconhecimento de linguagens.

Em segundo lugar porque o problema do clculo do valor de uma funo pode tambm

ser reduzido a um problema de reconhecimento de uma linguagem.

Comecemos pela verificao da primeira razo.

Considere-se o problema de deciso seguinte

- o nmero natural n primo ?

Trata-se de um problema de deciso: decidir se ou no, mas decidir de modo

fundamentado.

Construa-se no alfabeto ={1} a linguagem composta por cadeias de 1s que tm um comprimento igual a um nmero primo:

L ={1n, n primo},

em que como sabemos 1n = 1111 , n vezes

Isto

L={11, 111, 11111, 1111111, }

Agora temos o problema de reconhecimento de linguagens

- a cadeia 1n pertence linguagem L ?



equivalente ao problema de deciso acima enunciado.

Alm do clculo do valor de uma funo ou do reconhecimento de uma linguagem

temos outro tipo de computao: o da transduo de cadeias, ou seja, a transformao de

uma cadeia de smbolos por exemplo revertendo-a, deslocando-a para a esquerda ou para a

direita, contando o nmero de as, etc. Temos aqui o terceiro paradigma da computao.

De entre os trs paradigmas da computao, qual o mais importante?

De facto nenhum mais importante do que o outro. Verifica-se at o princpio da

inter-redutibilidade (Fig.1.5.1): qualquer instncia de um dos trs paradigmas de pode reduzir

a uma instncia de qualquer um dos outros dois.

Figura 1.5.1. Inter-redutibilidade entre os trs paradigmas da computao.

Vejamos como.

i) Qualquer caso de computao de uma funo pode ser reduzido a uma instncia do

reconhecimento de uma linguagem.

Exemplo 1.5.1. Seja a funo

f(n) = m , m o n-simo nmero primo

Tabela 1.5.1. Funo n-simo nmero primo

Reconhecimento de Linguagens

Transduo de cadeias

Clculo de funes f(n)



n 1 2 3 4 5 6

f(n) 2 3 5 7 11 13

Suponhamos que queremos calcular

f(5) = ??

Para reduzir este clculo a um problema de reconhecimento de linguagens faa-se a

construo engenhosa seguinte (inspirado em Taylor):

1 Usando a representao binria de nmeros naturais, constroem-se as cadeias que

resultam da concatenao de 101, isto 5 em binrio, com os nmeros naturais (1, 2, 3, 4, 5,

6, ), usando por exemplo # como separador:

2 Define-se agora a linguagem L associada aos nmeros primos

L ={Binrio(n)#Binrio(m)}

(no esquecer que m o n-sio nmero primo).

A computao do valor de f(5) equivalente determinao de qual a nica cadeia

daquele conjunto que pertence a L . De facto h-de l estar, naquele conjunto de cadeias,

101#1011

Assim, procurando-a, ficamos a saber que

f(5)=11

ii) Reduo de uma classificao de cadeias a uma computao numrica de uma funo

101#1 101#10 101#11 101#100 101#101 101#110 101#111



Tomemos o caso do reconhecimento de palndromos.

Em primeiro lugar faz-se uma codificao dos smbolos do alfabeto, de modo que cada

smbolo fique associado a um e um s nmero natural em binrio.

Por exemplo, em ={a,b}, se a = 01 e b = 10, ento o palndromo aba resulta no nmero natural 011001=2510.

Em segundo lugar constri-se a linguagem dos palndromos, L(Pal),.

L(Pal)= {a,b,aa,bb,aaa, aba,bab, bbb,

e os seus cdigos,

Cdigos= {01,10,0101,1010,010101, 011001,100110,101010, }

A funo caracterstica de L ser

1,se o cdigo de um palndromo( )

0, se no o n

nn

Agora para se saber se 25 o cdigo de um palndromo, basta calcular o valor da

funo caracterstica (25) que 1, e assim se conclui que aba um palndromo.

Claro que para cada caso necessrio desenvolver o engenho para encontrar a forma

de implementar o princpio da inter-redutibilidade. O que importa saber que sempre

possvel encontrar uma soluo.

Mas este princpio muito importante: ele permite que se use o problema da

identificao de linguagens em teoria da computao como representativo dos trs

paradigmas. Por isso o que usaremos ao longo da cadeira.



Bibliografia

An Introduction to Formal Languages and Automata, Peter Linz, 3rd Ed., Jones and Bartelett

Computer Science, 2001

Models of Computation and Formal Languages, R. Gregory Taylor, Oxford University Press,

1998.

Introduction to Automata Theory, Languages and Computation, 2nd Ed., John Hopcroft,

Rajeev Motwani, Jeffrey Ullman, Addison Wesley, 2001.

Elements for the Theory of Computation, Harry Lewis and Christos Papadimitriou, 2nd Ed.,

Prentice Hall, 1998.

Introduction to the Theory of Computation, Michael Sipser, PWS Publishing Co, 1997.

Anexo 1. Tabela de nmeros primos

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139

149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281

283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443

449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613

617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787

797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971

977 983 991 997 1009 1013 1019 1021 1031 1033 1039 1049 1051 1061 1063 1069 1087 1091 1093 1097 1103

1109 1117 1123 1129 1151 1153 1163 1171 1181 1187 1193 1201 1213 1217 1223 1229 1231 1237 1249 1259

1277 1279 1283 1289 1291 1297 1301 1303 1307 1319 1321 1327 1361 1367 1373 1381 1399 1409 1423 1427

1429 1433 1439 1447 1451 1453 1459 1471 1481 1483 1487 1489 1493 1499 1511 1523 1531 1543 1549 1553

1559 1567 1571 1579 1583 1597 1601 1607 1609 1613 1619 1621 1627 1637 1657 1663 1667 1669 1693 1697

1699 1709 1721 1723 1733 1741 1747 1753 1759 1777 1783 1787 1789 1801 1811 1823 1831 1847 1861 1867

1871 1873 1877 1879 1889 1901 1907 1913 1931 1933 1949 1951 1973 1979 1987 1993 1997 1999 2003 2011

2017 2027 2029 2039 2053 2063 2069 2081 2083 2087 2089 2099 2111 2113 2129 2131 2137 2141 2143 2153

2161 2179 2203 2207 2213 2221 2237 2239 2243 2251 2267 2269 2273 2281 2287 2293 2297 2309 2311 2333

2339 2341 2347 2351 2357 2371 2377 2381 2383 2389 2393 2399 2411 2417 2423 2437 2441 2447 2459 2467

2473 2477 2503 2521 2531 2539 2543 2549 2551 2557 2579 2591 2593 2609 2617 2621 2633 2647 2657 2659

2663 2671 2677 2683 2687 2689 2693 2699 2707 2711 2713 2719 2729 2731 2741 2749 2753 2767 2777 2789

2791 2797 2801 2803 2819 2833 2837 2843 2851 2857 2861 2879 2887 2897 2903 2909 .

Teoria da Computao Captulo 2 . Autmatos Finitos


CAPTULO 2

AUTMATOS FINITOS

2.1. Introduo 45

2.2.Aceitadores determinsticos 46

2.3. A arte de construir DFAs 59

2.4. Linguagens regulares 75

2.5. Autmatos finitos no-determinsticos (DFAs) 83

2.6 Equivalncia entre DFAs e NFAs 85

2.7. Reduo do nmero de estados em Autmatos Finitos 97

2.8 Aplicao dos DFAs na busca de texto 105

2.9 Autmatos transdutores 107

Mquinas de Mealy 108

Mquinas de More 109

Bibliogafia 112

Apndice: Software de autmatos finitos 112

JFLAP

Deus ex-mquina



2.1. Introduo

No Cap.1 estudmos as noes bsicas de linguagens, gramticas e autmatos. Podem-se

definir muitas linguagens a partir de um mesmo alfabeto, conforma as regras particulares de

combinao dos caracteres do alfabeto.

Por exemplo a partir do alfabeto = {a, b} e usando a notao de conjuntos poderemos definir as linguagens L1 = { anbm | n,m >= 0 }a que pertencem as cadeias : ,aabbbbb, aaaa, bbbb, ou a linguagem L2 = { anbn | n >= 0 } a que pertencem as cadeias: ,ab,aabb, aaabbb, aaaabbbb, ou ainda L3 = {a,b}* composta por qualquer cadeia de as e bs ,incluindo

.. Quantas linguagens se podem definir com este alfabeto ?

As linguagens podem ser definidas por uma gramtica, que indica como se formam as

cadeias de caracteres. Conhecidas as suas produes fcil derivar cadeias da linguagem.

Pode-se agora pr o problema ao contrrio: dada uma cadeia de caracteres, como saber se

pertence a uma dada linguagem ? Se a cadeia for pequena pode ser relativamente simples, por

inspeco visual, decidir se pertence ou no. Mas para uma cadeia grande de um gramtica

mais elaborada, no fcil decidir.

aqui que entram os autmatos finitos. Vimos no Cap. 1 um autmato aceitador da

cadeia pai. Se fosse possvel construir um autmato que aceitasse todas as cadeias de uma

dada linguagem (e s essas), ento para se saber se uma cadeia pertence a uma linguagem

bastaria d-la a ler ao autmato. Se ele parasse no estado aceitador depois de concluir a sua

leitura, a cadeia pertenceria linguagem. Caso contrrio no pertenceria.

Infelizmente no possvel desenhar um autmato para uma qualquer linguagem. H

linguagens para as quais ainda hoje no possvel decidir se uma cadeia lhe pertence ou no.

Num mesmo alfabeto pode-se definir um nmero infinito de linguagens, cada uma delas

com caractersticas prprias. Felizmente para algumas classes de linguagens possvel

construir autmatos finitos aceitadores: o caso por exemplo das linguagens regulares, cujas

propriedades veremos mais frente. Por agora basta-nos saber que possvel construir um

autmato finito aceitador para uma linguagem regular.



Teremos assim a Figura 2.1.1.

Figura 2.1.1. Relao entre linguagens, gramticas e autmatos.

Existem outras classes de linguagens, que no regulares, para as quais possvel

tambm construir autmatos aceitadores, naturalmente distintos dos das linguagens regulares.

Vemos assim que h diferentes classes de linguagens e diferentes classes correspondentes de

autmatos.

Para as linguagens regulares, as mais simples, constroem-se autmatos finitos

determinsticos, os autmatos tambm mais simples. Quando um autmato usado para

reconhecer uma linguagem, mais exacto chamar-lhe aceitador. No entanto usaremos com

frequncia o termo autmato, distinguindo-se a sua funo de aceitador dentro do contexto em

que usado. Como veremos existem autmatos que no so aceitadores, isto , no so

construdos para aceitar ou no uma linguagem, mas antes para executarem sobre as cadeias

de caracteres uma dada operao (como alis j vimos no Cap. 1).

2.2. Aceitadores determinsticos

Um aceitador determinstico define-se como uma estrutura matemtica e desenha-se como um

grafo.

Exemplo 2.2.1.

Linguagens L

Gramticas G Geram as cadeias de L

Autmatos Reconhecem as cadeias

de L



Por exemplo o grafo seguinte representa um aceitador determinstico. O seu alfabeto

={0,1}.

Figura 2.2.1 Grafo de um aceitador determinstico.

Vejamos como funciona.

O autmato est no estado inicial, q0, e apresenta-se-lhe entrada uma cadeia de 0s e

1s, com por exemplo 1100.

Ele vai ler os caracteres da esquerda para a direita, isto 1 >1 > 0 >0. As arestas

representam as transies de estado quando o autmato l o carcter etiqueta da aresta.

Estando em q0 e lendo 1, transita para q1. Estando em q2 e lendo 1, transita para q2, isto , fica

onde est. Lendo agora 0, estando em q1, transita para q2. Lendo depois 0 transita para q3 e a

fica, porque no h mais nada para ler.

O estado q1 tem uma forma especial. Ele o estado aceitador. Se o autmato, partindo

do estado inicial, leu a cadeia 1100 e terminou no estado aceitador, ento aceita essa cadeia.

Poderemos ver outras que tambm aceita. Por exemplo 001, 0100, 1110001, etc. Se estiver

em q0 e aparece um 1, vai para o aceitador; se estiver em q1 e aparece um 1, mantm-se no

aceitador. Se estiver em q2 e aparece um 1, vai para o aceitador.

Ento conclui-se que qualquer cadeia que termine num 1 aceite pelo autmato: de facto

qualquer que seja o seu penltimo estado, o seu ltimo ser sempre o aceitador de ele ler

apenas mais um 1. Mas h cadeias de outro tipo, como por exemplo 0100, que tambm, so

aceites. Se depois do ltimo 1 aparecem dois zeros seguidos (e mais nada) ele termina

tambm no estado aceitador. Portanto o autmato aceita as cadeias que terminam num 1 ou

em 00 depois do ltimo 1.

q0 q1 q2

0

1

1 0

0

1

Incio



Note-se que em cada estado o aceitador determinstico sabe exactamente o que deve

fazer, porque tido lhe dito: de cada estado h duas arestas definindo as duas transies

possveis, uma para cada carcter do alfabeto. Essas duas transies podem ser iguais, com

acontece no estado q2. Pode-se simplificar o grafo colocando apenas uma aresta com duas

etiquetas, com o na figura seguinte.

Figura 2.2.2 Grafo do mesmo aceitador da Fig. 2.2.1

Se tivssemos uma alfabeto com trs caracteres (por exemplo {a,b,c}, ento de cada

estado teriam que partir sempre trs arestas explicitamente definidas (ainda que pudessem ser

iguais). Um aceitador determinstico no tem qualquer capacidade de decidir em qualquer

circunstncia, da o nome de determinstico. Consequentemente todas as transies possveis

tm que estar explicitamente definidas. A funo de transio por isso uma funo total, isto

, est explicitamente definida para todos os valores do seu domnio.

Note-se que esta definio que estamos a adoptar no seguida por todos os autores.

Alguns admitem que possam existir transies no definidas. Nestes, se aparecer entrada,

num dado estado, um carcter para o qual no esteja explicitamente definida uma transio, o

DFA morre, isto , passa a um estado no aceitador e no sai mais de l, quaisquer que sejam

os caracteres seguintes na cadeia lida (mais tarde chamaremos ratoeira a este estado).

Vimos que um autmato finito determinstico facilmente definido e descrito por um

grafo. Tem cinco partes: um conjunto de estados, um conjunto de regras para transitar entre

eles, um alfabeto de entrada que define os caracteres aceitveis entrada, um estado inicial,

um estado final. Veremos casos que tm vrios estados finais. Para definir formalmente o

autmato, usaremos todas essas cinco partes que compem um quinteto.

q0 q1 q2

0

1

1 0

0,1

Incio



Definio 2.2.1 Aceitador determinstico

Um aceitador determinstico (usaremos o acrnimo dfa-, de deterministic finite

accepter) definido pelo quinteto

M=(Q,, , q0, F )

em que : Q: o conjunto finito de estados internos

: alfabeto de entrada (conjunto finito de caracteres)

: Qx Q a funo total chamada funo de transio

q0 Q o estado inicial

F Q o conjunto de estados finais ou aceitadores

Uma funo total quando definida para todos os valores possveis dos seus

argumentos; caso contrrio diz-se parcial. Ao dizer-se que a funo de transio total,

atendendo sua definio, isso quer dizer que ela tem que estar definida para todas as

combinaes possveis de um estado e um carcter do alfabeto, isto , para todos os elementos

do produto cartesiano Qx.

Exemplo 2.2.2. O interruptor do Cap. 1

Retomemos aqui o exemplo do interruptor do Cap. 1. Se definirmos a linguagem das

sequncias de Press(P) tais que o interruptor fica ligado aps a sua aplicao (partindo do

estado inicial F), teremos P, PPP, PPPPP, etc., ou seja, um nmero mpar de accionamentos

do interruptor. Agora poderemos definir o autmato como um aceitador dessa linguagem,

colocando a dupla circunferncia no estado A.

Figura 2.2.3 Grafo do interruptor do Cap. 1.

Aplicando-lhe a definio 2.1 v-se que

F A

P

P



Q, conjunto de estados internos: {F, A}

, alfabeto de entrada: {P}

, funo de transio: F P A; A P F

q0 , o estado inicial: F

F, o estado final: {A}

Exemplo 2.2.3.

Seja o autmato da Fig. 2.2.4.

Figura 2.2.4. Autmato do exemplo 2.2.3

Aplicando-lhe de igual modo a definio 2.1 v-se que:

Q, conjunto de estados internos: {1,2,3,4}

, alfabeto de entrada: {a,b}

, funo de transio: 1 a 2; 1 b 4, 2 b 3, etc.

q0 , o estado inicial: 1

F, o estado final: {4}

Neste caso a funo de transio tem muitos elementos. Usando uma tabela especifica-se

mais facilmente.

Note-se que pelo facto de a funo de transio der total, a tabela tem que ter todas as clulas

preenchidas. Neste caso para cada estado existem duas arestas possveis, uma para a e outra

para b.

1 2 3

4

a

b

b

a

a

b

b a



Tabela 2.2.1. Tabela de transies do DFA da Fig. 2.2.3.

Se estado

actual

e a entrada

actual

o estado

seguinte ser

1 a 2

1 b 4

2 a 4

2 b 3

3 a 3

3 b 4

4 a 4

4 b 4

Qual ser a linguagem aceite por este autmato ?

O estado 4 tem uma caracterstica: se o autmato l chegar, nunca mais de l sai, e por

isso chama-se estado ratoeira, ou armadilha (trap) ou poo.

A figura seguinte reduz o esquema geral de um autmato que vimos no Cap. 1 ao caso

particular de um dfa.

Note-se que um dfa no tem nem dispositivo de memria nem cadeia de sada. Tem apenas

dispositivo de leitura e unidade de controlo. Conforme o contedo actual da clula lida, d-se

ou no uma transio de estado dentro da unidade de controlo.



Figura 2.2.5. O esquema de um DFA. Note-se a ausncia de qualquer dispositivo de

memria.

A transio de um estado para outro depende do estado actual (antes da transio) e do

carcter lido entrada no instante actual.

Figura 2.2.6. A funo de transio de um DFA.

Tabela 2.2.2

Um autmato representa-se por um

grafo em que os vrtices (ns)

representam os estados e as arestas

orientadas tm como etiquetas os

caracteres lidos na cadeia de entrada. H

trs tipos de vrtices, indicados na Tabela

2.2.2., ao lado

Smbolo Significado

Estado normal

Estado inicial

Estado aceitador (ou final)

Aresta

cadeia de entrada

a

a

b

b

a

b

q0

q1 q2

estado seguinte, movida,

smbolo na sada (caso a tenha)

carcter de entrada estado actual

[*] carcter

q0

qf

qi



Exemplo 2.2.4

Figura 2.2.7 DFA do exemplo 2.2.4.

Temos um autmato com trs estados, um de cada tipo. O alfabeto do autmato = {0,1}. Lendo com ateno as etiquetas das arestas pode-se escrever a seguinte tabela de

transies. O DFA pode-se assim definir formalmente como

M= (Q, S, , ,q0,F) com

Q = {q0,q1,q2}, = {0,1}, F = {q2} e definida pela Tabela 2.2.4.

Tabela 2.2.3. Funo de transio do exemplo 2.2.4.

Qual ser a linguagem aceite pelo autmato? Um bom desafio para o leitor ...

No Captulo 3 estudaremos as expresses regulares, uma tcnica de especificao de

linguagens que tem uma lgebra prpria muito adequada para deduzir a definio da

linguagem a partir de um DFA qualquer. Neste momento poderemos fazer o seguinte

procedimento heurstico:

-colocamo-nos no estado aceitador e vemos como l poderemos chegar,

incio

0

1

q2

0

0

1

q1 q0

1

Estados

Entradas

0 1

q0

q1

q2

q1 q0

q2

q0 q1

q0



-depois andamos para trs e em cada estado vemos o mesmo. At que se consiga

visualizar mentalmente a linguagem do autmato.

Chega-se ao estado final a partir de q1 com um 0, ou seja, com (****)0.

Chega-se a q1 com um 0 depois de 1: (***10)0. De modo que sempre que uma

cadeia termine em 100, termina no estado aceitador. Se terminar em 1000 no aceita a cadeia.

Mas aceita se terminar em 10000, 1000000, ou qualquer nmero par de zeros

precedido de 1.

Poderemos definir formalmente linguagem de um autmato finito.

Definio 2.2.2a. Linguagem de um DFA

Dado um DFA qualquer, M, a linguagem L aceite (ou reconhecida) por M o conjunto

de todas as cadeias que, comeando a ser lidas no estado inicial, fazem com que o autmato

alcance um dos estados finais depois de toda a cadeia ter sido lida. Escreve-se L(M) para

dizer que L a linguagem aceite ou reconhecida por M.

Que linguagens aceitam os seguintes autmatos ?

Exmplo 2.2.5

Fig. 2.2.8.

Exemplo 2.2.6

Fig. 2.2.9.

Exemplo 2.2.7

Incio q0 q1

0 0 1

1

Incio q0 q1

0 1

1

0



Fig. 2.2.10

Um DFA pode ser definido pela explicitao da funo de transio e, a partir dela,

facialmente se desenha o seu grafo.

Exemplo 2.2.8

Seja o DFA M = ({q0, q1, q2}, {a,b}, , q0, {q2}) cuja funo de transio a seguinte:

(q0, a) = q1 Tabela de transies (q0, b) = q2 (q1, a) = q0 (q1, b) = q2 (q2, a) = q2 (q2, b) = q2 Nas transies aparecem trs estados q1, q2 e q3. O grafo do autmato desenha-se graficando as transies, depois de se desenharem os seus trs estados. Obtm-

se assim a Fig. 2.2.11.

Fig. 2 .2.11

Ser possvel simplificar este DFA, isto , encontrar um outro com menos estados que

aceite a mesma linguagem (e s a mesma) ?

a

b q0

q1

q2 q1

q0

q2 q2

q2

q2

a

a

a,b

q0 q1

b b

q2 q2

q0 q1 q2 1 0

0 0,1 1



Veremos em captulos posteriores algoritmos para simplificar autmatos, reduzindo ao

mnimo possvel o nmero de estados. Neste momento poderemos apenas olhar com ateno

para o DFA e verificar o que ele faz. Se aparecer um b, no estado inicial, vai para o aceitador

q2. Se estiver em q1 e aparece um b, transita para q2 ; e se estiver em q2 e aparecer um b,

mantm-se a. Portanto qualquer que seja o seu estado se parecer um b na cadeia de entrada,

ele aceita-a: a sua linguagem portanto o conjunto de todas as cadeias em {a,b}* que

contenham pelo menos um b. O autmato seguinte aceita essa linguagem.

Fig. 2.2.12. Grafo equivalente ao

da Fig. 2.2.11.

Funo de transio estendida a cadeias de caracteres, *

Na definio do DFA a funo de transio definida de tal forma que ela activada por um

carcter. Se quisermos calcular a transio do DFA de uma configurao inicial para outra

configurao aps um conjunto de transies, seria interessante dispor de uma forma de

representao sucinta, compacta, que exprimisse essa transio salto resultante da leitura de

um conjunto de caracteres ou de uma cadeia completa.

Pode-se estender a noo de transio com esse objectivo. Em vez de escreve-se *, em que o asterisco quer dizer aps um certo nmero de transies.

A funo de transio estendida assim definida por

*: Q * Q

a

a,b

b

q2 q2

q0



em que

- o seu segundo argumento uma cadeia em vez de um carcter, e

- o seu valor de sada d o estado do autmato depois de ler a (sub)cadeia.

Por exemplo, se tivermos num autmato tal que

(q0, a) = q1 e (q1, b) = q2 ento *(q0, ab)=q2

Representando por grafos, teremos a Fig. 2.2.13.

Figura 2.2.13. Ilustrao da funo de transio estendida. Em a) grafo normal; em b) grafo

compactado usando uma transio estendida.

A funo de transio estendida pode definir-se recursivamente do modo seguinte:

(i) *(q,)= q

(ii) *(q,wa)= (* (q, w), a)

para todo o q Q, w*, a.

Para o exemplo anterior teremos :

* (q0, ab)= (* (q0, a), b)

*(q0, a)=* (q0, a)= (*(q0, ), a)= (q0, a)=q1

*(q0, ab)= ( q1, b)=q2

q0 q1 q2 a b

a) Funo de transio

q0 q2 ab

* b) Funo de transio estendida



Definio 2.2.2b.Linguagens de um DFA (definio formal)

A linguagem L aceite (ou reconhecida) por um DFA M =(Q, , , q0, F) o conjunto de todas as cadeias em aceites por M, i.e.,

L(M) = {w* : *(q0, w)F }

A funo de transio e * so funes totais (definidas para todos os elementos do seu domnio). Em cada passo define-se um e um s movimento, e por isso o autmato se

chama determinstico, no podendo fazer escolhas. Um autmato processa todas as cadeias

em *, aceitando-as ou no.

Quando no aceita uma cadeia, pra num estado no aceitador. O conjunto das cadeias

em que isso se verifica constitui o complemento da linguagem L(M), que se pode definir

formalmente por

Complem(L(M)) = {w* : *(q0, w)F }

Consideremos os autmatos da Fig. 2.2 14, diferentes apenas na identificao do estado

final.

O primeiro reconhece, como vimos, a linguagem das cadeias em {a,b}* que tenham pelo

menos um b. O segundo aceita, no mesmo alfabeto, as cadeias que tenham apenas as. Isto ,

a linguagem do segundo o complemento da linguagem do primeiro: se uma cadeia s tem

as no tem nenhum b, e se tem pelo menos um b no contm s as.

Figura. 2.2.14. Autmatos complementares no alfabeto {a,b}.

a

b

q0

a,b

q1

a,b

a

b

q0

q1



Repare-se que o estado no aceitador do primeiro autmato o estado aceitador do

segundo; e o estado aceitador do primeiro o estado no aceitador do segundo. De facto,:

- se uma cadeia aceite pelo primeiro no o pode ser pelo segundo: uma cadeia que

termine no estado aceitador do primeiro tem que terminar no estado no aceitador do

segundo;

- e se uma cadeia recusada pelo primeiro tem que ser aceite pelo segundo: se uma

cadeia termina no estado no aceitador do primeiro tem que terminar no estado aceitador do

segundo.

Para este autmato com dois estados, fcil de ver a relao entre os autmatos de

linguagens complementares.

Ser assim no geral ?

De facto . Se um autmato M aceita uma linguagem L(M), ento o complemento de L

ser reconhecida pelo autmato que se obtm de M invertendo neste a funo dos estados: os

no aceitadores passam a aceitadores e os aceitadores passam a no aceitadores.

2.3. A arte de construir DFAs

Os exemplos de autmatos que vimos at aqui parecem simples, e a sua construo (em grafo)

relativamente expedita.

Casos h em que bem mais difcil obter uma soluo simples (na medida do possvel) e

apropriada para uma dada funo.

A expertise para desenhar DFAs depende mais da arte aprendida e treinada do que de

uma teoria sofisticada.

Vejamos um exemplo:

Exemplo 2.2.9 Paridade individual

Desenhar um autmato que, no alfabeto ={0,1}, aceite todas as cadeias com um nmero mpar de 1s.



Podemos comear a desenhar estados e arestas, por tentativa e erro, at que consigamos,

com mais ou menos remendos, uma soluo. Se o conseguirmos, muito provavelmente

obteremos um

Documents

Automatos