capítulo 1 - conceitos preliminades de Teoria da Computação

Prévia do material em texto

Caṕıtulo 1
Conceitos Preliminares
Inicialmente, na Seção 1.1, será abordado o problema fundamental relativo ao uso dos
computadores, o da representação, com o intuito de fazer transparecer a importância
dos conceitos matemáticos a serem introduzidos em seguida, tanto no ńıvel de modela-
gem quanto no de representação propriamente dito. O conceito de linguagem formal,
a partir do qual será desenvolvido todo o material do restante do texto, será mostrado
na Seção 1.2. Em seguida, será dada a noção de gramática, um dos formalismos mais
utilizados para a definição de linguagens formais. Nessas duas seções, os conceitos de
linguagem formal e de gramática serão vistos de modo sucinto, nas suas formas mais
gerais; nos caṕıtulos seguintes, eles serão retomados em conexão com classes espećıficas
de linguagens. Para finalizar o caṕıtulo, será apresentada a noção de problemas de
decisão.
1.1 Representação
Quando se pretende resolver um problema por computador, uma tarefa importante é
representar as entidades envolvidas, sejam elas concretas ou não. A representação de
uma entidade nas formas de um programa, de entrada para um programa ou de sáıda de
um programa é, muitas vezes, constitúıda por sequências de śımbolos.1 Considere, por
exemplo, uma aplicação referente à folha de pagamento de uma empresa. A entidade
correspondente ao processo de cálculo da folha de pagamento é representada por uma
sequência de śımbolos em uma linguagem de programação, denominada programa; a
entrada para tal programa é constitúıda de sequências de śımbolos representando vários
tipos de entidades, como o mês em questão, o ano, os nomes dos empregados, o número
de horas trabalhadas para cada empregado etc.; a sáıda do programa é constitúıda por
sequências de śımbolos representando os empregados, o total de horas trabalhadas, a
remuneração etc.
No exemplo do parágrafo anterior, os śımbolos utilizados nas representações das
1 Embora cada vez mais estejam sendo usados recursos gráficos bi e tridimensionais, som etc. De
qualquer maneira, em algum ńıvel, mesmo tais entidades são representadas mediante sequências de
śımbolos.
1
2 Editora Thomson Introdução aos fundamentos da computação
Entidade Modelo Matemático Representação
Mês Número inteiro no Um dos caracteres 1, 2, 3, 4, 5,
intervalo [1, 12] 6, 7, 8, 9, 0, A ou B
Remuneração Número real positivo Numeral com 2 casas decimais
Presença Vetor de números, um Sequência de numerais na
para cada dia do mês base 10
FP Relação Tabela em que cada linha tem
o nome, cargo, salário etc.
Cálculo de FP Algoritmo Programa
Figura 1.1 A matemática entre a entidade e a representação.
diversas entidades mencionadas são normalmente os caracteres (letras, d́ıgitos e/ou ca-
racteres especiais). No entanto, aqui o que pode ser considerado “śımbolo” ficará em
aberto, de forma que não se tenha, de partida, uma restrição desnecessária quando se
pretenda conceber alguma linguagem para representação de alguma coisa. Assim, por
exemplo, podem ser usados como śımbolos sequências espećıficas de alguns caracteres
espećıficos. Podem ser usados como śımbolos alguns desenhos inventados especifica-
mente para a aplicação em questão. E assim por diante.
Muitas vezes, é útil considerar, entre uma entidade representada e a sequência de
śımbolos que a representa, a existência de um terceiro elemento: o modelo matemático
correspondente à entidade representada. A Figura 1.1 mostra alguns exemplos (FP
refere-se à abreviação de folha de pagamento). Veja que a representação do mês não
é lá muito convencional (outubro representado por 0, novembro por A e dezembro por
B). Por outro lado, as descrições de algumas representações estão um pouco vagas, não
especificando precisamente (por enquanto) quais são as sequências realmente permiti-
das; por exemplo, não é explicitada qual é a linguagem de programação espećıfica do
programa que representa o cálculo da folha de pagamento.
Na coluna representação, da Figura 1.1, o elemento fundamental é a sequência de
śımbolos. Ela é utilizada na representação de qualquer tipo de entidade, de maneira a
propiciar a comunicação entre humanos, entre humanos e computadores e entre com-
putadores, além do processamento computacional que a envolve. Por outro lado, as
próprias sequências de śımbolos podem ser estudadas matematicamente, ou seja, há
um modelo matemático especialmente desenvolvido para tratar das mesmas. Em tal
modelagem, em geral, os śımbolos e as sequências de śımbolos são consideradas como
componentes do que se denomina linguagens formais.
Exemplo 1 Seja o (sub)problema de representar o mês em algum tipo de aplicação.
Os meses do ano, de janeiro a dezembro, são as entidades a serem representadas. Na
Figura 1.1 tais entidades são modeladas como o conjunto dos números 1 a 12. Sendo
um pouco mais abstratos, basta considerar como modelo um conjunto de 12 elementos;
considerar tais elementos como números é absolutamente dispensável. Por outro lado,
existem inúmeras representações posśıveis, além daquela exibida na Figura 1.1. Por
Newton José Vieira Caṕıtulo 1: Conceitos preliminares 3
exemplo:
• As palavras janeiro, fevereiro, . . . , dezembro. Śımbolos usados: letras a, b, . . . , z.
• Numerais na base decimal. Śımbolos usados: os d́ıgitos 0 a 9.
• Numerais na base binária. Śımbolos usados: os d́ıgitos 0 e 1.
• Numerais em algarismos romanos. Śımbolos usados: as letras I, V e X.
• Sequências de um a doze 0s. Śımbolos usados: apenas o d́ıgito 0.
A linguagem formal usada para representar os meses é, assim, constitúıda de sequências
de alguns śımbolos escolhidos. Em ńıvel matemático, uma linguagem formal será defi-
nida, na Seção 1.2, justamente como um conjunto de sequências de śımbolos, sendo o
conjunto dos śımbolos escolhidos denominado o alfabeto da linguagem.
Um exemplo importante de linguagem formal é uma linguagem de programação.
Cada programa escrito em uma certa linguagem de programação é uma sequência de
śımbolos. No caso, pode-se convencionar que os śımbolos são os caracteres que podem
aparecer nos programas. Mas, alternativamente, pode-se convencionar que os śımbolos
são certas sequências espećıficas de caracteres. Por exemplo, a palavra “while”, presente
em muitas linguagens de programação, pode ser considerada como uma sequência de 5
śımbolos, se se considerar cada caractere como um śımbolo, ou como um único śımbolo.
Cada uma dessas duas visões pode ser a mais conveniente dependendo da aplicação.
De qualquer forma, considerando um programa como uma sequência de śımbolos, a
linguagem de programação pode ser considerada como o conjunto de tais sequências.
Uma boa parte deste texto versará sobre linguagens formais. Isso será importante
tanto para introduzir técnicas bem fundamentadas para a construção de algoritmos,
visando amplo espectro de aplicações, quanto para caracterizar o conceito de computa-
bilidade. Nesse último aspecto, será visto, por exemplo, que existe uma infinidade de
funções que não são computáveis; em particular, serão vistos problemas com enuncia-
dos bastante simples para os quais não existe algoritmo e, portanto, não há programa
em nenhuma linguagem de programação.
Exemplo 2 Seja J o conjunto dos programas em Java. Tal conjunto será visto neste li-
vro como a linguagem Java. Neste caso, o problema de determinar, dada uma sequência
de śımbolos (no caso, caracteres) x qualquer, se ela pertence ao conjunto J , é com-
putável. Ele é o problema da análise sintática:2 se x ∈ J , então x é (um programa)
sintaticamente correto; se x 6∈ J , x é incorreto. Um exemplo de problema para o qual
não existe algoritmo é o de, dado um programa qualquer em Java, determinar se ele
emitirá algum sinal sonoro, isto é, dada uma sequência de śımbolos x, determinar se
ela pertence aoconjunto {x ∈ J |x, ao ser executado, emite um sinal sonoro}. A não
existência de algoritmo para esse problema será objeto do Exerćıcio 2 no final da seção.
2 A expressão x ∈ A denota que o elemento x pertence ao conjunto A, e x 6∈ A denota que x não
pertence a A. Elementos de teoria dos conjuntos são apresentados na Seção A.2.
4 Editora Thomson Introdução aos fundamentos da computação
Para fazer o estudo das linguagens formais, assim como para considerar modelos
alternativos para o conceito de computabilidade, são necessários alguns elementos de
matemática, que estão explicitados no Apêndice A. Esses elementos também são úteis
na etapa intermediária de modelagem ilustrada na Figura 1.1. Em tal apêndice, cada
assunto é apresentado de forma bastante concisa, mas suficiente para dar suporte ao
aprendizado do que vem a seguir.
Na próxima seção, o conceito de linguagem formal introduzido anteriormente será
um pouco mais elaborado, de forma a dar suporte ao conteúdo dos caṕıtulos restantes.
Exerćıcios
1. Encontre uma maneira de representar, por meio de uma sequência dos śımbolos
x e o:
a) qualquer número inteiro positivo;
b) qualquer vetor de números inteiros positivos;
c) qualquer matriz de números inteiros positivos.
2. Uma versão do problema da parada, problema este a ser abordado no Caṕıtulo 5,
é: dado um programa (sem entrada), determinar se ele para. Lá no Caṕıtulo 5
será visto que não existe algoritmo que, recebendo como entrada um (texto de)
programa qualquer em Java (ou em outra linguagem de programação), determine
se ele para ou não. Em outras palavras, o problema da parada não é com-
putável. Sabendo disto, argumente que o problema enunciado no Exemplo 2,
“dado um programa qualquer em Java, determinar se ele emitirá algum sinal
sonoro”, também não é computável.
1.2 Linguagens Formais
Uma linguagem formal, ao contrário de uma linguagem natural, é tal que:
a) tem uma sintaxe bem definida, de forma que, dada uma sentença, seja sempre
posśıvel saber se ela pertence ou não à linguagem; e
b) tem uma semântica precisa, de modo que não contenha sentenças sem significado
ou amb́ıguas.
As linguagens formais são úteis, não só na matemática, mas também nas áreas que
utilizam a matemática como ferramenta, como as engenharias, a f́ısica, a qúımica e
a computação. No caso da computação, as linguagens formais têm uma importância
ı́mpar, pois a maioria dos profissionais da área lida diretamente com uma ou mais no
dia-a-dia.
Exemplos de linguagens formais, ou concretizações diretas das mesmas, são as lin-
guagens Java, C, Pascal, HTML etc. Em prinćıpio, se um programador ou analista
projeta um programa ou sistema que envolve um diálogo com o usuário, ele tem o pro-
blema de projetar a linguagem (formal) de comunicação. Desde o ńıvel de instruções
Newton José Vieira Caṕıtulo 1: Conceitos preliminares 5
de máquina até os ńıveis mais altos da programação de um computador, as linguagens
formais são uma presença constante.
Nesta seção, será vista uma definição de linguagem formal bastante geral, sem tocar
na parte de semântica. À primeira vista isso pode parecer uma limitação, mas o fato é
que uma abordagem puramente sintática é suficiente para a caracterização do conceito
de “computabilidade”, um dos objetivos deste texto, assim como para servir de base
para ampla gama de aplicações, como ficará claro no decorrer do livro. Além disso, a
especificação e o processamento da sintaxe de linguagens formais já envolve um material
bastante extenso, que pode anteceder um estudo posterior de semântica. No entanto,
muitas vezes consegue-se uma estrutura sintática rica o suficiente para capturar todos
os aspectos relevantes da linguagem, não havendo a necessidade de considerar uma
semântica à parte.
Toda linguagem3 tem um alfabeto associado.
Definição 1 Um alfabeto é um conjunto finito não vazio.
Os elementos de um alfabeto serão referidos como śımbolos. Note que só há duas
restrições para que um conjunto possa ser usado como alfabeto: ele não pode ser vazio
e deve ser finito. Uma palavra4 sobre um alfabeto Σ é uma sequência finita de śımbolos
de Σ.5 O tamanho de uma palavra x, |x|, é o número de śımbolos que a compõem.
Em particular, existe a palavra vazia, constitúıda de zero śımbolos; tal palavra será
designada por λ. Assim, |λ| = 0.
Exemplo 3 Dois exemplos de alfabetos particularmente importantes são: Σ = {1} e
Γ = {0, 1}.
São palavras sobre Γ: λ, 0, 1, 00, 01, 10, 11, 000 etc. Com esse alfabeto, pode-se
representar qualquer número. Uma possibilidade é utilizar a codificação na base 2: 0
é representado por uma infinidade de palavras: 0, 00 etc.; 1 é representado por uma
infinidade de palavras: 1, 01 etc.; apenas λ não representa nenhum número.
São palavras sobre Σ: λ, 1, 11, 111 etc. Observe que, com esse alfabeto, também
se consegue representar qualquer número natural! Por exemplo, basta representar o
número n por uma palavra de tamanho n. Nesse caso, cada palavra x representaria
o número |x|. Comparando a representação do parágrafo anterior com a deste, note
que a menor palavra x usada para representar um número n na base 2 tem tamanho
⌊log2 n⌋+ 1, e a palavra y usada para representar o mesmo número n na base 1 possui
tamanho n. Dessa forma, nessa segunda representação a palavra usada é exponencial-
mente maior.
3 Daqui para a frente, quando se disser “linguagem”, quer-se dizer “linguagem formal”, a menos que
se diga o contrário.
4 Em inglês, são utilizados os termos string ou word.
5 Formalmente, uma sequência é uma função f : {1, 2, 3, . . . , n} → Σ. Ela é representada normalmente
por f(1)f(2)f(3) · · · f(n). Por exemplo, a sequência f : {1, 2, 3} → {0, 1} tal que f(1) = 1, f(2) = 0 e
f(3) = 1 é representada por 101.
6 Editora Thomson Introdução aos fundamentos da computação
Seja a um śımbolo qualquer. A notação an, em que n ∈ N, será utilizada para
designar a palavra constitúıda de n as em sequência. Assim, por exemplo, dado o
alfabeto {0, 1}, são exemplos de palavras sobre tal alfabeto: 10 = λ, 04 = 0000,
13012 = 111011 etc.
Definição 2 Uma linguagem sobre um alfabeto Σ é um conjunto de palavras sobre Σ.
Pela definição, qualquer conjunto de palavras é uma linguagem. Denotando o conjunto
de todas as palavras sobre Σ por Σ∗, diz-se, então, que uma linguagem sobre Σ é
qualquer subconjunto de Σ∗.
Exemplo 4 Seja o alfabeto Σ = {0, 1}. O conjunto de todas as palavras sobre Σ é
Σ∗ = {λ, 0, 1, 00, 01, 10, 11, 000, . . .}. São exemplos de linguagens sobre Σ:
• ∅. É a linguagem mais simples que existe; não contém palavras;
• {λ}. Contém uma única palavra: a palavra vazia;
• {0}. Contém uma única palavra: 0;
• {λ, 0}. Contém duas palavras: λ e 0;
• {w ∈ Σ∗ | 1 ≤ |w| ≤ 5}. Contém
∑5
i=1 2
i palavras;
• {0n |n é um número primo}. Esta linguagem é infinita, já que existe uma infini-
dade de números primos;
• {0n1n |n ∈ N}. Linguagem constitúıda de toda palavra de tamanho par cuja
primeira metade só contém 0s e cuja segunda metade só contém 1s;
• Σ∗. Contém todas as palavras sobre o alfabeto Σ.
Assim como as três últimas linguagens do Exemplo 4, a maioria das linguagens
de interesse é infinita. Como fazer para especificar tais linguagens, se não dá para
listar explicitamente todas as suas palavras? Na verdade, como será visto oportuna-
mente, existem muitas opções para isso, cada uma delas possuindo contextos em que é
mais apropriada.
Como uma linguagem é um conjunto, pode-se lançar mão das operações sobre con-
juntos, definidas na Seção A.2. Assim, por exemplo, se L1 e L2 são linguagens sobre
alfabetos Σ1 e Σ2, respectivamente, também são linguagens:
• L1 ∪ L2, uma linguagem sobre Σ1 ∪ Σ2;
• L1 ∩ L2, uma linguagem sobre Σ1 ∩ Σ2;
• L1 − L2, uma linguagem sobre Σ1.
• L1 = Σ
∗
1 − L1, uma linguagem sobre Σ1.
Newton José Vieira Caṕıtulo1: Conceitos preliminares 7
Note que, por definição, o complemento de uma linguagem é constitúıdo das palavras no
alfabeto da própria linguagem, excetuadas as palavras da mesma. Além dessas, levando-
se em consideração que os elementos que constituem as linguagens são as palavras,
existem outras operações, tanto sobre palavras quanto sobre linguagens, que podem
auxiliar na especificação de uma linguagem. Veja ainda que:6
• P(L1) é um conjunto de linguagens sobre Σ1;
• P(Σ∗1) é o conjunto de todas as linguagens sobre Σ1.
A concatenação de duas palavras x = a1a2 . . . am e y = b1b2 . . . bn é a palavra xy =
a1a2 . . . amb1b2 . . . bn. Em particular, note que λw = wλ = w para qualquer palavra w.
Tal definição implica que a concatenação é uma operação associativa: x(yz) = (xy)z
para quaisquer palavras x, y e z. Desse modo, uma sequência de concatenações poderá
ser escrita sem parênteses. E para expressar a concatenação de uma palavra w com
ela mesma n− 1 vezes, pode-se escrever wn; em particular, define-se que w0 = λ para
qualquer palavra w.
Exemplo 5 Sejam x = aab e y = cc. Então yx = ccaab, x2 = xx = aabaab,
xy2 = aab(cc)2 = aabcccc, axbbyc = aaabbbccc = a3b3c3, λ(aa)3λλy3λ = a6c6.
Uma palavra x é dita ser um prefixo de uma palavra w se w = xy para alguma
palavra y; é dita ser um sufixo de w se w = yx para alguma palavra y; e é dita ser
uma subpalavra de w se w = yxz para algum par de palavras y e z. As três partes, x,
y e z, podem ser λ ou não. Observe que, em particular, λ e w são prefixos, sufixos e
subpalavras de qualquer palavra w, e também que prefixos e sufixos são subpalavras.
Exemplo 6 Considere a palavra abc. Seus prefixos são: λ, a, ab e abc. Seus sufixos:
λ, c, bc e abc. As subpalavras de abc são: λ, a, b, c, ab, bc e abc. Apenas a subpalavra
b não é prefixo nem sufixo de abc.
O reverso de uma palavra w = a1a2 . . . an, w
R, é a sequência dos śımbolos de
w na ordem reversa, isto é, wR = anan−1 . . . a1. Uma palavra w tal que w = w
R é
um paĺındromo. Veja que todo paĺıdromo de tamanho par é da forma xxR, e que os
paĺındromos de tamanho ı́mpar são da forma xaxR, em que a é um śımbolo do alfabeto
em questão.
Exemplo 7 Alguns reversos de palavras: λR = λ; aR = a; (c5)R = c5, (abcaabb)R =
bbaacba. Alguns paĺındromos: λ, a, bb, ccc, aba, baab, abcacba.
Definição 3 A concatenação de duas linguagens L1 eL2 é dada por:
L1L2 = {xy |x ∈ L1 e y ∈ L2}.
6 P(A) denota o conjunto potência do conjunto A, como definido na Seção A.2.
8 Editora Thomson Introdução aos fundamentos da computação
Em particular, ∅L = L∅ = ∅ e {λ}L = L{λ} = L, para qualquer linguagem L.
Exemplo 8 Sejam as linguagens L1 = {w ∈ {0, 1}
∗ | |w| = 5} e a linguagem L2 =
{0y | y ∈ {0, 1}∗}. Então:
• L1L1 = {w ∈ {0, 1}
∗ | |w| = 10};
• L1L2 = {w ∈ {0, 1}
∗ | o sexto śımbolo de w é 0};
• L2L1 = {w ∈ {0, 1}
∗ | w começa com 0 e |w| ≥ 6};
• L2L2 = {0y | y ∈ {0, 1}
∗ e y contém no mı́nimo um 0}.
Seja L uma linguagem. A notação Ln será utilizada para designar LL . . . L (n vezes).
Recursivamente:
a) L0 = {λ};
b) Ln = Ln−1L para n ≥ 1.
L0 = {λ} porque, segundo o item b desta definição, tem-se que (para n = 1) L1 = L0L,
e para que L1 seja igual a L é preciso que L0 seja {λ}.
Exemplo 9 {0, 1}2 = {00, 01, 10, 11}. Generalizando, {0, 1}n = {w ∈ {0, 1}∗ | |w| =
n} para qualquer n ≥ 0. {λ, 0, 1}2 = {λ, 0, 1, 00, 01, 10, 11}. Generalizando, {λ, 0, 1}n =
{w ∈ {0, 1}∗ | |w| ≤ n} para qualquer n ≥ 0. {0, 01}2 = {00, 001, 010, 0101}.
Definição 4 A operação fecho de Kleene de uma linguagem L, L∗, pode ser definida
recursivamente assim:
a) λ ∈ L∗;
b) se x ∈ L∗ e y ∈ L, então xy ∈ L∗.
A partir da Definição 4 e da definição de concatenação de linguagens, pode-se
verificar que:
L∗ =
⋃
n∈N
Ln.
Ou seja, L∗ = L0∪L1∪L2∪ · · · = {λ}∪L∪LL∪ · · ·. Veja o Exerćıcio 16 da Seção 1.5.
Define-se também o fecho positivo de Kleene de L: L+ = LL∗. Pode-se verificar que:
L+ =
⋃
n∈N−{0}
Ln.
Segue diretamente dessas definições que L∗ = L+ ∪ {λ}. Pode-se mostrar também que
L+ = LL∗ = L∗L.
Exemplo 10 A seguir, são apresentadas algumas linguagens e seus fechos de Kleene:
• ∅∗ = {λ}, e ∅+ = ∅;
• {λ}∗ = {λ}+ = {λ};
Newton José Vieira Caṕıtulo 1: Conceitos preliminares 9
• {0}∗ = {0n |n ∈ N} e {0}+ = {0n |n ≥ 1};
• {λ, 00, 11}∗ = {λ, 00, 11}+ = {λ} ∪ {00, 11}+.
Com as operações definidas nesta seção, pode-se expressar (ou definir) de forma
precisa algumas linguagens, como exemplificado a seguir.
Exemplo 11 Seguem descrições informais, em português, para algumas linguagens
sobre {0, 1}, bem como descrições mais formais utilizando as operações definidas nesta
seção:
a) o conjunto das palavras que começam com 0: {0}{0, 1}∗;
b) o conjunto das palavras que contêm 00 ou 11: {0, 1}∗{00, 11}{0, 1}∗;
c) o conjunto das palavras que terminam com 0 seguido de um número ı́mpar de 1s
consecutivos: {0, 1}∗{01}{11}∗;
d) o conjunto das palavras que começam ou terminam com 0: {0}{0, 1}∗∪{0, 1}∗{0};
e) o conjunto das palavras de tamanho par que começam ou terminam com 0:
({0, 1}{0, 1})∗ ∩ [{0}{0, 1}∗ ∪ {0, 1}∗{0}];
f) o conjunto do item (e): [{0}{0, 1}({0, 1}{0, 1})∗ ] ∪ [{0, 1}({0, 1}{0, 1})∗{0}];
g) o conjunto das palavras com um prefixo de um ou mais 0s seguido (imediatamente)
de um sufixo de 1s de mesmo tamanho: {0n1n |n ≥ 1};
h) o conjunto das palavras formadas por concatenações de palavras da forma 0n1n
para n ≥ 1: ∪k≥1{0
n1n |n ≥ 1}k.
Um aspecto muito importante é que as seis primeiras linguagens do exemplo ante-
rior são linguagens definidas a partir de conjuntos finitos de palavras usando apenas
as operações sobre conjuntos e as de concatenação e fecho de Kleene. O tratamento
computacional de uma linguagem (verificar se uma palavra pertence ou não à mesma)
que possa ser descrita dessa forma pode ser feito de forma extremamente eficiente. O
Caṕıtulo 2 irá tratar justamente desse tipo de linguagem e do respectivo tratamento
computacional. Já as duas últimas linguagens do exemplo não podem ser descritas
por meio daquelas operações a partir de conjuntos finitos, e seu tratamento computa-
cional não pode ser feito de forma tão eficiente. Elas serão consideradas em caṕıtulos
posteriores.
Como uma linguagem sobre um alfabeto Σ é sempre um conjunto contável, pois é
um subconjunto de Σ∗, que é enumerável, existe a possibilidade de fazer uma definição
recursiva, da forma mostrada na Seção A.6. Mas a verdade é que, na prática, as
linguagens raramente são definidas dessa forma. Existe um formalismo, que permite
o uso de recursão, porém foi especialmente projetado para a definição de linguagens:
a gramática. Na próxima seção será apresentada uma breve introdução às gramáticas.
Em caṕıtulos posteriores, elas serão mais bem estudadas e exploradas pouco a pouco.
10 Editora Thomson Introdução aos fundamentos da computação
Exerćıcios
1. Qual é o número de prefixos, sufixos e subpalavras de uma palavra de tamanho n?
2. Seja Σ = {0, 1, #}. Sejam k e n números naturais tais que k ≤ n.
a) Quantas palavras há na linguagem Σk?
b) Quantas palavras há na linguagem (Σ ∪ {λ})k?
c) Quantas palavras de n śımbolos contêm exatamente k ocorrências de #?
d) Quantas palavras de n śımbolos contêm no máximo k ocorrências de #?
3. Seja Σ um alfabeto. Prove que se x, y, w ∈ Σ∗ e xw = yw, então x = y.
4. Sejam A = {00, 11}, B = {01, 10} e C = {λ, 1}. Calcule:
a) AA;
b) AC;
c) CC;
d) (AB)C;
e) A(BC);
f) A(B ∪ C);
g) AB ∪AC.
5. Sejam Σ = {0, 1}, A = Σ∗{0} e B = {1}Σ∗. Descreva, em português, as lingua-
gens a seguir. Não é necessário dizer que as palavras são de 0s e 1s. Por exemplo,
A é o “conjunto das palavras que terminam com 0”.
a) A ∪B;
b) A ∩B;
c) A−B;
d) B −A;
e) A;
f) AB;
g) BA.
6. Seja L = {λ, 0, 1}.
a) Que linguagem é L0?
b) Que linguagem é L2?
c) Que linguagem é Ln para n ≥ 0?
d) Quantas palavras tem Ln para n ≥ 0?
7. Sejam A = {0} e B= {1}. Determine AnB, ABn e (AB)n.
8. Sejam A = {λ, a} e B = {a, b}. Determine AnB, ABn e AnBn. Quantos elemen-
tos tem cada um desses conjuntos?
Newton José Vieira Caṕıtulo 1: Conceitos preliminares 11
9. Encontre linguagens A, B e C tais que A(B −C) 6= AB −AC.
10. Que linguagens são subconjuntos de quais outras?
a) {a}∗;
b) {a}∗ ∪ {b}∗;
c) {a}∗{b}∗;
d) {a, b}∗;
e) ({a}∗{b}∗)∗.
11. Sejam A = {a} e B = {bb}. Quantas palavras de n śımbolos, para cada n ≥ 0,
há em:
a) A∗B?
b) AB∗?
c) A∗B∗?
12. 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 com, no máximo, um 0;
c) o conjunto das palavras de tamanho ı́mpar;
d) o conjunto das palavras com um prefixo de um ou mais 0s seguido (imedia-
tamente) de um sufixo de zero ou mais 1s;
e) o conjunto dos paĺındromos que não tenham śımbolos consecutivos idênticos;
f) o conjunto das palavras de tamanho par cuja primeira metade é idêntica à
segunda.
Procure ser bem preciso e conciso.
13. Sejam Σ = {0, 1}, A = Σ5 e B = {0}Σ∗. Para cada uma das linguagens a
seguir, dê uma propriedade necessária e suficiente para que uma palavra pertença
à mesma. Não é preciso dizer que a palavra contém apenas os śımbolos 0 e 1.
a) A∗;
b) B+;
c) A ∩B;
d) AB;
e) A∗ ∩B∗.
14. Descreva, em português, as seguintes linguagens sobre o alfabeto {0, 1}:
a) {0, 1}∗{1}{0, 1};
b) {0}{0, 1}∗ ∪ {0, 1}∗{1};
c) {0, 1}∗{01}{11}∗;
d) {01, 1}∗;
e) {1, λ}({0}{0}∗{1})∗{0}∗;
12 Editora Thomson Introdução aos fundamentos da computação
f) {0}∗{1}({0} ∪ {1}{0}∗{1})∗.
15. Seja Σ o conjunto de todas as 26 letras do alfabeto e C o conjunto das 21 con-
soantes. Seja D o conjunto de todas as palavras de um dicionário da lingua
portuguesa, e, para cada letra l ∈ Σ, seja Pl = D ∩ (Σ
∗{l}Σ∗). A partir de tais
conjuntos, usando operações sobre conjuntos, concatenações e fechos de Kleene,
descreva o conjunto das palavras de D tais que:
a) que contêm pelo menos uma das letras A, B ou C;
b) que contêm as letras A e B, mas não C;
c) que não contêm A nem B;
d) que começam com a letra A;
e) que começam com a letra A e contêm pelo menos uma consoante;
f) que contêm a subpalavra RR.
16. Expresse as linguagens a seguir utilizando as operações sobre conjuntos finitos de
palavras de {0, 1}∗. Considere o alfabeto como sendo {0, 1}.
a) o conjunto das palavras de 10 śımbolos;
b) o conjunto das palavras que têm de 1 a 200 śımbolos;
c) o conjunto das palavras que começam e terminam com o mesmo śımbolo;
d) o conjunto das palavras que contêm pelo menos um 0 e um 1;
e) o conjunto das palavras que começam com 0 e contêm 00;
f) o conjunto das palavras que não têm 00 como prefixo, mas têm 00 como
sufixo;
g) o conjunto das palavras que começam com 00 ou 11 e terminam com 01 ou
10;
h) o conjunto das palavras em que todo 0 é seguido de dois 1s consecutivos;
exemplos: λ, 1, 1011111, 11011101111;
i) {01n0 |n é ı́mpar};
j) o conjunto das palavras de {0}∗{1}∗ de tamanho par;
k) o conjunto das palavras com número par de 0s ou ı́mpar de 1s (ou ambos);
l) o conjunto das palavras que contêm um ou dois 1s, cujo tamanho é múltiplo
de 3;
m) o conjunto das palavras com número par de 0s e ı́mpar de 1s.
17. Sejam A, B e C linguagens sobre um alfabeto Σ. Mostre que:
a) A(B ∪ C) = (AB) ∪ (AC);
b) nem sempre A(B ∩ C) = (AB) ∩ (AC).
18. Mostre que, se λ ∈ L, então L+ = L∗ e, se λ 6∈ L, então L+ = L∗ − {λ}.
19. Quando L∗ é finita?
20. Prove que (wR)n = (wn)R para toda palavra w e todo n ∈ N.
Newton José Vieira Caṕıtulo 1: Conceitos preliminares 13
21. Prove que não existe x ∈ {0, 1}∗ tal que 0x = x1.
22. Sejam L1 e L2 linguagens sobre um alfabeto Σ tais que L1 ⊆ L2. Prove que
L∗1 ⊆ L
∗
2.
23. Apresente um exemplo em que L∗1 ∪ L
∗
2 = (L1 ∪ L2)
∗, mas L1 6⊆ L2 e L2 6⊆ L1.
24. Mostre que os conjuntos a seguir são enumeráveis:
a) {0}∗;
b) {0}∗{1}∗.
25. Seja a seguinte definição recursiva da linguagem L sobre o alfabeto {0, 1}:
a) λ ∈ L;
b) se x ∈ L, então 0x ∈ L e x1 ∈ L;
c) nada mais pertence a L.
Que linguagem é L?
26. Seja a linguagem X, de alfabeto {a, b}, definida assim:
a) λ ∈ X;
b) se x ∈ X então ax ∈ X e axbx ∈ X;
c) x ∈ X somente se pode ser obtido como especificado em (a) e (b).
Sejam na(x) e nb(x) o numero de as e de bs, respectivamente, na palavra x. Prove,
por indução, que na(x) ≥ nb(x).
27. Dê definições recursivas para as seguintes linguagens:
a) {0n1n |n ∈ N};
b) {w ∈ {0, 1}∗ | w contém 00};
c) {w ∈ {0, 1}∗ | w é paĺındromo};
d) {xx |x ∈ {0, 1}∗};
e) {001011021 . . . 0n1 |n ∈ N}.
1.3 Gramáticas
As gramáticas são um formalismo originalmente projetado para a definição de lingua-
gens. Nesta seção, será apenas definido o conceito de gramática e apresentados alguns
poucos exemplos. Nos próximos caṕıtulos, o estudo de gramáticas, associado a classes
espećıficas de linguagens, será retomado e serão apresentados muitos outros exemplos.
Antes de dar uma definição precisa de gramática, serão apresentados os conceitos
envolvidos de maneira informal. Como foi dito na Seção A.6, uma definição recursiva
provê um meio de construir (ou gerar) os elementos de um conjunto (enumerável).
Similarmente, uma gramática mostra como gerar as palavras de uma linguagem.
14 Editora Thomson Introdução aos fundamentos da computação
O elemento fundamental das gramáticas é a regra.7 Uma regra é um par ordenado
(u, v), tradicionalmente escrito na forma u → v, em que u e v são palavras que podem
conter śımbolos de dois alfabetos disjuntos, um com śımbolos denominados variáveis,
ou não terminais, e outro com śımbolos chamados terminais. As variáveis são śımbolos
auxiliares para a geração das palavras da linguagem, enquanto o conjunto de terminais
nada mais é que o alfabeto da linguagem definida. Nos exemplos a seguir, serão usadas
letras maiúsculas para as variáveis e minúsculas para os terminais. Segue um exemplo
de regra:
aAB → baA
Essa regra especifica que: dada uma palavra que contenha a subpalavra aAB, tal
subpalavra pode ser substitúıda por baA. Assim, a partir da palavra aABBaAB,
aplicando-se a regra mencionada, pode-se obter, diz-se derivar :
• baABaAB, substituindo a primeira ocorrência de aAB; ou
• aABBbaA, substituindo a segunda ocorrência de aAB.
A relação de derivação é denotada por ⇒. Por exemplo, a cadeia de derivações
aABBaAB ⇒ baABaAB (aplicando-se a regra aAB → baA)
⇒ bbaAaAB (aplicando-se a regra aAB → baA)
⇒ bbaAbaA (aplicando-se a regra aAB → baA)
mostra uma derivação de bbaAbaA a partir de aABBaAB.
Uma gramática consta de um conjunto de regras e da indicação de uma variável
especial denominada variável de partida. Qualquer derivação deve começar com a
palavra constitúıda apenas pela variável de partida.
As palavras de variáveis e/ou terminais geradas a partir da variável de partida são
chamadas formas sentenciais da gramática. Assim, uma regra pode ser aplicada a uma
forma sentencial para gerar uma outra forma sentencial. Uma forma sentencial sem
variáveis é conhecida como sentença. A linguagem definida pela gramática, também
dita gerada pela gramática, é o conjunto de sentenças geradas pela gramática. Para
uma gramática G, a linguagem gerada por ela é denotada por L(G). A seguir, os
conceitos introduzidos anteriormente são exemplificados.
Exemplo 12 Agora define-se uma gramática G que tem duas variáveis, P e X, sendo
P a variável de partida, e dois terminais, 0 e 1. Suas regras são:
1. P → 0P
2. P → 1X
3. X → 1X
4. X → λ
7 Também chamada regra de produção, ou produção, simplesmente.
Newton José Vieira Caṕıtulo 1: Conceitos preliminares 15
Toda derivação deve começar com a forma sentencial constitúıda pela variável de par-
tida P . Um exemplo de derivação é:
P ⇒ 0P (regra 1)
⇒ 01X (regra 2)
⇒ 01 (regra 4)
Como 01 é uma sentença, tal palavra pertence aL(G). Um outro exemplo de derivação:
P ⇒ 0P (regra 1)
⇒ 00P (regra 1)
⇒ 001X (regra 2)
⇒ 0011X (regra 3)
⇒ 0011 (regra 4)
Logo, 0011 ∈ L(G). Pode-se notar que qualquer derivação de sentença, ou seja, forma
sentencial sem variáveis, envolve:
• aplicar n ≥ 0 vezes a regra 1, produzindo uma forma sentencial da forma 0nP ;
em seguida,
• aplicar uma única vez a regra 2, produzindo 0n1X; depois,
• aplicar k ≥ 0 vezes a regra 3, produzindo 0n11kX; e, finalmente,
• aplicar uma única vez a regra 4, produzindo 0n11k.
Logo, a linguagem gerada por G é L(G) = {0}∗{1}+.
Agora, define-se formalmente o que é gramática.
Definição 5 Uma gramática é uma quádrupla (V,Σ, R, P ), em que:
a) V é um conjunto finito de elementos denominados variáveis;
b) Σ é um alfabeto; V ∩ Σ = ∅;
c) R ⊆ (V ∪ Σ)+ × (V ∪ Σ)∗ é um conjunto finito de pares ordenados chamados
regras; e
d) P ∈ V é uma variável conhecida como variável de partida.
Observe que o lado esquerdo de uma regra não pode ser λ. O próximo exemplo apresenta
uma gramática mais elaborada.
Exemplo 13 Seja a gramática H = ({P,B}, {a, b, c}, R, P ) em que R é constitúıdo
das regras:
1. P → aPBc
2. P → abc
16 Editora Thomson Introdução aos fundamentos da computação
3. cB → Bc
4. bB → bb
Toda derivação de H deve começar com a forma sentencial constitúıda pela variável de
partida P . Um exemplo de derivação de sentença:
P ⇒ abc (regra 2)
Logo, abc ∈ L(H). Outro exemplo de derivação:
P ⇒ aPBc (regra 1)
⇒ aaPBcBc (regra 1)
⇒ aaabcBcBc (regra 2)
⇒ aaabBccBc (regra 3)
⇒ aaabbccBc (regra 4)
⇒ aaabbcBcc (regra 3)
⇒ aaabbBccc (regra 3)
⇒ aaabbbccc (regra 4)
Logo, a3b3c3 ∈ L(H). Na verdade, pode-se mostrar que L(H) = {anbncn |n ≥ 1}.
É muito comum uma gramática ter duas ou mais regras com o mesmo lado esquerdo.
Por exemplo, a gramática do Exemplo 12 tem as regras 1 e 2 com o mesmo lado
esquerdo, assim como as regras 3 e 4. Nesse caso, pode-se abreviar colocando-se apenas
um lado esquerdo e os lados direitos das várias regras separados por “|”. Desta forma,
as regras do Exemplo 12 seriam substitúıdas por:
P → 0P | 1X
X → 1X |λ
De forma análoga, as regras 1 e 2 da gramática do Exemplo 13 podem ser substitúıdas
por:
P → aPBc | abc
Seja uma gramática G = (V,Σ, R, P ). Diz-se que x ⇒ y em G, em que x, y ∈
(V ∪ Σ)∗, se há uma regra u → v ∈ R tal que u ocorre em x e y é o resultado de
substituir uma ocorrência de u em x por v. A relação
n
⇒ é definida recursivamente
assim, utilizando-se ⇒:
a) x
0
⇒ x para todo x ∈ (V ∪ Σ)∗;
b) se w
n
⇒ xuy e u → v ∈ R, então w
n+1
⇒ xvy para todo w, x, y ∈ (V ∪ Σ)∗, n ≥ 0.
Quando x
n
⇒ y, diz-se que “de x deriva-se y em n passos”, ou então que “há uma
derivação de tamanho n de y a partir de x”. Diz-se ainda que de x deriva-se y em zero
ou mais passos, x
∗
⇒ y, se existe n ≥ 0 tal que x
n
⇒ y.8 E de x deriva-se y em um ou
8 Usando a terminologia da Seção A.3, x
∗
⇒ y é o fecho transitivo e reflexivo da relação ⇒.
Newton José Vieira Caṕıtulo 1: Conceitos preliminares 17
mais passos, x
+
⇒ y, se existe n ≥ 1 tal que x
n
⇒ y.9 Com isso, pode-se definir o que é
a linguagem gerada pela gramática G:
L(G) = {w ∈ Σ∗ |P
∗
⇒ w}.
Exemplo 14 Seja a gramática I = ({X,B}, {a, b}, R,X), em que R consta das regras:
1 e 2. P → aPb |Bb
3 e 4. B → Bb |λ
O seguinte esquema de derivação mostra como toda palavra da forma anbn+1+k, para
n ≥ 0 e k ≥ 0 podem ser geradas :
P
n
⇒ anPbn (regra 1 n vezes, n ≥ 0)
⇒ anBbn+1 (regra 2)
k
⇒ anBbn+1+k (regra 3 k vezes, k ≥ 0)
⇒ anbn+1+k (regra 4)
Logo, pode-se derivar qualquer palavra anbn+1+k, para n, k ≥ 0, em n+k+2 passos, ou
seja, qualquer palavra anbm tal que n < m, ou ainda, observando-se que m = n+1+k,
então P
m+1
=⇒ anbm. E como não é posśıvel gerar outras palavras, conclui-se que L(I) =
{anbm |n < m}.
No exemplo anterior foi introduzido o conceito de esquema de derivação. No exem-
plo, qualquer sentença que possa ser gerada obedece ao esquema, no sentido de que
uma derivação da sentença pode ser obtida introduzindo-se valores espećıficos para as
variáveis que aparecem no esquema. Por exemplo, uma derivação da sentença aabbbb
seria obtida instanciando-se n com 2 e k com 1:
P
2
⇒ a2Pb2 (regra 1 duas vezes)
⇒ a2Bb3 (regra 2)
1
⇒ a2Bb4 (regra 3 uma vez)
⇒ a2b4 (regra 4)
Em geral, um esquema de derivação para uma gramática G mostra apenas como
um conjunto A (das sentenças geradas segundo o esquema) está contido na linguagem
gerada por G, ou seja, A ⊆ L(G). Diferentes esquemas podem ser usados para mos-
trar que outros subconjuntos de L(G) são deriváveis. Por outro lado, deve-se provar
também que as únicas palavras geradas por G são as deriváveis pelo(s) esquema(s)
apresentado(s). No caso particular do Exemplo 14, como não existem outros esque-
mas para quaisquer sentenças deriváveis na gramática, pode-se dizer que o esquema lá
apresentado mostra como derivar todas as palavras de L(G).
9 x
+
⇒ y é o fecho transitivo da relação ⇒.
18 Editora Thomson Introdução aos fundamentos da computação
Exemplo 15 Seja a gramática H do Exemplo 13. As duas derivações demonstram
que P
1
⇒ abc e P
8
⇒ a3b3c3. É fácil mostrar que todas as palavras da forma anbncn,
para n ≥ 1, são geradas por H. Para isso, basta notar que tais palavras podem ser
geradas por derivações da forma:
P
k
⇒ akP (Bc)k (regra 1 k vezes, k ≥ 0)
⇒ ak+1bc(Bc)k (regra 2)
1
⇒ ak+1bBcc(Bc)k−1 (regra 3 uma vez)
2
⇒ ak+1bBBccc(Bc)k−2 (regra 3 duas vezes)
...
k
⇒ ak+1bBkck+1 (regra 3 k vezes)
k
⇒ ak+1bk+1ck+1 (regra 4 k vezes)
Isso mostra que se pode derivar palavras da forma ak+1bk+1ck+1, para k ≥ 0, em
k + 1+ (1 + 2 + · · ·+ k) + k = (2k + 1) + k(k + 1)/2 = k(k + 5)/2 + 1 passos. Tem-se,
então, que:
P
(n−1)(n+4)/2+1
=⇒ anbncn para n ≥ 1.
Logo, conclui-se que {anbncn |n ≥ 1} ⊆ L(H).
Para a gramática H do Exemplo 13, analisando-se as alternativas posśıveis ao es-
quema de derivação apresentado no Exemplo 15, pode-se notar que, qualquer que seja
a ordem de aplicação das regras 3 e 4, não se consegue gerar outras sentenças que não
sejam as da forma anbncn para n ≥ 1. Logo, L(H) = {anbncn |n ≥ 1}
A mesma linguagem pode ser gerada por inúmeras gramáticas. Duas gramáticas
G e G′ são ditas equivalentes quando L(G) = L(G′). O problema de modificar uma
gramática de forma que ela atenda a certos requisitos, mas sem alterar a linguagem
gerada pela mesma, é importante em determinados contextos, por exemplo, na cons-
trução de analisadores sintáticos de linguagens. Algumas técnicas de manipulação de
gramáticas serão abordadas na Seção 3.4.3.
Na gramática a seguir, assim como nas dos Exemplos 12 e 14, as regras têm a carac-
teŕıstica de que os seus lados esquerdos contêm apenas e tão-somente uma variável. Esse
tipo de gramática, muito importante em termos práticos, será estudado na Seção 3.4.
Exemplo 16 Seja a gramática G = (V,Σ, R,E), em que:
• V = {E,T,N,D};
• Σ = {+,−, (, ), 0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
• R contém as regras:
E → E + T |E − T |T
T → (E) |N
N → DN |D
Newton José Vieira Caṕıtulo 1: Conceitos preliminares 19
D → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
A gramática G gera expressões aritméticas contendo números naturais na base decimal,
operadores de soma e subtração e parênteses. Por meio das três regras com E do lado
esquerdo, pode-se gerar uma sequência de somas e/ou subtrações de T s (termos); por
exemplo:
E ⇒ E + T (regra E → E + T )
⇒ E − T + T (regra E → E − T )
⇒ E − T − T + T (regra E → E − T )
⇒ T − T − T + T (regra E → T )
Observe como as regras são recursivas à esquerda, levando à produção de uma sequên-
cia da direita para a esquerda. Entretanto, as regras responsáveis pela produção dos
números das expressões são recursivas à direita, redundando na produção de números
da esquerda para a direita. Por exemplo, para gerar um número de quatro d́ıgitos,
pode-se derivar:
N ⇒ DN (regra N → DN)
⇒ DDN (regra N →DN)
⇒ DDDN (regra N → DN)
⇒ DDDD (regra N → D)
e, em seguida, derivar os quatro d́ıgitos usando-se as regras com D do lado esquerdo.
Observe também que a geração de parênteses se dá por recursão (no caso, indireta), a
qual não pode ser classificada como recursão à esquerda nem à direita. Por exemplo,
na derivação:
E ⇒ E + T (regra E → E + T )
⇒ T + T (regra E → T )
⇒ (E) + T (regra T → (E))
a variável E aparece (recursivamente) na forma sentencial entre “(” e “)”.
Exerćıcios
1. 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) 0101;
20 Editora Thomson Introdução aos fundamentos da computação
d) 0011.
Que linguagem é gerada?
2. Seja a gramática G = ({A,B}, {a, b}, R,A) em que R é constitúıdo pelas quatro
regras:
A → aA |B
B → bB |λ
Apresente um esquema de derivação que mostre como derivar qualquer palavra
de L(G). Expresse o que é L(G) de forma bem concisa utilizando a notação
introduzida na Seção 1.2.
3. Seja a gramática H = ({P,A,B}, {a, b}, R, P ) em que R tem as regras:
P → AB
A → aA |λ
B → bB |λ
Mostre que H gera a linguagem do Exerćıcio anterior.
4. Construa gramáticas para as seguintes linguagens:
a) {0}{0, 1}∗{11};
b) {λ, 0}{11}∗{λ, 0};
c) {w ∈ {a, b}∗ | o número de as em w é par};
d) {anbn |n ∈ N};
e) {w ∈ {a, b}∗ |w = wR};
f) {w ∈ {a, b}∗ |w = wR e w não contém śımbolos consecutivos idênticos};
g) {anbncndn |n ∈ N}.
5. Para as gramáticas dos itens (d) e (e) do exerćıcio anterior, determine o número
de passos necessário para gerar uma palavra de tamanho n.
6. Considere as gramáticas desenvolvidas no Exerćıcio 4. A partir delas, construa
gramáticas que gerem:
a) A concatenação das linguagens dos itens (c) e (d);
b) A união das linguagens dos itens (d) e (e);
c) O fecho de Kleene da linguagem do item (f).
7. Diga que linguagens são geradas pelas gramáticas:
a) G1 = ({A}, {0, 1}, R1, A), sendo R1 constitúıdo de:
A → 0A |A0 | 1
b) G2 = ({B}, {0, 1}, R2, B), sendo R2 constitúıdo de:
Newton José Vieira Caṕıtulo 1: Conceitos preliminares 21
B → 0B00 | 1
c) G3 = ({S,A,B}, {0, 1}, R3 , S), sendo R3 constitúıdo de:
S → AA |B
A → 0A |A0 | 1
B → 0B00 | 1
8. Identifique as linguagens geradas pelas gramáticas:
a) G1 = ({P,X}, {a, b}, R1 , P ).
R1: P → aX | bP |λ
X → aP
b) G2 = ({P,A}, {a, b}, R2 , P ).
R2: P → aPa |A
A → bA | b
c) G3 = ({A,B}, {0, 1}, R3 , A).
R3: A → 0A |B
B → B1 | 01
d) G4 = ({P,X}, {a, b}, R4 , P ).
R4: P → aP |Xb |λ
X → aP
e) G5 = ({P,X}, {a, b}, R5 , P ).
R5: P → aaP |Xb |λ
X → aP
f) G6 = ({A,B}, {0, 1}, R6 , A).
R6: A → 0A0 |B1
B → 1B1 |λ
g) G7 = ({P}, {0, 1}, R7, P ).
R7: P → 0P1 | 1P0 |λ
h) G8 = ({A,X}, {0, 1}, R8 , A).
R8: A → XA |X
X → 0X1 |λ
i) G9 = ({X,B}, {a, b, c}, R9 ,X).
R9: X → aBX | abc
Ba → aB
Bb → bB
Bc → bcc
j) G10 = ({X,A,#}, {a, b}, R10 ,X).
R10: X → aAX |#
22 Editora Thomson Introdução aos fundamentos da computação
Aa → aA
Ab → bA
A# → b#a
# → λ
1.4 Problemas de Decisão
Ao longo deste texto serão tratados vários problemas cujas respostas são do tipo sim
ou não. Nesta seção, é apresentada uma introdução genérica e informal a esse tipo de
problema.
Definição 6 Um problema de decisão (PD) é uma questão que faz referência a um
conjunto finito de parâmetros e que, para valores espećıficos dos parâmetros, tem como
resposta sim ou não.
Seguem alguns exemplos.
Exemplo 17 São exemplos de problemas de decisão:
a) determinar se o número 123654789017 é um número primo;
b) determinar se um número natural n é um número primo;
c) determinar se existe um ciclo em um grafo G;
d) determinar se uma palavra w é gerada por uma gramática G.
O primeiro PD não tem parâmetros, o segundo e o terceiro possuem um parâmetro
cada um, um número natural n e um grafo G, e o quarto tem dois parâmetros, uma
palavra w e uma gramática G.
A questão referente a um PD pode ser vista como representando um conjunto
de questões, uma para cada combinação posśıvel dos valores que os parâmetros po-
dem assumir. Cada questão obtida dando aos parâmetros valores espećıficos, ou seja,
instanciando-se os parâmetros, é dita ser uma instância do PD. Em particular, um PD
sem parâmetros contém uma única instância.
Exemplo 18 O PD (b) do Exemplo 17, “determinar se um número natural n é um
número primo”, é constitúıdo pelo seguinte conjunto infinito de questões:
• determinar se 0 é um número primo;
• determinar se 1 é um número primo;
• determinar se 2 é um número primo;
• e assim por diante.
O PD “determinar se 123654789017 é um número primo” é constitúıdo por uma única
instância, a qual é instância também do PD “determinar se um número natural n é um
número primo”.
Newton José Vieira Caṕıtulo 1: Conceitos preliminares 23
Para cada instância de um PD, existe uma resposta correta, sim ou não. Uma
solução para um PD, denominada procedimento de decisão, é um algoritmo que, para
qualquer instância do PD, determina a resposta correta. Informalmente, um algoritmo
é uma sequência finita de instruções, cada uma executável por uma máquina em tempo
finito, e cada uma produzindo o mesmo resultado para os mesmos dados. Adiante, se-
rá apresentada uma proposta de formalização do conceito de algoritmo mediante a
chamada hipótese de Church-Turing. Até lá, fica-se com esta definição informal.
Um PD que tem solução é dito ser decid́ıvel, e um PD que não tem solução, inde-
cid́ıvel.
Pelo exposto anteriormente, se um PD tem um conjunto finito de instâncias, então
ele é decid́ıvel: pode-se construir um algoritmo que simplesmente consulte uma “tabela
de respostas” pré-computadas. Assim, o estudo de PDs torna-se mais interessante para
PDs com uma infinidade de instâncias.
Observe que uma solução para o PD mais geral “determinar se um número natural
n é um número primo” serve também para solucionar o PD mais restrito “determinar
se 123654789017 é um número primo”. Neste caso, ambos os problemas têm solução.
Contudo, mesmo que não existisse solução para o primeiro PD, haveria solução para o
segundo! Mesmo que não se soubesse a resposta! Para ressaltar esse ponto, observe a
famosa conjectura de Fermat, que só foi provada recentemente, 350 anos após enunciada:
Para qualquer número natural n ≥ 3 não existem números naturais a, b e c
tais que an + bn = cn.
O problema de determinar se esta conjectura está correta é um PD que tem solução,
pois é um PD sem parâmetros e, portanto, constitúıdo por uma única instância. Mesmo
na época em que a conjectura não tinha sido provada, o PD respectivo já tinha solução,
embora desconhecida... Considere os dois algoritmos: “retorne sim” e “retorne não”;
um deles é a solução.
Um PD obtido de outro, P , restringindo-se o conjunto de valores posśıveis de um ou
mais parâmetros de P , é dito ser uma restrição de P . Assim, por exemplo o PD “de-
terminar se 123654789017 é um número primo” é uma restrição de “determinar se um
número natural n é um número primo”. É evidente que, se um PD tem solução, então
suas restrições também têm. No entanto, pode acontecer de uma ou mais restrições de
um PD terem soluções e o PD não ter. Por exemplo, a restrição do PD “determinar se
uma palavra w é gerada por uma gramática G”:
“determinar se uma palavra w é gerada por G0”,
em que G0 é uma gramática na qual o lado esquerdo de cada regra é constitúıdo por
uma variável,10 tem solução, mas, como será mostrado à frente, o PD original não
tem solução.
Existe uma relação estreita entre problemas de decisão e linguagens. Em primeiro
lugar, uma solução de um PD, sendo um algoritmo, deve poder ser expressa em alguma
linguagem. Esta, tipicamente é uma linguagem de programação, mas, em prinćıpio,
10 Esse tipo de gramática será definido na Seção 3.4 como uma gramáticalivre do contexto.
24 Editora Thomson Introdução aos fundamentos da computação
pode ser qualquer linguagem projetada para se expressar algoritmos para uma certa
noção espećıfica de algoritmo. Por outro lado, há um outro tipo de linguagem que
terá sua importância quando for abordado o problema da decidibilidade. Para que as
instâncias de um problema sejam submetidas a um algoritmo elas devem ser expressas
por meio de palavras em uma linguagem. Sendo Σ o alfabeto de tal linguagem, ela
seria então LP = {w ∈ Σ
∗ |w representa uma instância de P} (nada impede que uma
mesma instância seja representada por várias palavras da linguagem). Para cada pala-
vra de LP , a resposta pode ser “sim” ou “não” para a instância respectiva. Uma outra
linguagem, subconjunto de LP , também importante, como se verá depois, é aquela
constitúıda apenas das palavras que representem instâncias para as quais a resposta é
“sim”: LsP = {w ∈ LP | a resposta para a instância representada por w é “sim”}. Note
que a resposta para a instância representada por w é “sim” se e somente se w ∈ LsP .
Logo determinar se o PD P tem solução é equivalente a determinar se o seguinte PD
tem solução: dada uma palavra w ∈ LP , determinar se w ∈ L
s
P . Segue um exemplo.
Exemplo 19 Seja PP o problema de determinar se n ∈ N é primo. Representando-se
cada instância por uma palavra w ∈ {0, 1}+, de forma que w seja uma das repre-
sentações em binário de um número natural, aqui referido por η(w), tem-se:
• LPP = {0, 1}
+;
• LsPP = {w ∈ {0, 1}
+ | η(w) é primo}.
Com isto, n é primo se e somente se w ∈ LsPP , em que w é tal que η(w) = n.
Exerćıcio
1. Sejam os PDs:
a) determinar se um número natural n, para 1 ≤ n ≤ 200, é um número primo;
b) dada uma equação do segundo grau de coeficientes a, b e c, determinar se
suas ráızes são ambas reais, se cada um dos coeficientes é um número natural
entre 10 e 20 (exclusive);
c) dada uma equação do segundo grau de coeficientes a, b e c, determinar se
suas ráızes são ambas reais, se seus coeficientes podem ser números reais
quaisquer;
d) dada uma fórmula da lógica de predicados, determinar se ela é válida;
e) dados dois conjuntos finitos, determinar se eles são disjuntos;
f) determinar se uma árvore A tem altura menor ou igual a n;
g) determinar se uma palavra w é paĺındromo, se w ∈ {0, 1}∗.
Dizer quantos parâmetros e quantas instâncias tem cada um.
2. Dentre os PDs a seguir, quais são decid́ıveis?
a) Determinar se existe vida extraterrestre.
Newton José Vieira Caṕıtulo 1: Conceitos preliminares 25
b) Determinar se para todo número natural n existe um par de números primos
gêmeos maior que n. (m e n são primos gêmeos sse são ambos primos e
|m − n| = 2. Atualmente não se sabe se o conjunto dos primos gêmeos é
finito ou não.)
c) Dado um número natural n, determinar se existe um par de números pri-
mos gêmeos maior que n. (Primos gêmeos são como definidos na questão
anterior.)
d) Dado um conjunto finito de números naturais, determinar se ele contém
algum número primo.
e) Dado um programa em C (sem entrada) que tenha no máximo 1GB, deter-
minar se ele para.
f) dada uma equação do segundo grau de coeficientes a, b e c, determinar se
suas ráızes são ambas reais, se cada um dos coeficientes é um número natural
entre 10 e 20 (exclusive);
g) dada uma equação do segundo grau de coeficientes a, b e c, determinar se
suas ráızes são ambas reais, se seus coeficientes podem ser números reais
quaisquer;
h) Dados dois conjuntos finitos, determinar se eles são disjuntos.
3. Diz-se que um PD P é redut́ıvel a um PD Q, se existe um algoritmo R que,
recebendo x como entrada, produz um resultado y tal que a resposta a P para a
entrada x é idêntica ou complementar11 à resposta a Q para a entrada y, qualquer
que seja a entrada x. Diz-se, com isso, que o algoritmo R pode ser usado para
reduzir o problema P ao problema Q.
Seja D um PD decid́ıvel e I um PD indecid́ıvel. O que se pode dizer de um PD
X, com relação à sua decidibilidade, se:
a) D é redut́ıvel a X?
b) X é redut́ıvel a D?
c) I é redut́ıvel a X?
d) X é redut́ıvel a I?
4. Considere o problema de redução de um problema de decisão a outro, como
descrito no exerćıcio anterior.
a) Dê um exemplo de redução de um problema decid́ıvel a um problema inde-
cid́ıvel.
b) Explique porque um problema indecid́ıvel não pode ser reduzido a um pro-
blema decid́ıvel.
11 A resposta complementar a sim é não, e a não é sim.
26 Editora Thomson Introdução aos fundamentos da computação
1.5 Exerćıcios Adicionais
1. Seja um alfabeto qualquer Σ. Prove que Σ∗ é enumerável. Prove que P(Σ∗)
não é enumerável. Ou seja, qualquer linguagem é enumerável, mas o conjunto
de todas as linguagens não! Consequência: como o conjunto dos compiladores é
enumerável, existem linguagens para as quais não há compiladores.
2. Faça uma definição recursiva da função v : {0, 1}∗ → N tal que v(w) é o número
natural representado por w na base 2. Por exemplo, v(01) = 1, v(101) = 5,
v(0010) = 2 etc.
3. Seja o alfabeto Σ = {a, (, ),+,−}. Segue uma definição recursiva de uma lingua-
gem E, de expressões aritméticas:
a) a ∈ E;
b) se x, y ∈ E então (x+y) ∈ E e (x−y) ∈ E;
c) só pertencem a E as palavras especificadas por (a) e (b).
Prove que nenhuma palavra de E contém a subpalavra )(.
4. Seja a seguinte definição recursiva da linguagem L sobre o alfabeto {0, 1}:
a) λ ∈ L;
b) se x ∈ L, então 0x ∈ L e x1 ∈ L;
c) nada mais pertence a L.
Que linguagem é L? Prove sua resposta.
5. Considere a linguagem L = {ab}∗{ba}∗.
a) Faça uma definição recursiva de L.
b) Construa uma gramática que gere L.
c) Em quantos passos é derivada uma palavra de n śımbolos na gramática
constrúıda?
6. Faça definições recursivas das seguintes linguagens:
a) {w ∈ {0, 1}∗ | |w| é par};
b) {w ∈ {0, 1}∗ |w é paĺındromo};
c) {w ∈ {0, 1}∗ |w contém 00};
d) {w ∈ {0, 1}∗ |w não contém 00};
e) {w ∈ {0, 1}∗ |w o número de 0s em w é igual ao de 1s};
f) {0n
2
|n ∈ N}.
7. Sejam Σ = {0, 1}, L1 = Σ{0}Σ
∗ e L2 = Σ
∗{0}Σ∗{0}Σ∗. Para cada linguagem
a seguir, escreva uma propriedade necessária e suficiente para que uma palavra
w ∈ Σ∗ pertença à linguagem. Não é preciso dizer que ela é constitúıda apenas
de 0s e 1s.
Newton José Vieira Caṕıtulo 1: Conceitos preliminares 27
a) L2.
b) L1 ∩ L2.
c) L2 ∩ L1.
d) L1 − (ΣΣ)
∗.
8. Expresse as linguagens a seguir utilizando operações sobre conjuntos finitos de
palavras de {0, 1}∗, se for posśıvel. Se não for, faça uma descrição o mais formal
que conseguir.
a) O conjunto das palavras que têm de 5 a 10 śımbolos.
b) O conjunto das palavras que não tenham 00 como subpalavra, nem 11.
Exemplos: λ, 0, 01, 10, 101.
c) O conjunto das palavras em que as posições ı́mpares só têm 1s. Exemplos:
λ, 101, 111, 1010111011.
d) O conjunto das palavras que contêm um ou dois 1s.
e) O conjunto das palavras de tamanho múltiplo de 3 terminadas em 11.
f) O conjunto das palavras de tamanho par que não contêm 11.
g) O conjunto das palavras em que as posições pares contêm apenas 0s e as
ı́mpares apenas 1s. Exemplos: λ, 1, 10, 101 etc.
h) O conjunto das palavras em que entre cada par de 0s o número de 1s conse-
cutivos é par. Exemplos: λ, 10, 00, 001, 11011001.
i) O conjunto das palavras de tamanho ı́mpar que têm um 1 no meio.
9. Sejam L = {w ∈ {0, 1}∗ |w não termina com 1 nem contém 11} e F = {0, 10}.
Mostre que L = F ∗.
10. Seja L = {w ∈ {0, 1}∗ |w não contém 11}. Mostre que não existe X ∈ {0, 1}∗ tal
que L = X∗.
11. O conjunto das palavras sobre um alfabeto Σ, Σ∗, pode ser definido recursiva-
mente a partir da operação de “justapor um śımbolo à direita” assim:
a) λ ∈ Σ∗;
b) se x ∈ Σ∗ e a ∈ Σ, então xa ∈ Σ∗.
Utilizando essa mesma operação de justapor um śımbolo à direita, defina re-
cursivamente a operação de concatenação. Em seguida, prove por indução que
(xy)z= x(yz) para todo x, y, z ∈ Σ∗.
Usando as operações de justapor um śımbolo à direita e de justapor um śımbolo
à esquerda, defina recursivamente a operação reverso. Em seguida, prove por
indução que (xy)R = yRxR para todo x, y ∈ Σ∗. Para isso, o resultado anterior
pode ser utilizado. Mostre também que se w é paĺındromo, então w = vvR ou
w = vavR para algum v ∈ Σ∗ e a ∈ Σ.
12. Mostre que para quaisquer linguagens A e B (AB)R = BRAR. Observe que, por
definição, XR = {wR |w ∈ X}. Na demonstração você pode usar o fato de que
(xy)R = yRxR para quaisquer palavras x e y.
28 Editora Thomson Introdução aos fundamentos da computação
13. Mostre que se x, y e xy são paĺındromos, então existe uma palavra z e números
naturais k e n tais que x = zk e y = zn.
14. Mostre que se X ⊆ L∗, então (L∗ ∪X)∗ = L∗.
15. Seja LR = {wR |w ∈ L}, em que L é uma linguagem. Para que linguagens L,
LR = L?
16. Prove que L∗ =
⋃
n∈N L
n. (Dica: Para provar que L∗ ⊆
⋃
n∈N L
n, use indução
sobre |w|, e para provar que
⋃
n∈N L
n ⊆ L∗, use indução sobre n.)
17. Prove:
a) L∗L∗ = L∗;
b) (L∗)∗ = L∗;
c) (L1 ∪ L2)
∗L∗1 = (L1 ∪ L2)
∗;
d) (L1 ∪ L2)
∗ = (L∗1L
∗
2)
∗.
18. Mostre que o conjunto Σ∗1Σ
∗
2 é enumerável, sendo que Σ1 e Σ2 são alfabetos.
19. Seja a gramática G = ({P,A,B,D}, {0, 1,#}, R, P ), em que R é:
P → A#B
A → DDA |λ
B → B1 |λ
D → 0 | 1
a) Que linguagem é gerada por G?
b) Quantos passos são necessários para derivar uma palavra em G?
c) Construa uma gramática que gere L(G), porém sem usar regra com o lado
direito igual a λ.
20. Construa gramáticas para as linguagens:
a) {w ∈ {0, 1}∗ |w não contém 00};
b) {0n12n+10n |n ∈ N};
c) {wwR |w ∈ {a, b}∗ e w contém pelo menos um a e um b};
d) {w0w |w ∈ {1, 2}∗};
e) {anbnck | 0 ≤ n < k}.
1.6 Notas Bibliográficas
Para uma leitura complementar sobre lógica matemática orientada para aplicações em
ciência da computação, em ńıvel de graduação, consultar Ben-Ari (2009), Nissanke
(1999), Burke e Foxley (1996) ou Souza (2008). Excelentes introduções à lógica são
as de Hodges (2001), Tarski (1995), Suppes (1957) e Copi (1981). Para aqueles com
propensão a racioćınio de natureza mais abstrata (matemática), há ampla coleção de
Newton José Vieira Caṕıtulo 1: Conceitos preliminares 29
bons livros, dentre os quais indica-se os de Mendelson (1987) e Enderton (2000). Para
os interessados especificamente em aprender as técnicas e estratégias utilizadas para
prova de teoremas, indica-se o excelente livro de Velleman (1994).
Aqueles que querem se aprofundar um pouco mais com relação aos conceitos de con-
juntos, funções e relações, podem consultar Halmos (1991). Outros textos que também
abordam tais assuntos, e que são orientados para estudantes em ńıvel de graduação, são
os de Dean (1997), Rosen (1999), Epp (1990) e Grimaldi (1994), além do já citado livro
de Velleman (1994). Esse último tem também uma excelente introdução aos conceitos
de recursão, indução matemática e conjuntos enumeráveis.
Os livros de matemática discreta mecionados anteriormente têm caṕıtulos com in-
troduções a grafos. Para os que querem se aprofundar um pouco mais, recomenda-se o
livro de West (1996).
As gramáticas foram propostas por Chomsky (1956; 1959).
Vários outros textos que abordam linguagens formais e autômatos contêm caṕı-
tulos com uma revisão dos conceitos apresentados. Dentre eles, podem-se destacar
Hopcroft et al. (2001), Lewis e Papadimitriou (1998), Linz (1997), Martin (1991) e
Moret (1997).