Teoria da ComputaoPablo Azevedo Sampaio Wilson Rubens Galindo Wilson Rosa de Oliveira Jnior

Volume 1

Recife, 2009

Universidade Federal Rural de Pernambuco Reitor: Prof. Valmar Corra de Andrade Vice-Reitor: Prof. Reginaldo Barros Pr-Reitor de Administrao: Prof. Francisco Fernando Ramos Carvalho Pr-Reitor de Extenso: Prof. Paulo Donizeti Siepierski Pr-Reitor de Pesquisa e Ps-Graduao: Prof. Fernando Jos Freire Pr-Reitor de Planejamento: Prof. Rinaldo Luiz Caraciolo Ferreira Pr-Reitora de Ensino de Graduao: Prof. Maria Jos de Sena Coordenao Geral de Ensino a Distncia: Prof Marizete Silva Santos Produo Grfica e Editorial Capa e Editorao: Allyson Vila Nova, Rafael Lira e Italo Amorim Reviso Ortogrfica: Marcelo Melo Ilustraes: Allyson Vila Nova Coordenao de Produo: Marizete Silva Santos

SumrioCaptulo 1 Introduo ...................................................................................4 1.1 Alfabetos, Cadeias e Linguagens ........................................................5 1.2 Operaes sobre cadeias..................................................................10 1.3 Operaes sobre linguagens.............................................................14 Captulo 2 Autmatos Finitos Determinsticos ........................................18 2.1 Explicao Inicial ...............................................................................18 2.2 Definio Formal ...............................................................................25 2.3 Criando AFDs ....................................................................................32 Captulo 3 Autmatos Finitos No-Determinsticos ................................42 3.1 Explicao Inicial ...............................................................................42 3.2 Definio Formal ...............................................................................45 3.3 Relao entre AFD e AFND...............................................................46 3.4 Um novo tipo de transio () ............................................................51 Consideraes Finais ....................................................................................60

Teoria da Computao

Captulo 1 IntroduoOl, cursista! Em disciplinas passadas, voc deve ter aprendido a criar programas para resolver problemas os mais variados. Nessa sua experincia com a programao, talvez voc j tenha tido a impresso de que possvel criar programas para qualquer problema matemtico que se possa imaginar. Ser que isso mesmo verdade? Ser que todo problema matemtico pode ser resolvido com algum programa de computador? Essa questo, que envolve tanto a Matemtica quanto a Computao, uma das principais questes tericas que abordaremos neste curso de Teoria da Computao. Para chegarmos a uma resposta para ela, ns vamos estudar modelos matemticos conhecidos como modelos computacionais. Veremos que, com cada modelo, somos capazes de criar diversos computadores tericos (ou programas tericos), onde cada computador resolve algum problema matemtico especfico. Veremos vrios modelos computacionais diferentes. Cada novo modelo apresentado ser, em geral, capaz de resolver mais problemas matemticos do que os modelos anteriores. Muitos dos modelos computacionais tm aplicao prtica em reas como: buscas em texto, validao de entradas, criao de linguagens de programao e criao de compiladores. No decorrer do curso falaremos um pouco de cada uma dessas aplicaes prticas, mas somente quando chegarmos ao ltimo modelo computacional (o modelo Mquina de Turing) que poderemos responder a questo terica levantada acima. Ou seja, somente com o modelo Mquina de Turing seremos capazes de chegar a concluses tericas sobre a real capacidade de resolver problemas dos computadores reais construdos pelo homem. Antes de comearmos a ver os modelos computacionais, precisamos introduzir alguns conceitos importantes que usaremos em todo o material. Esses conceitos bsicos sero apresentados no decorrer deste primeiro captulo, enquanto os modelos computacionais sero vistos somente a partir do segundo captulo.

4

Teoria da Computao

1.1 Alfabetos, Cadeias e LinguagensNeste incio do curso, ns vamos desviar um pouco do termo problema matemtico para falar no termo linguagem formal. Para a Teoria da Computao (e para a Matemtica) esses dois conceitos podem assumir significados parecidos. Poderamos, na verdade, usar apenas um deles neste curso de Teoria da Computao, deixando o outro de lado. Por isso, o que faremos ser dar destaque ao termo linguagem formal, deixando o termo problema matemtico um pouco mais de lado. primeira vista, pode no fazer muito sentido para voc como essas duas palavras podem significar a mesma coisa, mas no se assuste! Aqui, no estamos preocupados com o significado comum das palavras linguagem e problema, mas com o significado matemtico dado a elas dentro da Teoria da Computao! A definio matemtica de linguagem formal depende de outros conceitos matemticos importantes, que so: alfabeto, smbolos e cadeias. Apresentaremos a definio matemtica desses conceitos, comparando cada um deles com o conceito similar presente nos estudos da lngua humana escrita. Vamos comear relembrando o que sabemos sobre a escrita da lngua portuguesa... No incio das nossas vidas de estudantes, ns aprendemos as letras que formam o nosso alfabeto: A, B, C, D, ..., Z. Depois aprendemos a usar essas letras para formar as palavras e frases do nosso dia-adia. Esse conjunto de palavras e frases que usamos forma a nossa lngua: a Lngua Portuguesa. Outras lnguas do mundo se diferenciam da nossa por terem palavras e frases diferentes. Algumas dessas lnguas so escritas com o mesmo alfabeto que a nossa (como a lngua espanhola) e outras usam um alfabeto completamente distinto (como a japonesa). Do estudo das lnguas humanas, a Matemtica tomou emprestados os termos de alfabeto, cadeia e linguagem. A Matemtica deu sua prpria definio a cada um desses termos, criando conceitos mais gerais. Na viso matemtica, um alfabeto definido assim:Um alfabeto um conjunto qualquer que usamos para criar linguagens.

Vamos considerar, neste curso, que um alfabeto s no pode ser infinito nem vazio. Qualquer outro conjunto matemtico pode ser 5

Teoria da Computao

usado como alfabeto. Exemplos de alfabetos (na definio matemtica): A1 = { a, b, c, d } A2 = { 0, 1 } A3 = { x, +, (, *, ) } Nos trs exemplos acima, temos alfabetos formados por letras, nmeros e por outros sinais grficos diversos. Outros tipos de elementos tambm poderiam ter sido usados para formar outros alfabetos. Para dar um nome comum aos elementos de qualquer tipo presentes nos alfabetos, foi adotado o termo smbolos (ao invs do termo letras, usado para os elementos dos alfabetos das lnguas humanas). Bem, agora vamos falar do conceito matemtico que seria o mais prximo do conceito de palavra (e tambm do conceito de frase):Uma cadeia uma sequncia de smbolos de um alfabeto.

Diferente das palavras nas lnguas humanas, uma cadeia no precisa ter um significado associado. Basta ser formada por smbolos que aparecem em sequncia, podendo haver smbolos repetidos. Quando uma cadeia criada com os smbolos de um alfabeto X dizemos que ela uma cadeia sobre X. So exemplos de cadeias sobre A1: acaba, aba, abbccc, daacbbb. So exemplos de cadeias sobre A2: 0, 1000, 0011, 1101000. So exemplos de cadeias sobre A3: x*x, (x+x), **x*, )x**. Veremos agora um tipo especial de cadeia que no tem similar em linguagens humanas. (Se fosse possvel, este tipo de cadeia seria como uma palavra vazia, sem nenhuma letra). Essa cadeia a cadeia vazia:A cadeia vazia uma cadeia que no tem nenhum smbolo.

Este tipo de cadeia pode ser formado com qualquer alfabeto e ser uma cadeia bastante usada no restante do curso. Pelo fato de no ter smbolo nenhum, no temos como representar a cadeia vazia explicitamente. Por isso, usaremos a letra grega e (psilon) especialmente com essa finalidade. 6

Teoria da Computao

AtenoPara evitar confuso, o smbolo e no aparecer como smbolo de nenhum alfabeto neste material. Um e dever sempre ser entendido como a total ausncia de smbolos, ou seja, uma cadeia vazia. Assim, a cadeia 0 sobre o alfabeto A2 uma cadeia com um (nico) smbolo, mas e sobre o alfabeto A2 uma cadeia que no tem smbolo nenhum.

Agora que j definimos cadeias, podemos partir para o ltimo (e mais importante) conceito desta seo: o conceito matemtico de linguagem. Este conceito definido simplesmente assim:Uma linguagem formal (ou simplesmente linguagem) um conjunto de cadeias. uma

Esta definio tambm tem relao com as lnguas humanas, pois cada lngua humana tem um conjunto de palavras e de frases distinto. Portanto, podemos pensar que uma lngua humana o conjunto de palavras e frases que ela permite. Se trocarmos palavras e frases por cadeias, realmente, chegamos mesma definio apresentada acima. Cada linguagem formal formada de cadeias de um nico alfabeto. Se as cadeias forem formadas com um alfabeto X, dizemos que a linguagem uma linguagem sobre X. Alguns exemplos de linguagens finitas sobre o alfabeto A2: L1 = { 00, 01, 100, 11 } L2 = { 1, 000 } Uma linguagem vazia sobre A2: L3 = { } Veja que uma linguagem meramente um conjunto matemtico. Por isso, tudo que voc j conhece sobre conjuntos vale aqui. Por exemplo, assim como nos conjuntos, existem linguagens que so finitas, linguagens que so infinitas e linguagens que so vazias, dependendo da quantidade de cadeias que elas contm. Demos exemplos de linguagens finitas e vazias. Um problema surge quando desejamos representar uma linguagem infinita, porque impossvel listar todos os seus elementos. Por isso, muitas vezes definiremos uma linguagem infinita dando apenas uma descrio 7

Teoria da Computao

informal dela. Consideramos que uma descrio informal quando ela que no dada completamente em notao matemtica. Abaixo, damos um exemplo de uma descrio informal para uma linguagem infinita: Seja L4 a linguagem sobre A1 que contm todas as cadeias que comeam com o smbolo d (e no contm nenhuma cadeia alm dessas). Podemos dar uma descrio ainda mais simples da mesma linguagem assim: L4 a linguagem das cadeias sobre A1 que comeam com d. Se j tiver sido dito, antes, que o alfabeto A1 e, tambm, se o nome da linguagem no importar, a descrio pode ficar ainda mais simples: Cadeias que comeam com d. Veja que no conseguiramos listar todos os elementos da linguagem L4, porque as elas tm que ter d como primeiro smbolo, mas, depois dele, podem ter qualquer quantidade de smbolos. Isso torna as possibilidades infinitas, como voc pode perceber ao tentar listar as cadeias dessa linguagem: L4 = { da, db, daa, dbb, dba, dac, dcaa, dadaa, dacddbd, ... } Esperamos que tenha ficado claro pra voc, aluno, que uma linguagem meramente um conjunto. Por isso, tudo que voc j aprendeu antes sobre conjuntos pode ter aplicao no estudo formal de linguagens. Esperamos que, depois de ter lido esta seo, voc tenha compreendido bem estes trs conceitos: alfabeto, cadeia e linguagem. A seguir, na seo Aprenda Praticando daremos a voc a oportunidade de praticar esses conceitos.

