Lista0 2_LingFormais-PDs[solucao] FTC UFMG LISTA

Prévia do material em texto

Área de Teoria DCC/UFMG Fundamentos de Teoria da Computação 2020/01
SOLUÇÃO DE LISTA DE EXERCÍCIOS
Lista 0 - Parte 2/2
(Conceitos Fundamentais: Linguagens Formais e Problemas de Decisão)
• Material suplementar:
– Conjunto de slides: Aula 0.2 - Linguagens Formais e Problemas de Decisão.
Revisão.
1. Responda formalmente às seguintes perguntas:
(a) O que é um problema de decisão?
Solução do professor: Um problema de decisão é uma pergunta que depende de um número
finito de parâmetros e que, para cada atribuição concreta de valores a todos os parâmetros (ou
seja, para cada instância do problema), possui como resposta SIM ou NÃO.
(b) O que é uma solução para um problema de decisão?
Solução do professor: Uma solução para um problema de decisão é um algoritmo que para
toda instância do problema produz a resposta correta (SIM ou NÃO).
(c) O que significa dizer que um problema é decid́ıvel ou indecid́ıvel?
Solução do professor: Um problema é decid́ıvel se tem solução, ou seja, um algoritmo que
produza uma resposta correta para toda instância do problema.
Um problema é indecid́ıvel se não tem solução, ou seja, se não existe algoritmo que produza uma
resposta para toda instância do problema.
(d) O que é uma linguagem formal?
Solução do professor: Uma linguagem formal é um conjunto de cadeias que podem ser for-
madas com um alfabeto.
Formalmente, dado um alfabeto finito Σ, uma linguagem formal é um subconjunto de Σ∗.
(e) Qual a relação entre um método para decidir se uma cadeia qualquer pertence a uma linguagem
e uma solução para um problema de decisão?
Solução do professor: Qualquer problema de decisão da forma “A resposta para o PD com
parâmetros x é SIM ou NÃO?” é equivalente ao problema de linguagem “A palavra 〈x〉 pertence
à linguagem L?” para uma linguagem L apropriada.
1
Exerćıcios.
2. Sejam as linguagens L1 = {w ∈ {a, b}∗ | 1 ≤ |w| ≤ 10} e L2 = {w ∈ {a, b}∗ | w termina com b}.
Escreva as linguagens abaixo em termos da união, interseção, complemento, diferença e concatenação
das linguagens L1 e L2. O item (a) já está feito como exemplo.
(a) {w ∈ {a, b}∗ | 1 ≤ |w| ≤ 10 ou w termina com b} = L1 ∪ L2
(b) {w ∈ {a, b}∗ | 1 ≤ |w| ≤ 10 e w termina com b}
(c) {w ∈ {a, b}∗ | w não termina com b}
(d) {w ∈ {a, b}∗ | w = � ou |w| > 10}
(e) {w ∈ {a, b}∗ | 1 ≤ |w| ≤ 10 e w não termina com b}
(f) {w ∈ {a, b}∗ | w termina com b e |w| > 10}
(g) {w ∈ {a, b}∗ | 2 ≤ |w| ≤ 20}
(h) {w ∈ {a, b}∗ | |w| ≥ 2 e w termina com b}
(i) {w ∈ {a, b}∗ | |w| ≥ 2 e o último b de w ocorre não antes da posição |w| − 11}
(j) {xb | x ∈ {a, b}∗ e x contém um b}
(k) ∅
(l) L2
Solução do professor:
(a) {w ∈ {a, b}∗ | 1 ≤ |w| ≤ 10 ou w termina com b} = L1 ∪ L2
(b) {w ∈ {a, b}∗ | 1 ≤ |w| ≤ 10 e w termina com b} = L1 ∩ L2
(c) {w ∈ {a, b}∗ | w não termina com b} = L2
(d) {w ∈ {a, b}∗ | w = � ou |w| > 10} = L1
(e) {w ∈ {a, b}∗ | 1 ≤ |w| ≤ 10 e w não termina com b} = L1 − L2
(f) {w ∈ {a, b}∗ | w termina com b e |w| > 10} = L2 − L1
(g) {w ∈ {a, b}∗ | 2 ≤ |w| ≤ 20} = L1L1
(h) L1L2 = {w ∈ {a, b}∗ | |w| ≥ 2 e w termina com b} = L1L2
(i) {w ∈ {a, b}∗ | |w| ≥ 2 e o último b de w ocorre não antes da posição |w| − 11} = L2L1
(j) {xb | x ∈ {a, b}∗ e x contém um b} = L2L2
(k) ∅ = L1∅ = ∅L1 = L2∅ = ∅L2
(l) L2 = {�}L2 = L2 = {�}
3. Dê descrições em linguagem natural das seguinte linguagens. O item (a) já está feito como exemplo.
(a) {0, 1}∗ é o conjunto de todas as cadeias binárias.
(b) {0, 1}+
(c) {0, 11}∗
(d) {�, 01}∗
(e) {�, 01}+
2
Solução do professor:
(a) {0, 1}∗ é o conjunto de todas as cadeias binárias.
(b) {0, 1}+ é o conjunto de todas as cadeias binárias de tamanho pelo menos 1.
(c) {0, 11}∗ é o conjunto de todas as cadeias binárias em que os 1’s sempre aparecem aos pares.
(d) {�, 01}∗ é o conjunto de todas as cadeias formadas apenas pela repetição da subcadeia 01.
(e) {�, 01}+ é o conjunto de todas as cadeias de tamanho par formadas apenas pela repetição da
subcadeia 01.
4. Considere o alfabeto binário {0, 1}.
(a) Mostre que qualquer linguagem sobre o alfabeto binário {0, 1} é enumerável.
Solução do professor: Qualquer linguagem sobre o alfabeto {0, 1} é, por definição, um sub-
conjunto de {0, 1}∗.
É fácil ver que {0, 1}∗ é enumerável: basta listar todos seus elementos em ordem lexicográfica:
�, 0, 1, 00, 01, 10, 11, 000, 001, . . .
Como todo subconjunto de um conjunto enumerável é também enumerável, temos que toda
linguagem binária deve ser também enumerável.
(b) Mostre que o conjunto P({0, 1}∗) de todas as linguagens sobre o alfabeto binário não é enumerável.
Solução do professor: Vamos usar o método de diagonalização de Cantor, o mesmo usado
para mostrar que o conjunto dos números reais não é enumerável.
Por contradição, assuma que P({0, 1}∗) seja enumerável. Então existe uma enumeração L0, L1, L2, . . .
de todas as linguagens binárias. Esta enumeração pode ser representada na tabela abaixo, em
que cada coluna corresponde a uma palavra de {0, 1}∗ e cada linha corresponde a uma linguagem.
Cada entrada (i, j) da tabela contém ∈ se a cadeia da coluna j pertence à linguagem da linha i,
ou /∈ em caso contrário. Por exemplo, a palavra � pertence à linguagem L0, mas não pertence à
linguagem L1.
Enumeração � 0 1 00 01 10 11 000 001 . . .
L0 ∈ /∈ ∈ /∈ ∈ /∈ ∈ /∈ ∈ . . .
L1 /∈ /∈ /∈ /∈ /∈ ∈ ∈ /∈ /∈ . . .
L2 ∈ ∈ /∈ /∈ ∈ ∈ ∈ /∈ /∈ . . .
...
...
...
...
...
...
...
...
...
...
. . .
Li /∈ ∈ /∈ /∈ /∈ ∈ ∈ ∈ ∈ . . .
...
...
...
...
...
...
...
...
...
...
. . .
Se encontrarmos uma linguagem L̂ ∈ {0, 1}∗ que não esteja listada na tabela acima, chegamos a
uma contradição (pois assumimos por hipótese que a lista de linguagens está completa).
Constrúımos L̂ assim: cada cadeia wj (correspondente à coluna j) pertence a L̂ se, e somente se,
wj não pertence à linguagem Lj (correspondente à linha j).
Assim, L̂ é tal que:
3
Enumeração � 0 1 00 01 10 11 000 001 . . .
L0 ∈ /∈ ∈ /∈ ∈ /∈ ∈ /∈ ∈ . . .
L1 /∈ /∈ /∈ /∈ /∈ ∈ ∈ /∈ /∈ . . .
L2 ∈ ∈ /∈ /∈ ∈ ∈ ∈ /∈ /∈ . . .
...
...
...
...
...
...
...
...
...
...
. . .
Li /∈ ∈ /∈ /∈ /∈ ∈ ∈ ∈ ∈ . . .
...
...
...
...
...
...
...
...
...
...
. . .
L̂ /∈ ∈ ∈ . . . . . . . . . . . . . . . . . . . . .
Mas note que a linguagem L̂ não pode estar na lista, pois ela é diferente de todos os demais
números da lista (L̂ difere de cada Lj exatamente na cadeia wj).
Logo, a lista não pode estar completa, pois L̂ não se encontra nela, e chegamos a uma contradição.
Portanto, o conjunto P{0, 1}∗ de todas as linguagens binários não é enumerável.
(c) Argumente que suas respostas para os itens anteriores valem para qualquer alfabeto finito. Ou
seja, argumente que suas demonstrações podem ser extendidas para mostrar que para qualquer
alfabeto Σ finito, toda linguagem L ⊆ Σ∗ é enumerável, mas o conjunto P(Σ∗) de todas a
linguagens sobre este alfabeto não é enumerável.
Solução do professor: Se Σ é finito, podemos definir uma ordem lexicográfica em Σ∗, logo Σ∗
é enumerável. (Intuitivamente, basta definir uma ordem arbitrária sobre os śımbolos de Σ e usar
esta ordem para enumerar todas as cadeias de Σ∗ em “ordem alfabética”).
A demonstração de que P(Σ∗) não é enumerável é praticamente idêntica à demonstração de que
P({0, 1}∗) não é enumerável; a única diferença é que nas colunas da tabela listamos as palavras
de Σ∗ em vez das palavras de {0, 1}∗.
5. Transforme os seguintes problemas de decisão em um problema de linguagem equivalente. Mais pre-
cisamente, dê uma linguagem para cada problema de tal forma que decidir se uma cadeia pertence à
linguagem equivale a decidir a resposta do problema de decisão para uma instância equivalente.
(a) “Determinar se a palavra w na ĺıngua portuguesa é um paĺındromo.”
(b) “Determinar se r é raiz do polinômio ax2 + bx+ c, para a, b, c, r ∈ Q.”
(c) “Determinar se um programa P executa por mais de n passos.”
Solução doprofessor:
(a) O PD é equivalente ao problema de terminar a pertinência de uma palavra à linguagem
Lpaĺındromo = {〈w〉 | w ∈ {a, b, c, . . . , z}∗ e w é um paĺındromo na ĺıngua portuguesa}.
(b) O PD é equivalente ao problema de terminar a pertinência de uma palavra à linguagem
Lraiz = {〈a, b, c, r〉 | r é uma raiz racional do polinômio ax2 + bx+ c com coeficientes racionais}.
(c) O PD é equivalente ao problema de terminar a pertinência de uma palavra à linguagem
Lexecucao = {〈P, n〉 | P é um programa que executa por mais de n passos}.
4