CAPÍTULO 2 AUTÓMATOS FINITOS - Universidade da cbarrico/Disciplinas/TeoriaComputacao/Downloads/2... · Teoria da Computação Capítulo 2 . Autómatos Finitos

  • View
    214

  • Download
    0

Embed Size (px)

Text of CAPÍTULO 2 AUTÓMATOS FINITOS - Universidade da ...

  • Teoria da Computao Captulo 2 . Autmatos Finitos

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

    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

  • Teoria da Computao Captulo 2 . Autmatos Finitos

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

  • Teoria da Computao Captulo 2 . Autmatos Finitos

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

    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 = { anb

    m | n,m >= 0 }a que pertencem as cadeias : ,aabbbbb, aaaa,

    bbbb, ou a linguagem L2 = { anb

    n| 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.

  • Teoria da Computao Captulo 2 . Autmatos Finitos

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

    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 GGeram as cadeias de L

    AutmatosReconhecem as cadeias

    de L

  • Teoria da Computao Captulo 2 . Autmatos Finitos

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

    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 q1q2

    0

    1

    10

    0

    1

    Incio

  • Teoria da Computao Captulo 2 . Autmatos Finitos

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

    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 q1q2

    0

    1

    10

    0,1

    Incio

  • Teoria da Computao Captulo 2 . Autmatos Finitos

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

    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 pa