Aprenda Praticando Este o momento de colocar em prtica os seus conhecimentos! Para isso, acompanhe atentamente a primeira questo, que j est respondida, e, depois, responda a segunda questo. 8

Teoria da Computao

1) Nas questes B = { a, b, 0, 1 }.

abaixo,

considere

que

o

alfabeto

a. Mostre quatro cadeias sobre o alfabeto. Resposta: Entre outras cadeias, podemos citar:

e, a, a0a, b101a.b. Crie duas linguagens finitas sobre o alfabeto. Resposta: Basta formar um conjunto com uma quantidade limitada (finita) de cadeias. Existe uma infinidade de linguagens assim, mas vamos indicar apenas duas aqui: { a, a0a, 1bb, 10 } { } c. Crie duas linguagens infinitas sobre o alfabeto. Resposta: Para criar linguagens infinitas, no ser possvel simplesmente listar as cadeias. O que ser preciso fazer pensar em uma propriedade que infinitas cadeias possuem. Ento, basta citar que a linguagem formada pelas cadeias com aquela propriedade. Tambm existe uma infinidade de linguagens assim, mas vamos mostrar duas: A linguagem que contm todas as cadeias que usam o smbolo 0. A linguagem das cadeias que comeam com a. Veja que a primeira linguagem contm cadeias como a0a, b110, 0ab e infinitas outras. J a segunda contm cadeias como a, a0, ab, a11b e infinitas outras. Agora a sua vez de responder a segunda questo. Ateno para o alfabeto que um pouco diferente do anterior. Isso muda as cadeias e, consequentemente, as linguagens que voc pode formar. 2) Nas questes C = { 1, 2, 3 }. abaixo, considere que o alfabeto

a. Mostre quatro cadeias sobre o alfabeto. b. Crie duas linguagens finitas sobre o alfabeto. c. Crie duas linguagens infinitas sobre o alfabeto.

9

Teoria da Computao

A partir de agora, veremos algumas operaes importantes que podem ser realizadas sobre cadeias e linguagens. (Operaes sobre alfabetos no so de grande utilidade, por isso no veremos).

1.2 Operaes sobre cadeiasEsta seo apresenta algumas operaes sobre cadeias que usaremos no decorrer do curso. Na definio das operaes, vamos usar duas cadeias genricas representadas assim: a1..an e b1..bm, onde os smbolos so representados genericamente por a (ou b) seguido de um nmero subscrito que representa a posio dele na cadeia. (Por exemplo, a3 representa o smbolo que aparece na terceira posio da cadeia a1..an). Nas explicaes que daremos abaixo, voc pode trocar essas duas cadeias por qualquer cadeia que desejar, inclusive pela cadeia vazia e. Para cada operao, mostraremos como chamamos a operao, depois como a representamos e, em seguida, explicamos detalhadamente o significado dela. Tamanho da cadeia a1..an : | a1..an | = n Esta operao d a quantidade total de smbolos de uma cadeia, contando inclusive com smbolos que aparecem mais de uma vez. Essa operao representada colocando a cadeia entre duas barras verticais |. Alguns exemplos: |a|=1 | aba | = 3 | 000 | = 3 |e|=0 Este ltimo exemplo mostra o tamanho da cadeia vazia e. Como dissemos na seo anterior, essa cadeia no tem smbolo nenhum. Por isso, o seu tamanho ser zero. Concateno da cadeia a1..an com a cadeia b1..bm: a1..an . b1..bm = a1..anb1..bm

10

Teoria da Computao

ou a1..an b1..bm = a1..anb1..bm Esta operao recebe duas cadeias e produz uma nova cadeia acrescentando, ao final da primeira cadeia, todos os smbolos da segunda cadeia. Esta operao pode ser representada colocando-se um sinal de ponto . entre as cadeias ou, simplesmente, colocando as cadeias lado a lado sem o uso de nenhum sinal. Vejamos alguns exemplos: 01 . 10 = 0110 a . bb = abb

e . 101 = 101abba . e = abba Os dois ltimos exemplos mostram uma propriedade interessante da concatenao: qualquer concatenao envolvendo a cadeia vazia e alguma outra cadeia d como resultado sempre essa outra cadeia. Autoconcatenao k vezes da cadeia a1..an (para um k 0): (a1..an)k = (a1..an) (a1..an) (a1..an) (repete k vezes)

Esta operao faz concatenaes entre k ocorrncias repetidas da cadeia, para um valor natural k constante. A operao representada colocando-se k como expoente na cadeia. O expoente k indica a quantidade de repeties da cadeia a serem consideradas.

AtenoAo longo do curso, usaremos parnteses, na maioria das vezes, com o propsito de agrupar. Nesses casos, ele poder ser ignorado. Os parnteses no podero ser ignorados apenas em casos particulares, que sero devidamente explicados. Isso acontecer quando os smbolos ) e ( fizerem parte do alfabeto que estivermos usando.

Alguns exemplos da autoconcatenao so dados abaixo: (101)1 = 101 (01)3 = 01.01.01 = 010101 a(b3) = a(b.b.b) = abbb 11

Teoria da Computao

(baa)0 = e

e2 = e.e = eOs dois ltimos exemplos mostram duas propriedades que merecem ser comentadas. A primeira delas est relacionada ao expoente zero: toda cadeia autoconcatenada zero vezes d ser sempre a cadeia vazia (independentemente de qual seja a primeira cadeia). J o ltimo exemplo ilustra a seguinte propriedade: a cadeia vazia autoconcatenada qualquer nmero k de vezes d sempre ela prpria (independente do valor do expoente k). Subcadeia a1..an subcadeia de b1..bm ou a1..an no subcadeia de b1..bm Esta uma operao especial que pode dar os resultados: verdadeiro ou falso. Ela d verdadeiro apenas se a cadeia a1..an igual a algum trecho contnuo da segunda cadeia b1..bm. Neste caso, podemos afirmar que a1..an subcadeia de b1..bm. Se no existir nenhum trecho contnuo de b1..bm que seja idntico cadeia a1..an, a operao d o resultado falso. Dizemos, ento, que a1..an no subcadeia deb1..bm. Voc pode ter ficado um pouco confuso com a explicao, mas alguns exemplos devem ajudar-lhe a entender. Examine os exemplos abaixo, relendo a explicao acima para tentar entender esta operao: aba subcadeia de aabaa aaba subcadeia de aabaa bb no subcadeia de aabaa 0 subcadeia de 100 01 no subcadeia de 100 100 subcadeia de 100

e subcadeia de 100Mais uma vez, colocamos, nos dois ltimos exemplos, dois casos especiais da operao. O penltimo exemplo mostra que a cadeia 12

Teoria da Computao

100 subcadeia de 100. Na verdade, essa uma propriedade geral: toda cadeia subcadeia dela prpria. J no ltimo exemplo, vemos a ocorrncia de outra propriedade geral: a cadeia vazia subcadeia de qualquer cadeia. As operaes sobre cadeias sero muito importantes no restante do curso. Por isso, vamos praticar um pouco essas operaes antes de passar para a ltima seo.

Aprenda Praticando Acompanhe atentamente a primeira questo, que j est respondida, e, depois, tente responder a segunda questo. 1) Nas questes abaixo, mostre o resultado de cada operao. Considere que o alfabeto { a, b, c }. a) aaa . bbc Resposta: aaabbc b) e . bba Resposta: bba c) (ca)3 Resposta: cacaca d) (aaab)1 Resposta: aaab e) ca subcadeia de ccca? Resposta: verdadeiro f) cca subcadeia de ccba? Resposta: falso 2) Nas questes abaixo, mostre o resultado de cada operao. Considere que o alfabeto { 1, 2, 3 }. a) 1 . 223 b) 3212 . e 13

Teoria da Computao

c) (11)2 d) (123)0 e) 11 subcadeia de 2131? f) 221 subcadeia de 221?

1.3 Operaes sobre linguagensVeremos, agora, as operaes sobre linguagens que sero mais importantes neste curso. Lembre-se, amigo(a) cursista, que as linguagens so meramente conjuntos de cadeias. Isso significa que todas as operaes que voc j aprendeu sobre conjuntos podem ser aplicadas s linguagens. De fato, duas das trs operaes que veremos sero meras operaes de conjuntos que voc j conhece. Apenas a ltima operao ser realmente novidade para quem j aprendeu conjuntos. Mostraremos como representar cada operao usando as letras L e M simbolizando duas linguagens quaisquer. Unio de L e M: LM Esta operao a mesma que vocs estudaram para conjuntos. O resultado da operao uma linguagem (conjunto) que contm todas as cadeias de L e todas as cadeias de M, e nenhuma cadeia alm dessas. Quer dizer, basta uma cadeia estar em L (ou em M) para fazer parte do resultado. Exemplos: { 1, 11 } { bab, aa, bb } { 01, 10 } { aa, b } { 0, 11 } { aa, bb } { 01, 10 } { } = { 0, 1, 11 } = { bab, aa, bb } = { 01, 10 } = { aa, b }

Todas as propriedades da unio de conjuntos se aplicam unio linguagens. Por exemplo: a unio de uma linguagem consigo mesma d como resultado ela prpria (ver penltimo exemplo). Outra propriedade que tambm vale : a unio de uma linguagem qualquer X com a linguagem vazia d a prpria linguagem X (ver ltimo 14

Teoria da Computao

exemplo). Interseco de L e M: LM Esta mais uma operao de conjuntos que usaremos com linguagens. O resultado dela uma linguagem que contm apenas as cadeias que esto em L e em M. Observe que, diferente da unio, uma cadeia precisa pertencer s duas linguagens para fazer parte do resultado! Alguns exemplos dessa operao: { aa, a } { 0, 1, 11, 001 } { 01, 111 } { aaa, aa } { a, bb } = {a}

{ 0, 00, 11 } = { 0, 11 } { } = { }

{ bb, b, bbb } = { }

