Sumários
Autómatos finitos IV
28 fevereiro 2011, 10:00 • José Félix Costa
Equivalência de autómatos finitos (determinísticos ou não determinísticos).
Teorema: Para todo o autómato finito não determinístico existe um autómato finito determinístico que lhe é equivalente.
Exercícios.
Discussão dos conceitos de classificação determinística, não determinística e probabilística.
Autómatos e gramáticas I
23 fevereiro 2011, 14:00 • José Félix Costa
Exercícios sobre gramáticas livres de contexto e gramáticas regulares.
Autómatos finitos não determinísticos. Exercícios.
Gramáticas II
22 fevereiro 2011, 10:00 • José Félix Costa
Exercícios sobre gramáticas livres de contexto.
Exercícios sobre o lema de pumping relativo a linguagens livres de contexto.
Demonstração do lema de pumping.
Gramáticas I
21 fevereiro 2011, 10:00 • José Félix Costa
Grámatica livre de contexto: derivação, derivação em zero ou mais passos, árvore de derivação, palavra derivada, palavra gerada. Linguagem gerada por gramática.
Exemplos.
Restrições às regras: conceito de gramática regular.
Exemplos.
Equivalência de formalismos: Uma linguagem é regular se e só se existe uma gramática regular que a gera.
Lema de pumping: Se A é uma linguagem livre de contexto, então existe um número p>0 tal que, se s é uma palavra de A de comprimento maior ou igual a p, então s pode ser decomposta em cinco subpalavras, s = uvxyz, que satisfazem as seguintes condições: (a) para todo o i>=0, u v^i x y^i z in A, (b) |vy|>0 e (c) |vxy|<=p.
Enunciado, explicitação do enunciado. Utilidade do lema de pumping na demonstração de que uma linguagem não é livre de contexto.
Exemplos.
Leituras: (a) gramática generativa, (b) Noam Chomsky, (c) autómatos, (d) reescrita.
Autómatos finitos III
16 fevereiro 2011, 14:00 • José Félix Costa
Representação em linguagem binária de predicados sobre o conjunto dos números naturais. Conjuntos tally.
Exercícios de aplicação do lema de pumping. Exercícios de aplicação conjunta do lema de pumping e do fecho booleano da classe das linguagens regulares.