Autómatos finitos II

15 fevereiro 2011, 10:00 • José Félix Costa

Demonstração do lema de pumping. Versões fraca [(a) e (b)] e forte do teorema [(a), (b) e (c)].

Exemplos de aplicação.

Teorema: A classe das linguagens regulares está fechada para a complementação, união e intersecção (fecho booleano).

Exemplos de aplicação.

NOTA: Devem tomar nota do seguinte: Esta teoria de autómatos e linguagens vai adiante ser utilizada para (1) resolver o problema das excepções e (2) caracterizar a classe LINEARSPACE.

Autómatos finitos I

14 fevereiro 2011, 10:00 • José Félix Costa

Alfabeto, palavra, linguagem.

Definição de autómato finito determinístico. Definição de aceitação de palavra por autómato finito determinístico.

Conceito de linguagem regular.

Exemplos.

Lema de pumping: Se A é uma linguagem regular, então existe um número 'p' (comprimento de pumping) tal que, se 's' é uma palavra de A de comprimento igual ou superior a 'p', então 's' pode ser decomposta em três subpalavras, s = xyz, que satisfazem as seguintes condições: (a) para todo o i>=0, x y^i z \in A, (b) |y| > 0 e (c) |xy| <= p.

Exemplos de aplicação do lema.

NOTA : Para a revisão de matérias, recomenda-se o livro de Michael Sipser. Introduction to the Theory of Computation, Thomson, Course Technology, Second Edition, International Edition, 2006.