Computabilidade e Linguagens Formais

Introdução à teoria dos autómatos
Notas baseadas em John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman.
“Introduction to automata theory, languages and computation”. 2nd ed, AddisonWesley, 2001.
–
Gabriel David / Cristina Ribeiro
1
História


Teoria dos autómatos: estudo dos dispositivos computacionais
abstractos [máquinas]
Alan Turing (1930’s)
–
–

1940’s, 1950’s
–

Estudos em autómatos finitos para modelar o cérebro
Noam Chomsky (1950’s)
–

Estudou os limites de uma máquina abstracta equivalente às máquinas
actuais
Antes de haver computadores!
Gramáticas formais - relacionadas com autómatos abstractos; úteis em
compilação
S. Cook (1969)
–
Teoria da complexidade – o que é possível ou não computar
Introdução-2
Interesse da teoria dos autómatos

Útil na modelação de hardware e software
–
–
–
–

Projecto e teste de circuitos digitais
Análise lexical em compilação
Processamento de texto, pesquisa na Web
Máquinas de estados, protocolos de comunicação, criptografia
Autómato finito
–
–
–
–
Sistema que em cada momento está num de um nº finito de estados
Estado memoriza a porção relevante da história do sistema
Sendo finito tem que esquecer o que não for relevante
Pode ser implementado com recursos fixos
Introdução-3
Interruptor on/off
Press
Start
on
off
Press

Autómato finito mais simples – modela interruptor
–
–
Dois estados [círculos]: on e off
Uma só entrada [etiquetas nos arcos]: Press


–
–
Representa influência externa no sistema [transição de estado]
Carregar no botão tem um efeito dependente do estado
Estado inicial indicado por uma seta com a etiqueta Start
Pode existir um (ou mais) estados finais ou de aceitação, indicados
por círculo de linha dupla

Chegar a um desses estados significa que a sequência de entradas é boa
Introdução-4
Reconhecedor
Start

t
t
h
th
e
the
n
then
Se a entrada for a cadeia t-h-e-n o autómato evolui do estado
inicial para o final
–
–
Acumula a história das entradas
O seu objectivo é reconhecer a palavra “then”
Introdução-5
Representações estruturais

Gramáticas
–
–
Processar dados com estrutura recursiva [expressões]
Exemplo de regra gramatical: E  E + E

–

Uma expressão pode ser constituída por duas expressões ligadas por “+”
Usadas em analisadores [parsers] de compiladores
Expressões regulares
–
–
Descreve a estrutura de cadeias de caracteres
Exemplo: [1-9][0-9][0-9][0-9][-][0-9][0-9][0-9][ ][A-Z][a-z]*


Descreve “4200-465 Porto” mas falha “5505-032 Vila Real”
Correcção: [1-9][0-9][0-9][0-9][-][0-9][0-9][0-9]([ ][A-Z][a-z]*)*
Introdução-6
Conceitos centrais

Alfabeto é um conjunto finito e não vazio de símbolos
–
–
–

 = {0, 1} , alfabeto binário
 = {a, b, …, z} , conjunto das minúsculas
Conjunto dos caracteres ASCII
Cadeia (ou palavra) é uma sequência finita de símbolos escolhidos de
um alfabeto
–
–
–
–
01101 é uma cadeia do alfabeto  = {0, 1}
Cadeia vazia () tem zero ocorrências de símbolos
Comprimento de uma cadeia é o número de ocorrências de símbolos:
|01101| = 5, || = 0
Potência de um alfabeto k é o conjunto de cadeias de comprimento k,
formadas por símbolos do alfabeto  (produto cartesiano)



0 = {}
Se  = {0, 1} então 1 = {0, 1} , 2 = {00, 01, 10, 11}, 3 = {000, 001, …, 111}
Distinção entre  = {0, 1} conjunto de símbolos e 1 = {0, 1} conjunto de cadeias
Introdução-7
Linguagem

O conjunto de todas as cadeias sobre um alfabeto  é denotada por *
–
–
–

* = 0  1  2  …
+ = 1  2  …
* = 0  +
Linguagem L sobre um alfabeto  é um subconjunto de * (L  *)
–
Linguagem das cadeias com n 0’s seguidos de n 1’s

–
Conjunto dos números binários que são primos

–
{10, 11, 101, 111, 1011, …}
Linguagem vazia

–
{, 01, 0011, 000111, …}

Linguagem só com a cadeia vazia

{}
Introdução-8
Problema

Problema é a questão de decidir se, dada uma cadeia, ela é
membro de uma determinada linguagem
–

Dados w  * e L  *, w  L ?
É comum descrever uma linguagem através de um
construtor de conjuntos
–
{w | w consiste de um número igual de 0’s e 1’s}

–

Conjunto dos w tal que w…
{w | w é um programa em C sintacticamente correcto}
Problema de testar a primalidade
–
w  Lp ? em que w é uma cadeia com a representação binária de
um número e Lp é a linguagem que contém todas as cadeias que são
representações binárias de números primos
Introdução-9
Linguagem ou problema?

Problema em sentido comum
–
–

Pedido para calcular ou transformar uma entrada (ex: compilador)
Não uma questão de decisão (sim/não)
Para efeitos de estudos de complexidade, definir um problema em
termos de uma linguagem é adequado
–
–
É tão difícil resolver a questão da decisão como a do problema
Se for difícil decidir se uma cadeia pertence à linguagem LX das cadeias
válidas na linguagem de programação X então não é mais fácil traduzir
programas na linguagem X para código objecto



Se fosse, executava-se o tradutor e decidia-se da pertença a LX conforme o sucesso
do tradutor em produzir código objecto. O problema da decisão ficava fácil, o que
contradiz a suposição (prova por contradição)
Exemplo de redução de um problema a outro
Linguagens e problemas são a mesma coisa
–
Cadeias enquanto tal – linguagem;
objectos representados – problema
Introdução-10