Concatenao de L com M: LM Diferentemente das outras duas operaes sobre linguagens, esta no foi tirada do estudo dos conjuntos matemticos. Esta operao sobre linguagens definida a partir da operao de concatenao para cadeias (lembra que vimos na seo anterior?). A operao sobre linguagens representada por um pequeno crculo, lembrando um pouco o ponto usado para a concatenao de cadeias. O que a operao L M faz aplicar a concatenao entre cadeias vrias vezes. A cada vez, feita a concatenao de uma cadeia de L com uma cadeia de M (nesta ordem), gerando uma outra cadeia. O conjunto de todas as cadeias que voc puder gerar assim ser o resultado da operao L M. Alguns exemplos: { aa, bb } {c} { 01, 11 } { 101, 000 } {c} { aa, bb } { aab, b } { } = { aac, bbc } = { caa, cbb } = { 01aab, 01b, 11aab, 11b } ={ }

15

Teoria da Computao

Vamos explicar o primeiro exemplo, para que fique claro como calcular essa operao. Primeiro concatenamos aa (da primeira linguagem) com c (da segunda linguagem), dando o resultado aac. Depois, concatenamos bb (da primeira) com c (da segunda), dando a nova cadeia bbc. Como no temos mais opes, terminamos. Veja que, no exemplo, a linguagem de resultado contm exatamente as duas cadeias geradas: aac e bbc. Com base nessa explicao, tente entender os demais exemplos. Agora, vamos destacar algumas propriedades, com base nos exemplos acima. A primeira propriedade que queremos destacar que a ordem em que duas linguagens so concatenadas pode fazer diferena no resultado. Veja que, nos dois primeiros exemplos, aplicamos a operao de concatenao com as mesmas duas linguagens, mudando apenas a ordem em que elas so concatenadas. Por conta dessa simples mudana de ordem, o resultado deu diferente nos dois primeiros exemplos. Outra propriedade interessante pode ser vista no penltimo exemplo, onde temos a concatenao da linguagem { 101, 000 } com a linguagem vazia { }. A propriedade que a concatenao de qualquer linguagem com a linguagem vazia d como resultado a linguagem vazia. A explicao que no h nenhuma cadeia na linguagem vazia, ento, no temos fazer nenhuma concatenao envolvendo cadeias das duas linguagens. Logo, a linguagem resultante no ter nenhuma cadeia.

Aprenda Praticando Como das vezes anteriores, a primeira questo j est respondida. Analise-a e, depois, tente responder a segunda questo. 1) Nas questes abaixo, compute o resultado de cada operao. O alfabeto usado { a, b, c }. a) { a, aa } o { bc, cc } Resposta: { abc, acc, aabc, aacc } b) { b, cab, baba } { cab, cc } Resposta: { b, cab, baba, cc } 16

Teoria da Computao

c) { b, cab, baba } { cab, cc } Resposta: { cab } 2) Nas questes abaixo, compute o resultado de cada operao. O alfabeto, dessa vez, { 0, 1, 2 }. a) { e, 11 } { 11, 2, 2112 } b) { 1, 211, 0022 } { 00, 211, 0022 } c) { 1, 211, 0022 } { 00, 211, 0022 }

17

Teoria da Computao

Captulo 2 Autmatos Finitos DeterminsticosNo captulo anterior, apresentamos um conceito central neste curso, que o conceito de linguagem. Vimos que uma linguagem pode ser vazia, finita ou infinita. As linguagens infinitas, em especial, no foram representadas de maneira completamente matemtica elas foram representadas por descries informais. A partir deste captulo, veremos modelos matemticos que permitiro representar linguagens (tanto finitas quanto infinitas) de um modo completamente formal, usando uma notao puramente matemtica. A ideia chave consistir em tratar a linguagem como um problema matemtico e apresentar uma soluo matemtica para o problema. Por exemplo, ao invs da linguagem das cadeias que comeam com d, pensaremos no problema de testar quais as cadeias que comeam com d. Usando algum modelo computacional, poderemos criar um computador abstrato (ou um programa abstrato) para servir de soluo do problema. Um computador abstrato, basicamente, indica o passo-a-passo que voc deve seguir para testar uma cadeia qualquer. Cada modelo computacional permite criar inmeros computadores abstratos (ou programas abstratos). No restante do curso, veremos, a cada momento, um novo modelo computacional. Depois de aprender como cada modelo funciona, voc dever ser capaz de us-lo para representar um grande nmero de linguagens, tanto finitas como infinitas. Ou, em outras palavras, cada modelo servir para resolver um grande nmero de problemas matemticos. Neste captulo, veremos o primeiro modelo computacional do curso: o modelo de Autmatos Finitos Determinsticos, ou, apenas, modelo AFD. Esse um modelo simples que servir como base para voc entender outros modelos que veremos posteriormente.

2.1 Explicao InicialO nome autmato usado para indicar algo que se move sozinho. No caso dos Autmatos Finitos Determinsticos, esse movimento no fsico, mas apenas uma mudana abstrata de estado. Podemos 18

Teoria da Computao

pensar em um estado como a situao em que o autmato pode estar. O autmato muda de estado apenas diante de estmulos externos, que chamaremos de entradas do autmato. Para entender o funcionamento de um autmato, tome um procedimento que voc faz com certeza em casa: acender uma luz. Para isso, voc normalmente deve pressionar o interruptor existente do ambiente. A funo do interruptor pode ser modelada por autmatos e um dos problemas mais fceis de serem modelados. Podemos tomar um autmato finito na forma de um grafo direcionado (conjunto de pontos ligados ou no por setas) para representar o problema. Como voc bem sabe, um interruptor pode estar ligado ou desligado. Ou seja, essas so as situaes ou os estados em que voc pode encontrar um interruptor. No grafo, representaremos os estados como crculos, e dentro de cada crculo voc pode colocar um nome para melhor identificar o que o estado significa. Mas, afinal, quando um interruptor pode mudar de estado? Apenas quando ele recebe um estmulo externo (ou uma entrada). No caso do interruptor, a entrada ser o ato de pressionar. As mudanas entre os estados so representadas, no grafo, como setas acompanhadas da entrada que causa a mudana. O grafo que representa o autmato do interruptor pode ser visto abaixo:

Figura 1 Sistema de um boto liga/desliga

Todo autmato finito tem um estado inicial indicado por um tringulo ou uma seta. Podemos tambm usar a notao de uma seta com o nome incio. No autmato acima, assumimos que o estado inicial desligado. Ao pressionar o boto do interruptor, o mesmo passa para o estado de ligado. E permanece assim at que o interruptor seja pressionado novamente, o que o faz voltar para o estado desligado. Bem, o exemplo do interruptor deve ter feito voc entender um autmato, mas talvez ainda no tenha esclarecido como ele pode representar uma linguagem. Os autmatos finitos determinsticos 19

Teoria da Computao

(AFDs) sero autmatos cujas entradas so os smbolos vindos da cadeia que voc deseja testar. Os smbolos da cadeia so lidos da esquerda para direita. Quando chega ao fim da cadeia, dependendo do estado em que terminou, o autmato ir aceitar ou rejeitar a cadeia. Vamos considerar que aceitar indica que a cadeia faz parte da linguagem que o autmato representa. Vejamos agora um exemplo simples de um AFD: ele reconhece apenas a palavra amor. Nosso sistema deve ter a capacidade de responder quando a cadeia dada for exatamente como ele estava programado para aceitar. Em outras palavras, qualquer cadeia que no seja a palavra amor dever ser rejeitada. Cada ao ser a leitura de um smbolo. A representao grfica do autmato seria esta:

Figura 2 Autmato para reconhecer a palavra amor

Em relao ao primeiro autmato, note que, basicamente, a nica novidade foi a presena de um crculo duplo no estado q4. Esta notao indica o estado de aceitao ou estado final. Podemos considerar que os outros estados so todos estados de no aceitao. Quando o autmato termina de ler uma cadeia e para no estado de aceitao, se diz que o autmato aceita ou reconhece a cadeia. J se ele no conseguir ler a cadeia inteira ou se ele no parar em um estado de aceitao, dizemos que o autmato rejeita a cadeia. Para ilustrar o funcionamento do autmato, vamos analisar alguns exemplos. Queremos saber como o autmato vai se comportar lendo as seguintes cadeias: ambiente, amora e amor. Comeando com a palavra ambiente, o autmato comea do estado q0, e s muda de estado quando l a, que justamente a primeira letra de nossa cadeia, ento temos:

20

Teoria da Computao

Partimos para a segunda letra:

Depois, para a letra b:

Neste caso, o autmato para por no haver mais possibilidades de sair de q2. Como este no um estado final, conclumos que o autmato rejeitou a cadeia ambiente. Vejamos outro exemplo com a palavra amora:

Agora lendo m:

Lendo o:

21

Teoria da Computao

Lendo r:

Lendo a:

O autmato para novamente, s que, neste caso muito interessante, note que estamos no estado de aceitao, mas o autmato no tem opo para o ltimo smbolo, deixando o smbolo a sem ser lido. Como dissemos antes, se a cadeia no for lida inteira, ela rejeitada pelo autmato. Portanto, ele rejeita amora. Tomemos o exemplo da cadeia amor. J temos a certeza que o autmato vai reconhecer esta cadeia como foi dito h pouco, mas devemos entender exatamente como isto acontece. Analisemos os passos a seguir: Lendo a:

Agora lendo m:

22

Teoria da Computao

Lendo o:

Lendo r:

Terminamos a leitura da palavra amor, percorremos todos os caracteres da palavra a agora devemos observar o autmato. Note que estamos no estado q4, que justamente o estado de aceitao. Se as duas situaes ocorrerem: terminamos de ler a cadeia e estamos no estado de aceitao, ento reconhecemos (aceitamos) a palavra. Portanto, a cadeia amor foi aceita!

Voc j pode entender que realmente o autmato finito que estamos trabalhando neste momento aceita apenas a palavra amor. E j deve ter concludo que uma cadeia s reconhecida se, ao trmino da leitura da cadeia, o autmato estiver no estado final. Talvez voc esteja pensando que esses autmatos so simples demais e pouco poderosos reconhecedores de cadeias. Pode parecer para voc que seria difcil fazer um autmato para reconhecer vrias cadeias, por exemplo. Mais difcil ainda seria criar um autmato para uma linguagem infinita (com infinitas cadeias), no acha? Na verdade, no to difcil. Tudo depende de como voc cria 23

Teoria da Computao

as mudanas de estados. Como exemplo, veja abaixo um autmato pequeno, mas capaz de reconhecer um conjunto infinito de cadeias (ou seja, uma linguagem infinita). Tente compreender como isso possvel, antes de ler o texto adiante.

Figura 3 Autmato Finito que reconhece linguagem infinita

