FenixEdu™

11 outubro 2012, 08:00 • Francisco Miguel Alves Campos de Sousa Dionísio

Lema da bombagem: motivação e aplicação a linguagens não regulares: {0^n 1^n, n>=0}, {0^i 1^j, j>=i>=0},{0^i 1^j, i>j>=0} e {wwR, w \in {0,1}*}.

10 outubro 2012, 11:00 • José Félix Costa

Conclusão.

Exercício: Mostre que a linguagem das palavras binárias que se escrevem com número desigual de 0's e 1's não é regular.

SIMULADORES DE AUTÓMATOS

http://www.cs.usfca.edu/~jbovet/vas.html

10 outubro 2012, 09:30 • José Félix Costa

Conclusão.

Exercício: Mostre que a linguagem das palavras binárias que se escrevem com número desigual de 0's e 1's não é regular.

SIMULADORES DE AUTÓMATOS

http://www.cs.usfca.edu/~jbovet/vas.html

9 outubro 2012, 09:30 • José Félix Costa

Conversão canónica de autómatos não determinísticos em autómatos determinísticos. (Resolveram-se os exercícios dos testes dos passados anos.)

8 outubro 2012, 11:00 • José Félix Costa

Exemplificação do uso do lema de "pumping":

Exercício: Mostre que a linguagem L = {0^n 1^n: n in N} (= {\epsilon, 01, 0011, 000111, 00001111, ...}) não é regular.

Exercício: Mostre que a linguagem L = {w in {0,1}*: em w há igual número de 0's e de 1's} não é regular.

Exercício: Mostre que a linguagem L = {w in {0,1}*: w é palíndromo e |w| é par} não é regular.

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Exercícios

Exercício: Mostre que a linguagem L = {ww: w é palavra binária} não é regular.

Exercício: Mostre que a linguagem L = {0^m 1^n: m > n} não é regular.

Exercício: Mostre que a linguagem L = {w in {0,1}*: w é palíndromo} não é regular.

Exercício: Mostre que a linguagem L = {1^n^2: n in N} = {1, 1111, 111111111, 1111111111111111, ...} não é regular.

Exercício: Mostre que a linguagem L = {w in {0,1}*: w não é palíndromo} não é regular.

Teoria da Computação