1) descreva mais formalmente as seguintes linguagens sobre o alfabeto {0,1}: a) o conjunto das palavras com, no mínimo, um 0; b) o conjunto das palavras de tamanho ímpar; c) o conjunto das palavras com tamanho múltiplo de 5; d) o conjunto das palavras com um prefixo de um ou mais 0’s seguido de um sufixo de zero ou mais 1’s; e) o conjunto das palavras que não terminam com 0101. f) o conjunto das palavras de tamanho par que não terminam com 0101 e nem começam com 11. g) o conjunto dos palíndromos que não contenham símbolos consecutivos idênticos; h) o conjunto das palavras de tamanho par cuja primeira metade é idêntica a segunda.

2) que condição os conjuntos a e b devem satisfazer para que a - b = b - a? e para que q u b = a ∩ b?

3) seja a gramática ({a, b},{0,1}, r, a), em que r tem as três regras:

a → bb.

b → 0b1|λ.

dê todas as derivações das seguintes palavras:

a) λ;

b) 01;

c) 0