Analisando com calma o AFD, notamos que ler qualquer quantidade de 0s repetidamente no far com que o autmato saia do estado inicial. Somente quando ler o primeiro smbolo 1, o AFD mudar para o estado final. Se este for o ltimo smbolo da cadeia, ento ele aceita a cadeia. Exemplos de cadeias que so aceitas por esse autmato so: 1, 01, 00001. Faa o teste no autmato acima e comprove! Isso dar a voc mais confiana de que realmente o autmato aceita infinitas cadeias. Uma vez que ele aceita infinitas cadeias, tente descrever informalmente a linguagem aceita pelo autmato. Faa isso antes de ler o prximo pargrafo. Podemos dar a seguinte descrio informal da linguagem que esse AFD aceita: todas as cadeias de nenhum ou mais smbolos 0s seguidos de um nico smbolo 1. Relembrando o que dissemos no incio do captulo, ns vamos tratar uma linguagem como um problema, ou melhor, como a soluo de um problema. Nesse caso, o problema seria testar se uma cadeia de entrada tem nenhum ou mais smbolos 0s seguidos de um nico smbolo 1. O AFD acima uma soluo para esse problema, pois ele representa como fazer, passo-a-passo, esse teste em uma cadeia. Essa uma maneira indireta de representar uma linguagem, mas uma maneira que usaremos bastante no decorrer do curso (tanto com o modelo AFD como com outros modelos). Por isso, tenha sempre em mente que um AFD representa uma linguagem. Representa indiretamente, mas representa. O nico detalhe que ainda no esclarecemos foi o fato de que a 24

Teoria da Computao

representao da linguagem deveria ser puramente matemtica (como dissemos no incio deste captulo). Porm, at agora, s vimos AFDs representados graficamente. Ser que possvel representar um AFD de maneira puramente matemtica? Sim, possvel. Veremos isso a seguir.

2.2 Definio FormalPodemos definir matematicamente um autmato determinstico D por meio uma quntupla (ou uma 5-tupla): D = (Q, , , s, F), onde: Q o conjunto de estados, que deve ser finito. (sigma) o alfabeto de entrada, que contm os smbolos que podem ser usados nas cadeias testadas no autmato (delta) a funo de transio. do tipo: Q x Q. Isso significa dizer que, estando em um estado de Q e lendo um smbolo do alfabeto , ela faz o autmato passar para outro estado de Q. s o estado inicial. Ele um elemento de Q (ou seja, s Q). F um conjunto dos estados finais ou estados de aceitao. Ele um subconjunto de Q (ou seja, F Q). Por ser um conjunto, pode haver mais de um estado final, assim como tambm pode no haver nenhum. Veremos adiante autmatos com essa caracterstica. Note tambm que no h restries quanto ao estado inicial ser um dos estados finais. J estamos acostumados a trabalhar com autmatos na forma grfica, mas vamos ver agora, por meio de exemplos, como passar da forma grfica para a forma de funo e vice-versa. Primeiramente, vamos partir da representao grfica para a representao formal. Suponha o autmato para reconhecer se h um nmero mpar de 0s em cadeias formadas por 0s e 1s. Vamos cham-lo de D1. A forma grfica de D1 dada abaixo: finito

25

Teoria da Computao

Figura 4 Autmato que reconhece nmeros mpares de zeros

Talvez parea difcil para voc, neste momento, aceitar que esse autmato consegue testar qualquer cadeia se h uma quantidade mpar de zeros, mas ns vamos esclarecer adiante. Na definio formal de D1, precisamos preencher os cinco parmetros da quntupla D1 = (Q, , , s, F). O primeiro o conjunto de estados Q, que ser simplesmente {q0, q1}. Para o parmetro seguinte, vamos observar o enunciado do autmato. Ns dissemos acima que s vo ser dados como entrada cadeias de 0s e 1s. Isso significa que o alfabeto {0,1}. O estado inicial (parmetro s) aquele representado por uma seta, que q0. Quanto aos estados de aceitao, so representados graficamente por crculos duplos. No autmato acima, s tem um estado de aceitao, que o estado q1. Assim, j podemos escrever a seguinte quntupla: D1 = ({q0, q1}, {0, 1}, , q0, {q1}) Lembramos que, na representao formal, os estados de aceitao so dados por um conjunto. Por isso, o parmetro F foi trocado pelo conjunto unitrio {q1}. J o estado inicial sempre nico, ento no precisou ser representado por um conjunto. Mas voc deve estar se perguntando: quem o delta ()? O delta a funo de transio. H uma maneira simples de represent-la, que usando uma tabela. Cada linha representa um estado (de origem), e cada coluna, um smbolo. Na clula formada pelo encontro entre um estado (origem) e um smbolo, coloca-se qual o estado para onde a seta aponta (destino), se houver seta para o smbolo em questo. A funo de transio de D1, ainda sem as clulas preenchidas, mostrada a seguir: q0 q1 0 1

26

Teoria da Computao

Agora, para preencher a tabela, devemos acompanhar o autmato da seguinte forma: estado em q0 e lendo 0 qual a ao devemos tomar? Olhando para o autmato, vemos que a ao mudar para o estado q1, pois h uma seta saindo de q0, tendo o smbolo 0 anotado sobre ela, e esta seta entra em q1. Ento, preenchemos a clula no encontro entre q0 e 0 com o valor q1. Depois, estando em q0, lendo 1, o autmato permanece no mesmo estado. Marcamos ento q0 na tabela. Fazemos a mesma anlise para o estado q1 e obtemos a seguinte tabela: q0 q1 0 q1 q0 1 q0 q0

A representao da funo de transio usando tabelas bastante prtica e, por isso, ser a mais usada. Porm, existem outras formas de represent-la, que so equivalentes. A seguir mostramos as transies do autmato D1 usando outra representao formal: (q0, 0) = q1 (estando em q0, lendo 0, mude para o estado q1) (q0, 1) = q0 (q1, 0) = q0 (q1, 1) = q0 Vamos explicar essa segunda representao da funo de transio () com base na representao por tabela. Veja que usamos a letra grega delta () como uma funo que recebe dois argumentos (um estado e um smbolo) e retorna um valor (um estado). Voc pode entender os dois argumentos como sendo a linha e a coluna da tabela. O valor seria o contedo da clula, na tabela. Por exemplo, o valor de (q0, 1) voc pode achar procurando na linha q0, coluna 1. Confira que o valor q1. Na representao final do AFD, basta usar uma das duas formas para representar a funo de transio. Das duas, usaremos com mais frequncia a representao com tabelas. Mas isso no significa que voc no deva saber a segunda forma ns usaremos essa forma mais adiante! Por isso, aprenda as duas. Pronto, com isso, conclumos a nossa primeira representao formal de um AFD. A representao completa, usando uma tabela 27

Teoria da Computao

para representar , fica assim: D1 = ({q0, q1}, {0, 1}, , q0, {q1}) q0 q1 0 q1 q0 1 q0 q1

Veja que, neste AFD, a tabela ficou completa, sem nenhuma clula vazia. Neste caso, dizemos que D1 um AFD completo. Vamos considerar que um AFD completo se ele tem transies para todos os smbolos em todos os estados. Caso contrrio, ele ser chamado de parcial. Um exemplo de AFD parcial (no completo) dado abaixo.

Figura 5 Autmato Finito Determinstico parcial

Voc j consegue entender por que ele parcial? Uma dica: tente representar as transies dele com tabela para descobrir se alguma clula fica vazia. Como voc deve observar, as clulas da linha q1 ficam todas vazias naquele AFD. Isso porque ele no tem transies saindo do estado q1 para nenhum smbolo. Desse modo, confirmamos que ele no um AFD completo um AFD parcial. No decorrer do curso usaremos autmatos parciais sem problema. Basta considerar que, quando no houver transio para o prximo smbolo da cadeia, o autmato vai rejeitar a cadeia. Por exemplo, no AFD acima, se dermos a cadeia 11 como entrada, o que acontece? Ele comea em q0, ento l o primeiro 1 e vai para q1. Depois, ele ler o segundo smbolo 1 e ir para qual estado? Em q1 no tem transio para o smbolo 1! Por isso, a cadeia ser rejeitada! Podemos converter um AFD parcial para um AFD completo de maneira relativamente simples: 1. Crie um novo estado, que ser chamado de estado sugadouro. Para cada smbolo, crie uma transio deste estado para ele mesmo. No autmato da figura 5, poderamos criar um estado q2 assim: 28

Teoria da Computao

2. Nos outros estados, se estiver faltando transio com algum smbolo, crie a transio apontando para o sugadouro. No autmato de exemplo, falta a transio 0 em q0 e faltam as transies 0 e 1 em q1, o que nos leva a acrescentar as transies para q2 assim:

O que acontecer que, em todos os casos em que no havia transio no primeiro autmato, haver uma transio indo para o estado sugadouro, no novo autmato. Os dois autmatos so equivalentes, aceitando as mesmas cadeias e rejeitando as mesmas cadeias. A diferena que, as cadeias que o primeiro autmato rejeitaria por no conseguir ler toda a cadeia, o novo autmato rejeitaria porque ficaria preso no estado sugadouro, depois de ler toda a cadeia. Agora que j vimos vrios detalhes dos Autmatos Finitos Determinsticos (AFDs), hora de parar um pouco para fixar o que foi visto. Faremos isso por meio dos exerccios a seguir.

Aprenda Praticando Observe o exerccio resolvido e, depois, tente resolver outro parecido. 29

Teoria da Computao

1) Crie um AFD para representar a linguagem L = { acaba }, definida sobre o alfabeto { a, b, c }. Resposta: A princpio, trivial criar um AFD para reconhecer uma linguagem com uma s cadeia. Basta criar um estado inicial e, depois dele, criar um estado para cada smbolo da cadeia. Ento, obtemos facilmente o autmato, que chamaremos de D 2:

Mas a forma grfica do autmato imprecisa e, por isso, no considerada uma representao formal (do ponto de vista matemtico) do autmato. A representao formal seria dada por uma tupla D2 = (Q, , , s, F), onde: Q facilmente identificvel, pois basta listar os nomes representados entre crculos no autmato acima: {q0, q1, q2, q3, q4, q5}. Quanto ao alfabeto (), j informamos no enunciado que seria { a, b, c }. O estado inicial (s) aquele identificado por uma seta: o estado q0 . Os estados finais ou de aceitao (F) so os estados com crculos duplos. No autmato, s tem um, o que d esse conjunto: {q5}. Quando funo de transio (), ela ser construda na forma de tabela, como ensinado anteriormente. Pronto, agora temos todos os componentes necessrios para montar nosso autmato: D2 = ({q0, q1, q2, q3, q4, q5}, {a, b, c}, , q0, {q5}), onde dado por: q0 q1 q2 a q1 q3 b c q2 -

30

Teoria da Computao

q3 q4 q5

q5 -

q4 -

-

Veja que este um autmato parcial, pois no tem transio, em cada estado, para todo smbolo. Poderamos deix-lo assim mesmo, mas, para praticar os conceitos, vamos criar o autmato completo equivalente. Para isso, criamos um novo estado q6 para ser o estado sugadouro. Depois, criamos as ligaes que faltam no autmato acima, fazendo-as apontarem para q6. A forma grfica mostrada abaixo:

