Autómatos Finitos

No capítulo anterior definiram-se as linguagens e expressões regulares com vista a resolver o Problema Principal de ALP (versão 1) – Determinar um sistema computável, eficiente e adequado para definir linguagens de programação. – onde:

  1. Computável: Existe um algoritmo que recebe como entrada uma palavra e ao fim de um número finito de passos produz uma resposta sim ou não conforme ou não.
  2. Eficiente: O número de passos referido no passo anterior não deve ser "muito maior" que o comprimento da palavra.
  3. Adequado: Deve ser possível definir (os programas de) qualquer linguagem de programação.

As linguagens regulares são uma classe de linguagens formais. Será que resolvem o Problema Principal de ALP? É necessário esclarecer:

  • Como definir um algoritmo, Super, que dada uma ER e produza um programa PL = Super(e) tal que, para cada palavra p, o resultado PL(p) é sim ou não conforme p in L(e) ou não?
  • Se as computações Super(e) e PL(p) são eficientes?
  • Se as linguagens regulares são adequadas para definir (os programs de) qualquer linguagem de programação?

O programa Super tem como entrada uma ER e, que especifica uma certa linguagem regular, e devolve um programa PL, que reconhece as palavras da linguagem definida por e.

Isto é semelhante ao trabalho de um compilador. Por exemplo, javac é um programa que tem como entrada ficheiros que especificam um certo programa e devolve esse programa em bytecode.