1a. Lista de Exercícios (com
exercícios do
Sipser) - obrigatória para entrega em 24/04/12
Faça quatro das seguintes questões
1.5.4- Mostre, com argumentos lógicos, que se A e B
são conjuntos finitos quaisquer, então existem |B|
|A|
funções com domínio em A e
contradomínio em
B.
1.5.6- Mostre que em qualquer grupo de no mínimo duas
pessoas, há pelo menos duas que têm o mesmo
número
de conhecidos dentro do grupo, considerando que a
relação
"conhecido de" é simétrica (use o princípio
da
correspondência).
1.5.9- Um conjunto enumerável é um conjunto
que
pode ser domínio ou contradomínio de uma
bijeção com os números naturais. Mostre o
seguinte: Se soubermos que A é um conjunto
não-enumerável, e B um subconjunto enumerável
de
A, então A - B (isto é, A sem os elementos de B)
é
também não-enumerável. (Sugestão: use
argumento por contradição)
1.6.2- O fecho transtitivo de uma relação R
sobre A
é a menor relação transtiva sobre A que
contém R (tomando a definição de
relação como subconjunto de um produto direto,
"menor"
significa minimal, isto é, qualquer subconjunto
próprio
dele deixa de satisfazer a propriedade que o define).
Se A = {a, b, c, d, e} e R = {(a,b), (a,c), (a,d) ,
(d,c),
(c,e)}, descreva o fecho transitivo reflexivo R* (Se voce
não se
lembra como "completar" uma relação para obter o
fecho,
consulte um livro; se quiser, represente R* por um grafo dirigido,
onde
a aresta dirigida a->b representa (a,b) )
1.6.5- Dê um exemplo de uma relação
sobre um
conjunto que não é reflexiva, mas seu fecho
transitivo
é reflexivo.
2. *- Explique, usando argumentos lógicos e o lema do
bombeamento, por que a linguagem L = {0
n1
n |
n
é número
natural } não é regular, ou seja, não pode
ser
aceita por um automaton finito.
2a. Lista de Exercícios -
cap. 2 - para antes da 1a. prova -
opcional
Responda por completo os ítens da questão
2.4.8 do livro texto H.U.
2.4.8- As seguintes declarações são
verdadeiras ou
falsas? Explique sua resposta em cada caso (Para todas elas,
é
assumido um alfabeto S fixo).
a) Cada subconjunto de uma
linguagem regular é regular;
b) Cada linguagem regular tem um subconjunto próprio (com
pelo menos um elemento a menos) regular;
c) Se L é regular, então assim também
é {xy tal que x pertence a L e y não pertence a
L};
d) A linguagem {w tal que w = wR } é
regular;
e) Se L é uma linguagem regular, assim também
é a linguagem {w pertencente a L tal que wR
também pertence a L}
f) Se C é um conjunto qualquer de linguagens regulares,
então também é o conjunto formado pela
união dessas linguagens
g) {wxwR onde x e w pertencem a S*} é
regular.
3a. Lista de Exercícios -
cap. 3 - para antes da 1a. prova -
opcional
Responda os seguintes itens dos seguintes problemas do livro texto
3.5.1- Mostrar que as seguintes linguagens são
livres de contexto.
a) {a
mb
n
onde m e n são números naturais distintos}.
b) {a,b}
* - {a
nb
n
onde n é um número natural};
e) {w
pertencente a {a,b}
* tal que w=w
R
}
3.5.2- Mostrar que as seguintes
linguagens não são livres de contexto.
c) {www
tal que w pertence ao conjunto {a,b}
* }.
d) {w
pertencente a {a,b,c}
* onde w tem números iguais
de
ocorrências de a, b e
c};
4a.
Lista de Exercícios (com matéria do Sipser) para
antes
da 2a. prova -
opcional
Quais modelos computacionais voce conheceu através desta
matéria?
Desses modelos, quais admitem variantes?
Desses modelos, quais admitem mais de uma semântica
(interpretação do funcionamento), quais não?
Dos que admitem mais de uma semântica, como você as
descreveria?
Dos que admitem mais de uma variante, quais variantes alteram o
poder
expressivo do modelo, quais não?
A menos de variantes equivalentes, quais modelos/semânticas
guardam relação de menor, maior, ou igual poder
expressivo, citando exemplos se possível?
Como voce hierarquizaria essas relações, e como voce
descreveria a hipótese que "fecharia" esta hierarquia no
seu
topo?
O que é o "problema da parada", e como vc descreveria sua
importância para a teoria da computação?
O que são classes de complexidade computacional?
Quais dessas classes voce considera mais importantes, e por que?