Note que uma vez que o autmato chega em q6, qualquer que seja o restante da cadeia, o autmato no sai mais do estado. Agora, podemos refazer a definio formal assim: D2 = ({q0, q1, q2, q3, q4, q5, q6}, {a, b, c}, , q0, {q5}), onde dado por: q0 q1 q2 q3 q4 q5 a q1 q6 q3 q6 q5 q6 b q6 q6 q6 q4 q6 q6 c q6 q2 q6 q6 q6 q6

Veja que a tabela agora est toda preenchida, como tpico de um AFD completo. Em especial, todas as posies que no 31

Teoria da Computao

tinham valor (representadas por um - antes), agora tm o estado q6. 2) Crie um AFD para representar a linguagem L = { baba }, definida sobre o alfabeto { a, b }. Esta questo voc dever responder. Em caso de dvidas, no deixe de consultar os tutores, por meio do ambiente de ensino.

2.3 Criando AFDsNos exerccios acima, construmos apenas AFDs para linguagens unitrias (isso , linguagens de uma s cadeia). Nesta seo, deremos algumas dicas para ajudar voc a construir AFDs para linguagens mais complexas, em especial, para construir AFDs para linguagens infinitas. Na construo de um autmato, o grande segredo fazer com cada estado tenha um significado. Cada estado deve representar alguma propriedade importante da cadeia. Mas, parar escolher qual propriedade importante de ser representada, voc precisa analisar bem o problema. Para voc entender melhor, vamos tomar como exemplo uma linguagem: todas as cadeias que comeam com 11, sobre o alfabeto {0 ,1}. Em outras palavras, precisamos criar um autmato para testar se uma cadeia comea com 11. Note que este um caso de uma linguagem infinita, o que no quer dizer que seja complexo resolver esse tipo de problema. O autmato precisa ter, pelo menos, um estado inicial. No caso, o estado inicial representa que ainda no foi visto nada da cadeia. Outro estado que o autmato vai precisar um que represente que o primeiro smbolo 1. E, ainda, um terceiro estado dever representar que os dois primeiros smbolos so 1. Este terceiro estado representa justamente a propriedade que queremos testar, por isso, ele ser estado de aceitao. Essas so as trs nicas situaes que interessam para o problema, portanto, precisaremos apenas desses trs estados. Um detalhe importante que os nomes que daremos aos estados no importante. Temos dado os nomes q0, q1, ..., qn, aos estados dos AFDs, mas poderamos cham-los de qualquer outra forma. Para mudar um 32

Teoria da Computao

pouco, vamos chamar os trs estados desse novo autmato de X, Y e Z. Estes trs estados esto representados abaixo, com bales indicando o significado de cada um:

E agora, o que falta ao autmato? Voc capaz de complet-lo sozinho? O que falta so as transies entre os estados, que so as mudanas que podem ocorrer para cada smbolo lido. So elas que vo fazer com que, realmente, os estados tenham o significado que planejamos. Se fizermos essas ligaes da forma errada, os estados no faro o que realmente queramos. Ou seja, no basta pensar corretamente nas situaes que os estados representam preciso criar transies que forcem os estados a cumprir o que deveriam. Voltando ao exemplo acima, vamos criar as transies em cada estado. Comeando no estado inicial, o que deveria acontecer se fosse lido o smbolo 1? Bem, no estado X, ainda no foi lido nada, ento, qualquer smbolo lido ser o primeiro da cadeia. Bem, o estado que representa que o primeiro smbolo da cadeia 1 Y, ento criamos uma seta de X para Y, anotada com o smbolo 1. E o que acontece em X se ler o smbolo 0? Essa situao seria a de que o primeiro smbolo da cadeia 0. Porm, esta no uma situao que interessa ao problema, pois, uma cadeia com essa caracterstica deve ser rejeita! Para foramos a rejeio da cadeia, vamos deixar o autmato sem essa transio. (Se voc desejar fazer um autmato completo, crie um estado sumidouro e faa uma transio para ele, neste caso). Agora vamos tratar o estado Y. O que deveria acontecer se fosse lido um 1 nesse estado? Bem, considerando que Y representa a situao que o primeiro smbolo 1, ao ler mais um smbolo 1, o autmato poder concluir que os dois primeiros smbolos so 1. 33

Teoria da Computao

Portanto, criaremos a transio de Y para Z, para o caso de ler 1. O caso de ler um smbolo 0 no estado Y parecido com o do estado X: no desejamos que essa situao ocorra, ento deixamos sem transio. Por fim, vamos tratar o estado Z. O que deveria acontecer se fosse lido um smbolo 0? E se fosse lido um smbolo 1? Bem, como dissemos antes, o estado Z representa exatamente a situao que se deseja testar, que se a cadeia comea com dois smbolos 1s. Uma vez que j sabemos como a cadeia comea, voc acha que algo que for lido depois vai ter importncia? A resposta no. Neste problema, s precisamos saber como a cadeia comea e se ela comear da maneira que esperamos, ela deve ser aceita, independente do que tem no restante da cadeia. Depois que sabemos que os dois primeiros smbolos so 1, podemos ler qualquer smbolo (0 ou 1) que essa situao da cadeia no se altera. Portanto, se o AFD ler 0 ou 1 no estado Z, ele deve permanecer nesse estado. O resultado final ser este AFD:

O autmato ainda est em sua representao grfica. A representao formal dele voc pode obter seguindo tudo o que explicamos em sees passadas. Chamando este autmato de D3, teramos a seguinte representao formal: D3 = ({X, Y, Z}, {a, b}, , X, {Z}) X Y Z 0 q1 q6 q3 1 q6 q6 q6

Resumindo o que vimos, para criar um AFD, voc precisa comear analisando bem a linguagem (ou o problema). Em geral, a linguagem indicar uma propriedade desejada na cadeia. Ento, na sua anlise, voc deve identificar as situaes intermedirias em que o autmato pode se encontrar ao ler cadeia, at que ele identifique a propriedade 34

Teoria da Computao

desejada. Cada situao dessas ser um estado do autmato. Por fim, voc dever criar as transies entre esses estados de uma maneira coerente com a situao que cada estado representa. Em certo sentido, criar AFDs para uma linguagem (ou problema) como fazer um programa (em alguma linguagem de programao) para um dado problema. Em ambos os casos, voc tem que fazer tudo com muita ateno, buscando colocar um sentido lgico no que est fazendo. Outra semelhana que, tanto a programao como criao de AFDs, so coisas que se aprendem praticando. Por isso, vamos para mais uma seo de exerccios.

Aprenda Praticando Desta vez, colocamos apenas exerccios resolvidos nesta seo, mas voc ter a ltima seo inteira para resolver por conta prpria. 1) Crie um AFD que represente o conjunto de cadeias sobre o alfabeto {0,1} que tenham 01 como subcadeia. Resposta: Em outras palavras, o objetivo do AFD que queremos ser encontrar, em qualquer parte da cadeia, um smbolo 0 seguido de um smbolo 1. Para definir os estados, temos que pensar nas possveis situaes que poderemos encontrar ao tentar atingir esse objetivo. A primeira situao, que representar o estado inicial, a situao em que nada foi visto da sequncia 01 que queremos. Voltaremos ao padro que seguimos no incio e chamaremos esse estado de q0 (mas podia ser qualquer outro nome). Uma segunda situao acontece depois de ler o smbolo 0, que o comeo da sequncia esperada. Essa situao seria foi visto um 0 mas falta ver um 1 e ser representada pelo estado q1. Nesse estado, vale a pena dar mais uma dica: ao pensar nas situaes relevantes para o problema, voc pode pensar na parte que j foi lida da cadeia e na parte que falta ser lida. Claro que isso depende do problema e voc precisar praticar para aprender a identificar as situaes importantes (e que formaro os estados).

35

Teoria da Computao

Por fim, a terceira situao aquele em que, depois de ter visto um 0, tambm foi visto o smbolo 1. Essa a situao que poderamos descrever como foi visto 01 (e no falta mais nada) e ela ser representa por q2. Como essa a situao que queremos encontrar na cadeia, q2 ser um estado de aceitao. Um esboo do autmato, portanto, seria esse:

J colocamos nele as transies mais importantes, que tratam o reconhecimento da sequncia 01, pois isso pode ajudar a entender as situaes que cada estado representa. Agora vamos completar as transies restantes. Vamos comear completando as transies de q2, que so as mais fceis de entender. Levando em considerao a descrio linguagem, perceba que basta identificar 01 em qualquer lugar da cadeia ela dever ser aceita. Isso nos leva a aceitar que, uma vez que atingido o estado de aceitao, no deveremos mais sair dele. Com isso, obtemos o seguinte:

Agora vamos ao estado q0, que representa nada foi visto. Falta completar a transio para q0 lendo 1. Neste caso, no faria sentido ir para q1, pois ele representa o fato de que foi visto um 0 e isso no verdade agora. Na verdade, para a linguagem em questo, ver um 1 neste momento no tem importncia alguma, ou seja, a cadeia no deve caminhar em direo aceitao ainda. A cadeia tambm no deve ser rejeitada, porque falta procurar 01 no restante dela. Por isso, o correto a fazer simplesmente permanecer em q0, j que nada da cadeia 01 foi visto, mas algo ainda pode ser visto depois. E se estivermos em q1 e lermos 0, o que deve acontecer? Este estado representa que foi visto um 0 e que falta ainda ver um 1. Ora, se vier outro 0, a situao ainda a de que foi visto um zero, certo? Portanto, o autmato deve permanecer no prprio estado q1. 36

Teoria da Computao

Assim, chegamos ao autmato AFD final:

E a sua representao formal ser: D4 = ({q0, q1, q2}, {0, 1}, , q0, {q2}), onde dado por: q0 q1 q2 0 q1 q1 q2 1 q0 q2 q2

2) Crie um autmato para reconhecer a linguagem das cadeias sobre o alfabeto {0,1} que terminam em 11. Este problema tem alguma semelhana com o anterior, porque o objetivo tambm identificar uma subcadeia. A diferena simplesmente que, nesta linguagem, a subcadeia deve aparecer no fim. Por isso, podemos comear este autmato de modo semelhante ao anterior. Neste AFD tambm teremos trs estados, com sentidos parecidos aos dos estados que criamos na questo anterior: q0 indicar que nada da cadeia 11 foi visto (nos ltimos smbolos) q1 indicar que apenas um 1 foi visto (nos ltimos smbolos) e falta ler outro 1 q2 indicar que dois 1s foram vistos (nos ltimos smbolos) Assim, de modo semelhante questo anterior, o desenho bsico do autmato ser este:

