Turmas - 1º Semestre de 2015
Turmas
1º Semestre de 2015

Dada a expressão regular a*(a + b)b*:

1. Construa, usando o algoritmo de Thompson, o autômato finito não-determinístico com movimentos vazios para reconhecer sentenças dessa linguagem.
2. Converta, usando o método da construção de subconjuntos, o autômato do item a para um autômato finito determinístico.
3. Minimize, se possível, o número de estados do autômato do item b.

Considere a expressão regular c*a(a+b+c)*b(a+b+c)*c*

Assinale a alternativa que descreva, corretamente, todas as cadeias geradas por essa expressão regular:

1. Cadeias sobre o alfabeto {a, b, c} onde o primeiro a precede o primeiro b.
2. Cadeias sobre o alfabeto {a, b, c} onde um número par de a's.
3. Cadeias sobre o alfabeto {a, b, c} contendo a substring baa.
4. Cadeias sobre o alfabeto {a, b, c} contendo um número ímpar de c's.
5. Cadeias sobre o alfabeto {a, b, c} terminadas por c.