P03-T3 Terceira aula prática (Turma 3)

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

Autómatos não determinísticos e conversão em determinísticos: autómato de alfabeto {a,b,c} das palavras que terminam em bc, autómato de alfabeto {0,1} das palavras com um 1 na penúltima posição; autómato das palavras de alfabeto {a,b,c} das palavras com zero ou mais as seguidos de zero ou mais bs seguido de zero ou mais cs.

Lema de «pumping» II

8 outubro 2012, 09:30 • 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.

P03-T4 Terceira aula prática (Turma 4)

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

Autómatos não determinísticos e conversão em determinísticos: autómato de alfabeto {a,b,c} das palavras que terminam em bc, autómato de alfabeto {0,1} das palavras com um 1 na penúltima posição; autómato das palavras de alfabeto {a,b,c} das palavras com zero ou mais as seguidos de zero ou mais bs seguido de zero ou mais cs.

TURMA 106: Autómatos finitos II

4 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.)

P03-T1 Terceira aula prática (Turma 1)

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

Autómatos não determinísticos e conversão em determinísticos: autómato de alfabeto {a,b,c} das palavras que terminam em bc, autómato de alfabeto {0.1} das palavras com um 1 na penúltima posição; autómato das palavras de alfabeto {a,b,c} das palavras com zero ou mais as seguidos de zero ou mais bs seguido de zero ou mais cs.