Analisemos, agora, a questo da cadeia 110, ou seja, se depois de ler 11 o prximo smbolo for 0. Neste caso, olhando para os 37

Teoria da Computao

ltimos smbolos, no temos mais a subcadeia desejada. Por isso, temos que fazer o autmato voltar para o estado inicial, resultando nesse autmato:

Nosso autmato j computa corretamente cadeias como: 110, 1101, 11011, 11011011. Destas, apenas as duas ltimas cadeias levam o autmato ao estado de aceitao, estando de acordo com a linguagem. Vejamos agora o caso de 111, 1111, 111111, pois todos eles devem ser aceitos. Isso quer dizer que quando o autmato est em q2 e comea a ler uns, dever continuar aceitando as cadeias. Isso faz sentido, pois q2 representa a situao que os dois ltimos smbolos so 1s e, se outro smbolo 1 for lido, essa situao no mudou. Obtemos ento o seguinte autmato:

Precisamos, ainda, definir o que fazer se q1 ler 0. Este estado representa que apenas um 1 foi visto, ento essa situao aconteceria com alguma trecho 10 de uma cadeia. Ora, esse trecho da cadeia representa algo de relevante para esta linguagem? No! Ento, devemos voltar para o estado q0, que representa que nada do trecho 11 foi visto nos ltimos smbolos. Em q0 o autmato esperar novamente que um trecho 11 aparea na cadeia. Por exemplo, essa volta a q0 acontecer com a cadeia 1011. Veja que, nela, o autmato, comeando em q0, iria para q1, voltaria a q0 e, depois, seguiria para q1 e q2, terminando com a aceitao da cadeia. Por fim, vamos definir a ao do autmato quando ele est em q0 e l 0. Novamente temos um caso que no interessa 38

Teoria da Computao

para essa linguagem. Por isso, conclumos facilmente que o autmato dever continuar em q0. Temos agora o seguinte autmato:

Depois de concluir a construo da forma grfica do autmato, vale a pena fazer alguns testes com ele para ver se ele d as respostas adequadas. Ou seja, devemos testar algumas cadeias que fazem parte da linguagem para ver se o autmato as aceita e devemos testar algumas cadeias que no fazem parte da linguagem para ver se ele as rejeita. Confirme que o autmato aceita todas essas cadeias (terminadas em 11): 011, 111, 01011, 0011, 000011. Confirme tambm que o autmato rejeita todas essas cadeias (que no terminam em 11): 01, 110, 101, 00, 0110, 01101. Este autmato est correto e vai dar as respostas esperadas, mas quando voc for criar um autmato pode acontecer de ele no dar as respostas corretas ou aceitando ao invs de rejeitar ou rejeitando ao invs de aceitar. Nestes casos, reveja o processo de criao do AFD, usando a cadeia que deu a resposta errada. Isso pode lhe ajudar bastante a encontrar onde a sua lgica falhou! Voltando para o autmato, agora s precisamos escrev-lo da maneira formal: D5 = ({q0, q1, q2}, {0, 1}, , q0, {q2}), onde dado por: q0 q1 q2 0 q0 q0 q0 1 q1 q2 q2

39

Teoria da Computao

3) O conjunto de cadeias sobre o alfabeto {0, 1} que no contenham 1s. Observao: a cadeia vazia e deve ser aceita. Resposta: Essa questo nos faz pensar sobre duas indagaes: O autmato pode aceitar uma cadeia sem smbolos (a cadeia vazia)? Um estado pode ser inicial e de aceitao ao mesmo tempo? A resoluo dessa questo, apresentada a seguir, deve esclarecer essas perguntas para voc. A linguagem pode ser entendida como o seguinte problema: testar se a cadeia no tem nenhum smbolo 1. Para isso, faremos um autmato que leia vrios 0s e aceite-os. Se algum 1 for lido, o autmato sai do estado de aceitao. Podemos comear este autmato com apenas um estado, que pode ser descrito como s viu zeros ou, ainda, no viu smbolo 1. Esta situao a situao em que o autmato comea e, ao mesmo tempo, tambm a situao desejado. Por isso, teremos de fazer o estado ser inicial e de aceitao ao mesmo tempo. O autmato parcial para o problema, portanto, seria esse:

Esse autmato j est correto. Ele aceita as cadeias corretas lendo-as completamente e parando no seu nico estado, mas ele rejeita cadeias como 01 pelo simples fato de no haver transio para o smbolo 1. Se voc desejar fazer um autmato completo, que sempre leia toda a cadeia, s precisa adicionar uma ao para o smbolo 1 que leve a um estado sugadouro, assim:

40

Teoria da Computao

Agora, daremos a definio formal desse autmato: D6 = ({q0, q1}, {0, 1}, , q0, {q0}), onde dado por: q0 q1 0 q0 q1 1 q1 q1

Pronto, terminamos esse exerccio. Na parte final deste captulo, ser a sua vez de praticar a criao de AFDs. Lembre-se de pedir ajudar no ambiente, se precisar!

Exerccios Propostos 1. Fornea AFDs que aceitem as seguintes linguagens sobre o alfabeto {0,1}: a) O conjunto das cadeias que terminam em 00. b) O conjunto das cadeias com trs 0s consecutivos (ou seja, cadeias com a subcadeia 000). c) O conjunto das cadeias que tm 011 como subcadeia. d) O conjunto das cadeias com nmero par de 1s. e) O conjunto das cadeias com nmero mpar de 0s. f) O conjunto das cadeias tais que cada bloco de cinco smbolos consecutivos contm, pelo menos, dois zeros. g) O conjunto de cadeias cujo terceiro smbolo a partir da extremidade direita 1. h) O conjunto de cadeias que comeam ou terminam (ou ambos) com 01. i) O conjunto de cadeias tais que o nmero de 0s divisvel por 5. j) O conjunto de cadeias tais que o nmero de 1s divisvel por 3.

41

Teoria da Computao

Captulo 3 Autmatos Finitos No-DeterminsticosVoc estudou, no captulo anterior, os Autmatos Finitos Determinsticos (AFD), que formam o modelo computacional mais simples do curso. Voc conhecer agora um modelo similar de autmatos que, em certo sentido, oferece mais liberdade a voc, criador de autmatos. A ideia deste novo modelo de um autmato que pode estar em vrios estados ao mesmo tempo ou ainda que no precise ler um caractere para mudar de estado. Estas so as duas principais caractersticas de um autmato finito no-determinstico (AFND). Em outras palavras um autmato lendo um smbolo pode ir para um estado ou para vrios estados ao mesmo tempo. Tambm pode estar em um estado e passar para outro sem necessariamente ler um smbolo. Estudaremos as caractersticas dos AFND e, posteriormente, compararemos com os AFD para verificar se as diferenas do AFND o tornam mais poderoso.

3.1 Explicao InicialVejamos agora a forma grfica de um AFND:

A nica diferena desse autmato para o que estamos acostumados a trabalhar que q0 tem duas transies lendo 1. Este estado, quando ler 1, vai para o conjunto {q0, q1} e fica nos dois estados ao mesmo tempo. Veremos agora o comportamento do autmato com algumas entradas: suponha a cadeia 110, comeamos em q0 lendo 1 e indo para os estados {q0, q1}. O diagrama a seguir mostra o resultado da ao:

42

Teoria da Computao

O autmato est, ao mesmo tempo, no estado q0 e q1. A partir de agora, toda vez que o autmato ler um smbolo de entrada, deve-se acompanhar o andamento de todos os estados atuais. Lendo o segundo smbolo, temos:

O estado q1 no tem transio lendo 1 ento simplesmente o caminho de q1 abandonado. Note tambm o estado q0 que, lendo 1, novamente bifurcou e estamos novamente em dois estados.

Vamos ento para o terceiro smbolo da cadeia. Neste caso, temos duas situaes: calculando primeiro q0, lendo 0, obtemos q0. Agora, a partir de q1, lendo 0, obtemos q2. O resultado esse:

Tambm poderamos representar esse processo de teste da cadeia mostrando os conjuntos obtidos a cada etapa, assim: 43

Teoria da Computao

{q0} lendo 1 {q0, q1} lendo 1 {q0, q1} lendo 0 {q0, q2} Igualmente ao estudado em AFD, quando terminamos de ler a cadeia e estamos num estado de aceitao, aceitamos esta cadeia no AFND. Em particular, se o AFND terminar em vrios diferentes estados, basta ter um estado de aceitao, para que a cadeia seja considerada aceita. No exemplo acima, o AFND terminou no conjunto de estados {q0, q2}. Como um deles (q2) estado de aceitao, a cadeia 110 foi aceita. Isso significa que nem sempre voc vai precisar calcular todos os caminhos possveis no AFND para uma certa cadeia. Bastar que voc ache um caminho que chegue ao estado de aceitao e voc poder concluir imediatamente que a cadeia aceita, mesmo sem voc ter calculado os outros caminhos! No exemplo anterior, bastaramos ter descoberto o caminho abaixo para concluir que a cadeia 110 aceita pelo AFND:

Como este caminho sozinho, termina no estado de aceitao, no precisamos examinar os outros caminhos conclumos que a cadeia aceita. Um detalhe que gostaramos de lembrar que, assim como os AFDs, os AFNDs servem para representar linguagens. Eles fazem isso de uma maneira sutil, tratando a linguagem como o problema de aceitar as cadeias que so da linguagem e rejeitar as que no so da linguagem. Isso precisa estar sempre claro na sua mente! Porm, queremos representar as linguagens da maneira mais matematicamente precisa que pudermos. Por isso, vamos agora definir os AFNDs formalmente, como fizemos para os AFDs.

44

Teoria da Computao

3.2 Definio FormalParecido com os AFDs, podemos definir matematicamente um autmato finito no-determinstico N por meio de uma quntupla (ou 5-tupla): N = (Q, , , s, F) onde: Q o conjunto finito de estados. o alfabeto de entrada. a funo de transio. do tipo: Q x 2Q. Significa dizer que estando em um estado e lendo um smbolo do alfabeto faz o autmato passar para um conjunto de estados do autmato. s Q o estado inicial. F Q: os elementos de F so os estados finais ou estados de aceitao. Voc j deve ter percebido que Q, , q0 e F tm o mesmo significado para os AFD. A nica diferena no , que agora pode acessar zero, um ou mais estados. Como exemplo, vamos fazer a representao formal do autmato N1, que levemente diferente do AFND mostrado na seo anterior. N1 mostrado abaixo em sua forma grfica.

