Multiplicação de matrizes

Teoria da Computação

Capítulo 2 . Autómatos Finitos

CAPÍTULO 2
AUTÓMATOS FINITOS

2.1. Introdução

45

2.2.Aceitadores determinísticos

46

2.3. A arte de construir DFA’s

59

2.4. Linguagens regulares

75

2.5. Autómatos finitos não-determinísticos (DFAs)

83

2.6 Equivalência entre DFA’s e NFAs

85

2.7. Redução do número de estados em Autómatos Finitos

97

2.8 Aplicação dos DFAs na busca de texto

105

2.9 Autómatos transdutores

107

Máquinas de Mealy

108

Máquinas de More

109

Bibliogafia

112

Apêndice: Software de autómatos finitos

112

JFLAP
Deus ex-máquina

LEI/DEI/FCTUC/2009/@ADC

Documento de trabalho

43

Teoria da Computação

LEI/DEI/FCTUC/2009/@ADC

Capítulo 2 . Autómatos Finitos

Documento de trabalho

44

Teoria da Computação

Capítulo 2 . Autómatos Finitos

2.1. Introdução
No Cap.1 estudámos as noções básicas de linguagens, gramáticas e autómatos. Podem-se definir muitas linguagens a partir de um mesmo alfabeto, conforma as regras particulares de combinação dos caracteres do alfabeto.
Por exemplo a partir do alfabeto

= {a, b} e usando a notação 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 a’s e b’s ,incluindo
.. Quantas linguagens se podem definir com este alfabeto ?
As linguagens podem ser definidas por uma gramática, que indica como se formam as cadeias de caracteres. Conhecidas as suas produções é fácil derivar cadeias da linguagem.
Pode-se agora pôr o problema ao contrário: dada uma cadeia de caracteres, como saber se pertence a uma dada linguagem ? Se a cadeia for pequena pode ser relativamente simples, por inspecção visual, decidir se pertence ou não. Mas para uma cadeia grande de um gramática mais elaborada, não é