Formalmente, este autmato pode ser representado assim: N1 = ({q0, q1, q2}, {0, 1}, , q0, {q2}) Com o seu conhecimento de AFD deve ser fcil compreender a parte acima. Porm, ela est incompleta porque ainda falta definir a funo e esta a parte do AFND que realmente diferente de um AFD. Porm, da mesma maneira que nos AFDs, podemos representar essa funo com uma tabela. A diferena que a clula da tabela mostrar um conjunto de destinos possveis ao ler o smbolo dado. No caso do autmato N1, a funo de transio dada pela tabela:

45

Teoria da Computao

q0 q1 q2

0 {q0} {q2}

1 {q0, q1}

3.3 Relao entre AFD e AFNDPelo que mostramos at agora, talvez fique em voc a sensao de que autmatos finitos no-determinsticos (AFNDs) so mais poderosos que autmatos finitos determinsticos (AFDs), pois AFNDs podem estar em mais de um estado ao mesmo tempo. Na verdade, dizer que um modelo mais poderoso que outro significa afirmar a existncia de alguma linguagem que os AFND reconhecem e que nenhum AFD pode reconhecer. O objetivo desta seo mostrar que isso no verdade. Queremos mostrar a equivalncia entre os dois modelos. Para isso, podemos mostrar como converter de um modelo para outro, nas duas direes. Primeiro, teramos que mostrar como converter de um AFD para um AFND, mas essa uma converso trivial. Na forma grfica, nem mesmo seria necessrio alterar nada no AFD para convert-lo para um AFND, pois, tudo o que um AFD permite, um AFND tambm permite. A converso de um AFD para um AFND provaria uma pequena diferena apenas na representao formal da funo de transio: seria necessrio transformar cada clula da tabela do AFD, que lista um certo estado, em um conjunto unitrio contendo esse mesmo estado. O mais difcil mostrar a outra converso: de um AFND para um AFD. A partir de agora, vamos mostrar o procedimento para voc transformar qualquer AFND em um AFD equivalente, de maneira que ambos reconheam a mesma linguagem (ou seja, toda cadeia que um deles aceitar, o outro tambm deve aceitar; toda cadeia que um deles rejeitar, o outro tambm deve rejeitar). Tome como exemplo o seguinte AFND:

46

Teoria da Computao

N2 = ({q0, q1, q2}, {0, 1}, , q0, {q2}) q0 q1 q2 0 {q0, q1} 1 {q0} {q2}

Note que este autmato apresenta transies que levam para um conjunto contendo zero, um ou mais estados, que so as caractersticas que distinguem os AFNDs. Para convertermos esse AFND (ou outro qualquer), a grande pergunta que precisaremos responder ser: como fazer os conjuntos de estados, presentes na tabela do AFND, aparecerem como um nico estado no AFD? Por exemplo, no AFND acima, se estiver em q0 e ler 0, ele vai para dois estados: q0 e q1. Em um AFD, ele teria que ir para um s estado, mas qual? Bem, a ideia da converso de AFND para AFD ser usar um conjunto de estados do AFND como sendo um nico estado para o AFD. Por exemplo, {q0, q1} so dois estados do AFND, mas ser tratado como sendo um s estado para o AFD. Sim, sabemos que isso confunde um pouco no incio, mas pense como se {q0, q1} fosse apenas um nome de um estado. Um nome estranho, em relao aos que vnhamos usando, mas lembre-se de que os nomes dos estados no fazem diferena nos autmatos. No AFD, um estado com nome {q0, q1} representaria a situao em que o AFND estaria, ao mesmo, nesses dois estados (e no estaria em nenhum outro mais). Ento, com esse artifcio, conseguimos responder a grande pergunta levantada antes sobre como trocar um conjunto de estados por estados individuais. Se voc entendeu esse ponto da explicao, o restante ser mais simples. Se no entendeu, releia ou busque ajuda no ambiente, que existe exatamente para ajudar voc! Como ponto de incio da converso para um AFD, precisamos definir qual ser o estado inicial. Bem, veja que o AFND comea 47

Teoria da Computao

em um estado s. O seu incio nunca comea bifurcado em vrias opes. Por isso, o estado inicial do AFD ser um conjunto que tem apenas o estado inicial do AFND. No caso do autmato N2, ele ser o estado {q0}. A partir desse estado, construiremos as transies e descobriremos outros estados importantes para o novo autmato. Por enquanto a tabela com as transies do AFD seria apenas essa: {q0} 0 1

Bem, para completarmos as transies nessa tabela, bastar olhar as transies de q0 em N2. Esse um caso simples, porque o estado {q0} tem apenas um estado do AFND. O resultado, por enquanto, seria essa tabela: {q0} 0 {q0, q1} 1 {q0}

Agora, veja que, nas clulas da tabela, apareceu o conjunto {q0, q1}. Este conjunto representa um novo estado e dever ser representado por uma nova linha da tabela: {q0} {q0, q1} 0 {q0, q1} 1 {q0}

Agora, devemos completar as transies para {q0, q1}, que no um caso to simples quanto o primeiro porque agora temos dois estados. Voc vai se questionar: estando no estado {q0, q1}, que representa q0 e q1 ao mesmo tempo, e lendo o caractere 0, quais os caminhos seguidos pelo autmato? A partir de q0, lendo 0, acessamos o conjunto de estados {q0, q1} e a partir de q1 acessamos , ento tomamos a unio desses dois resultados {q0, q1} = {q0, q1}. Com isso, preenchemos a primeira clula vazia: {q0} {q0, q1} 0 {q0, q1} {q0, q1} 1 {q0}

48

Teoria da Computao

Para preencher a prxima clula, devemos analisar o que acontece estando em {q0, q1} e lendo 1. Por meio de q0, acessamos {q0} e, por meio de q1, acessamos {q2}. Logo, o resultado ser a unio {q0} {q2} = {q0, q2}. Temos ento a nova linha preenchida: {q0} {q0, q1} 0 {q0, q1} {q0, q1} 1 {q0} {q0, q2}

Essa ser a regra geral para descobrir as transies de um conjunto de estados {e1, e2, ..., en}: para cada smbolo x, fazemos a transio de e1, depois de e2, depois de ..., depois de en. Por fim, fazemos a unio entre todos os conjuntos resultantes. Essa unio ser, ento, tratada como um novo estado do AFD que estamos criando. Bem, continuando a explicao da converso do autmato N2, veja que aparece um novo conjunto na tabela: {q0, q2}. Precisamos saber o comportamento do autmato neste estado, ento criamos uma nova linha para ele: {q0} {q0, q1} {q0, q2} 0 {q0, q1} {q0, q1} 1 {q0} {q0, q2}

Vamos agora descobrir as transies para {q0, q2}. Em q0, lendo 0, o autmato vai para {q0, q1} e q2 lendo o mesmo smbolo vai para . O resultado ser {q0, q1} = {q0, q1}. Agora, q0 lendo 1 continua

em q0, enquanto q2 lendo 1 vai para , logo obtemos o resultado {q0} = {q0}. A tabela, portanto, fica assim: {q0} {q0, q1} {q0, q2} 0 {q0, q1} {q0, q1} {q0, q1} 1 {q0} {q0, q2} {q0}

E agora, o que fazer? Surgiu algum estado (conjunto) novo? A resposta : no. Ento, a construo da tabela se encerrou. O que 49

Teoria da Computao

falta agora definir quem so os estados de aceitao. Para isso, olhe os estados de aceitao do AFND. Veja que, no caso do exemplo N2, tem apenas um estado de aceitao: q2. Lembre-se tambm que, se um AFND termina em um conjunto de estados, basta um deles ser estado de aceitao para aceitar uma cadeia. Por isso, na converso, bastar um conjunto conter q2 para que ele seja considerando um estado de aceitao. No caso, o nico estado de aceitao do exemplo {q0, q2}. Para simplificar as respostas dos exerccios, voc no precisar dar o restante da representao formal do AFD que acabou de construir. Bastar adicionar duas informaes na tabela: qual o estado inicial e quais so os estados de aceitao. Para indicar qual o estado inicial, coloque uma seta na linha que o representa (que dever ser a primeira linha da tabela, se voc fez da maneira que ensinamos aqui). J nos estados de aceitao, coloque com um asterisco ao lado dele na tabela. A tabela resultante do AFD seria essa: {q0} {q0, q1} * {q0, q2} 0 {q0, q1} {q0, q1} {q0, q1} 1 {q0} {q0, q2} {q0}

Como a representao grfica de um autmato costuma ser mais agradvel e fcil de entender, voc tambm dever constru-la. Isso pode ser feito com facilidade a partir da tabela das transies. Voc s precisar lembrar daquele detalhe importantssimo dito no comeo: que os conjuntos sero apenas nomes de estados individuais. No caso da tabela acima, o resultado seria essa representao grfica do AFD:

Voc, agora, pode fazer alguns testes e verificar que este autmato 50

Teoria da Computao

realmente equivalente ao autmato N2 que mostramos antes. Teste e confirme que ambos aceitam as cadeias: 01, 001, 0101, etc. Tambm examine ambos para confirmar que eles rejeitam as cadeias: e, 1, 00, 110, 010, 011, etc. O fato de que ambos aceitam as mesmas cadeias e rejeitam as mesmas cadeias faz com que sejam equivalentes. Porm, perceba a diferena entre eles: no AFND, voc no tem um caminho bem claro, bem determinado a ser seguido voc ter que testar vrios caminhos. Por isso, esse autmato recebe esse nome de no-determinstico: porque ele pode escolher entre vrias aes num mesmo instante. J no AFD, o caminho a ser seguido ser sempre bem definido. Ele vai seguir sempre para um estado por vez e vai parar em um s estado tudo muito bem determinado. Por isso, esse autmato recebeu o nome de determinstico: porque ele s vai ter uma ao para escolher a cada instante. Qual a vantagem ento de se trabalhar com AFNDs? Em alguns casos, ser mais fcil construir um AFND do que um AFD. Pode acontecer do AFND ter menos transies e menos estados do que o AFD equivalente, facilitando a vida de quem o constri. Porm, depois de construdo o AFND, vale a pena convert-lo para um AFD usando a tcnica que mostramos aqui. Para encerrar, lembramos a voc, leitor, que essa seo mostrou que (mesmo funcionando de maneiras diferentes) AFD e AFND so dois modelos equivalentes, ou seja, toda linguagem que um deles pode representar o outro tambm pode representar. Isso foi provado ao mostrarmos como converter um autmato de um tipo para o outro tipo. Na seo a seguir, veremos que existe um terceiro tipo de autmato, que tambm equivalente aos dois que j vimos.

3.4 Um novo tipo de transio ()E se pudssemos mudar de estado sem precisar ler nenhum smbolo? Voc no leu errado, h uma maneira de, no momento que o autmato chega em um estado, ele passar imediatamente para outros estados sem ter lido mais nenhum smbolo. Podemos fazer este tipo de transio com o uso de um identificador especial: a letra grega e (psilon). Um autmato com essa propriedade chamado de AFND com e-transies ou e-AFND.

51

Teoria da Computao

AtenoLembre-se que j usamos para representar a cadeia vazia, ou seja, a cadeia sem smbolos. Agora, vamos us-lo para representar uma transio que no l smbolo. Em todo caso, est representando a ausncia total de smbolos.

Essas transies sero transies espontneas no autmato, que o autmato pode fazer ou no, independente da cadeia que ele recebeu de entrada. Vamos analisar um e-AFND e entender seu funcionamento. Suponha um autmato que reconhece a soma de um inteiro positivo ou negativo com um decimal positivo.

Vamos acompanhar agora o funcionamento deste autmato com a expresso -12+2.6. Comeamos com estado q0: o nmero pode ser iniciado por +, -, ou nenhum caractere.

Note que, inicialmente, o autmato j est nos estados q0 e q1 ao mesmo tempo por causa da transio e entre esses estados. A transio espontnea faz com que o autmato avance nas transies mesmo sem ter lido qualquer caractere da cadeia. Comeamos a ler ento o primeiro smbolo (-). Seguindo o caminho de q0 lendo menos (-) faz o autmato passar para o estado q1, mas de q1, que o segundo caminho, no h transio ento este percurso abandonado. Os prximos so lidos e o autmato se comporta como um simples AFD lendo 12+ e obtemos o seguinte resultado:

52

Teoria da Computao

Estando em q3 o autmato l o prximo caractere dois (2) e imediatamente o autmato vai para o estado q4 mas tratamos aqui de um autmato com e transies. O e mais direita indica que chegando ao estado q4 imediatamente o autmato passa tambm para o estado q6, e por se tratar de um estado de aceitao se a cadeia terminasse neste momento seria aceita. Vejamos como fica a descrio dos caminhos do autmato at o momento:

Lembre-se que o autmato est no estado q4 e q6. Lendo o prximo caractere (.), o caminho de q6 abandonado, enquanto, no outro caminho, seguimos de q4 para o estado q5, como mostrado a seguir:

53

Teoria da Computao

Nosso prximo passo acompanhar o ponto (.) que faz o autmato paralisar o caminho atual de q6 e ir para q5 pelo caminho de q4. Em seguida o autmato l o seis (6) e vai para q6, e como estado de aceitao e terminamos de ler a cadeia aceitamos a cadeia. Tente repetir o funcionamento do autmato com esse nmero e crie novos nmeros para observar o comportamento do autmato com o uso das transies e.

Um detalhe importante do modelo e-AFND que ele equivalente tanto ao modelo AFD quanto ao modelo AFND (sem transio e). Porm, desta vez, no mostraremos como poderamos converter de um modelo para outro. Apenas saiba que possvel converter. Mais informaes voc pode encontrar na bibliografia.

Aprenda Praticando Nesta seo, mostraremos passo-a-passo como resolver, na prtica, os problemas aprendidos nas sees anteriores. Atente aos exerccios e se possvel resolva-os novamente sem a ajuda da apostila. essencial que voc s avance aos exerccios seguintes quando entender os resolvidos. Lembre-se que voc tem ajuda dos seus colegas de turma, tutores, professores, livros entre outros para esclarecer suas dvidas. 1. Crie o autmato finito no-determinstico que reconhea a seguinte linguagem: o conjunto de todas as cadeias sobre {0,1} que tenham 01 como subcadeia. 54

Teoria da Computao

Resposta: Primeiro, temos que criar um autmato que reconhea a cadeia 01. Obtido facilmente e mostrado abaixo:

S precisamos verificar as condies: a subcadeia pode estar aps a leitura de alguns caracteres, logo precisamos adicionar transies iniciais. Tambm 01 pode estar antes do final da cadeia por isso precisamos adicionar transies no final. Uma vez lido 01 o autmato no sai mais do estado de aceitao. Temos como resultado:

Agora s precisamos descrev-lo de maneira formal: M = ({q0, q1, q2}, {0,1}, , {q2}), onde: q0 q1 * q2 0 {q0,q1} {q2} 1 {q0} {q2} {q2}

2. Mostre os conjuntos de estados pelos quais o autmato passa quando recebe a cadeia 10010. No final, diga se a cadeia aceita ou no e justifique.

Resposta: Comeamos pelo estado q0. Depois de ler o smbolo 55

Teoria da Computao

1, o autmato vai permanecer em q0. Agora, em q0, quando l o prximo smbolo, que 0, o autmato pode ir para dois estados: {q1, q2}. Podemos representar esse incio assim: {q0} l 1 {q0} l 0 {q1, q2} ... Agora o autmato est em dois estados, ento deveremos acompanhar o que acontece nos dois caminhos ao ler o prximo smbolo da cadeia, que 0. Se estiver em q1 e ler um 0, vai {q2}; se estiver em q2, ao ler o 0, no tem opo, ou seja d o conjunto vazio. O resultado que o autmato poder estar apenas no conjunto {q2}. {q0} l 1 {q0} l 0 {q1, q2} l 0 {q2} ... Ainda falta ler o trecho 10 da cadeia. Ao ler 1 em q2, o resultado {q0}, completando mais um passo. Agora, lendo o ltimo smbolo, que 0, a partir de q0, o resultado {q1, q2}, como vimos antes. Assim, os conjuntos obtidos ao ler cada smbolo da cadeia 10010 sero: {q0} l 1 {q0} l 0 {q1, q2} l 0 {q2} l 1 {q0} l 0 {q0, q2} Note que ao ler 10010, terminamos nos estados q0 e q2 ao mesmo tempo. A cadeia ser aceita e a justificativa para isso que terminamos de ler a cadeia e um dos estados atingidos um estado de aceitao (o estado q2).

Atividades e Orientaes de Estudo Voc encontrar nesta seo uma relao de exerccios importantes. interessante que voc se esforce ao mximo para tentar resolver e entender cada questo desta. Resolv-los pode ser comparado a um exerccio de matemtica ou de programao: no existe um mtodo pr-definido cada um pode ver o problema de uma maneira e obter respostas diferentes. importante comparar com as respostas de outros colegas e tentar encontrar falhas nos autmatos uns dos outros. um timo exerccio para exercitar a mente na resoluo de problemas. Nunca esquea do apoio dos tutores no seu aprendizado, pois 56

Teoria da Computao

eles esto sempre prontos para tirar suas dvidas e lhe orientar nos exerccios. 1. Construa os AFND que reconheam as seguintes linguagens sobre o alfabeto {0,1}: a) O conjunto de cadeias que comeam por 0 e terminam com 1. b) O conjunto de cadeias que terminam com 00 c) O conjunto de cadeias que tm 01 como subcadeia. 2. Mostre um AFND que aceita o conjunto de cadeias sobre o alfabeto {0, 1, ..., 9} tal que o dgito final j tenha aparecido antes na palavra. 3. Mostre um AFND que aceita o conjunto de cadeias sobre o alfabeto {0, 1, ..., 9} tal que o dgito final no tenha aparecido antes na palavra. 4. Fornea um AFND que aceite o conjunto de cadeias sobre o alfabeto {0, 1} tais que no existam dois 0s separados por mais de trs 1s. 5. Converta o autmato no-determinstico N1 visto antes para um autmato determinstico equivalente.

Saiba Mais Muitas vezes precisamos estudar um mesmo assunto por diversos ngulos e de maneiras diferentes. Citamos abaixo alguns caminhos para voc estudar o assunto com linguagens e notaes diferentes ou at mesmo com a mesma. Sua pesquisa importante principalmente se voc no est completamente habituado com o assunto. Internet:http://www.ic.uff.br/%7Ecbraga/tc/2005.1

-

Curso

de

teoria

da

computao. 57

Teoria da Computao

http://www.inf.puc-rio.br/%7Einf1626

- Notas de aula de teoria da Curso com vrios

computao.http://www.deamo.prof.ufu.br/CursoLFA.html

exerccios resolvidos.http://homepages.dcc.ufmg.br/~nvieira/index.html

- Notas de teoria de

vrios anos.

Resumo Vimos neste volume nosso primeiro modelo matemtico de mquinas. Os autmatos finitos so simples e por isso no apresentam um grande poder computacional comparando com os modelos que veremos adiante. O principal modelo para descrever um autmato finito como uma funo: A = (Q, , , s0, F), onde: Q o conjunto finito de estados. o alfabeto de entrada. a funo de transio. s0 Q o estado inicial. F Q; os elementos de F so os estados finais ou estados de aceitao. Existem dois tipos de autmatos: AFD e AFND: Os primeiros s podem estar em um estado ao mesmo tempo e normalmente todas as suas transies so preenchidas. Um AFND pode estar em mais de um estado ao mesmo tempo ou mesmo em transio para nenhum estado. Embora os AFNDs tenham essa peculiaridade ambos modelos apresentam o mesmo poder computacional, ou seja, o problema que pode ser resolvido por um AFND pode ser tambm por um AFD e vice-versa.

58

Teoria da Computao

Referncias

Leitura Adicional: HOPCROFT, John E.; MOTwANI, Rajeev.; ULLMAN, Jeffrey D. Introduo Teoria de Autmatos, Linguagens e Computao. Editora Campus, 2002. LEwIS, Harry R.; PAPADIMITRIOU, Christos H. Elementos de Teoria da Computao, Bookman, 2 edio. MENEZES, Paulo Blauth. Linguagens Formais e Autmatos. Editora Sagra Luzzatto, 2000. SIPSER, Michael. Introduo a Teoria da Computao. Editora Thomson Pioneira, 2007.

59

Teoria da Computao

Consideraes FinaisVimos, neste volume, o conceito de linguagem formal como um conjunto de cadeias. Uma linguagem formal costuma ser formada por cadeias com uma propriedade especfica, ento podemos tratar uma linguagem como o problema de testar essa tal propriedade (exemplo: testar se termina em 11). Para representar matematicamente como resolver algum problema desse tipo de modo a representar a linguagem formal, vimos que existem os modelos computacionais. At agora, dois modelos foram apresentados: o AFD e o AFND. Ambos so equivalentes e sero chamados pelo nome geral de autmatos finitos. No segundo volume, comearemos vendo mais um modelo equivalente aos autmatos finitos, mas que funciona de maneira muito diferente deles. Em todo caso, ainda estaremos lidando com linguagens muito simples. Porm, no restante do segundo volume veremos dois modelos capazes de representar linguagens mais complexas, que os autmatos finitos no conseguem representar. Assim, continuaremos caminhando para conhecer o modelo mais poderoso de todos, que s ser conhecido no terceiro volume.

60