Capı́tulo 1

Conceitos Preliminares

Inicialmente, na Seção 1.1, será abordado o problema fundamental relativo ao uso

dos computadores, ou seja, o da representação, com o intuito de fazer transparecer a
importância dos conceitos matemáticos a serem introduzidos, tanto no nı́vel de mode-
lagem 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 capı́tulos seguintes, eles serão retomados em conexão com classes especı́ficas
de linguagens. Para finalizar o capı́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 saı́da de
um programa é, muitas vezes, constituı́da por sequências de sı́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 sı́mbolos em uma linguagem de programação, denominada programa; a
entrada para tal programa é constituı́da de sequências de sı́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 saı́da do programa é constituı́da por
sequências de sı́mbolos representando os empregados, o total de horas trabalhadas, a
remuneração etc.
No exemplo do parágrafo anterior, os sı́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 nı́vel, mesmo tais entidades são representadas mediante sequências de
sı́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 Número real na base 10
Presença Vetor de números, um Sequência de números reais 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 “sı́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 sı́mbolos sequências especı́ficas de alguns caracteres
especı́ficos. Podem ser usados como sı́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
sı́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 especı́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
sı́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 sı́mbolos podem ser estudadas matematicamente, ou seja, há
um modelo matemático especialmente desenvolvido para tratar das mesmas. Em tal
modelagem, em geral, os sı́mbolos e as sequências de sı́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 possı́veis, além daquela exibida na Figura 1.1. Por
Newton José Vieira Capı́tulo 1: Conceitos preliminares 3

exemplo:
• As palavras janeiro, fevereiro, . . . , dezembro. Sı́mbolos usados: letras a, b, . . . , z.
• Numerais na base decimal. Sı́mbolos usados: os dı́gitos 0 a 9.
• Numerais na base binária. Sı́mbolos usados: os dı́gitos 0 e 1.
• Numerais em algarismos romanos. Sı́mbolos usados: as letras I, V e X.
• Sequências de um a doze 0s. Sı́mbolos usados: apenas o dı́gito 0.
A linguagem formal usada para representar os meses é, assim, constituı́da de sequências
de alguns sı́mbolos escolhidos. Em nı́vel matemático, uma linguagem formal será defi-
nida, na Seção 1.2, justamente como um conjunto de sequências de sı́mbolos, sendo o
conjunto dos sı́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
sı́mbolos. No caso, pode-se convencionar que os sı́mbolos são os caracteres que podem
aparecer nos programas. Mas, alternativamente, pode-se convencionar que os sı́mbolos
são certas sequências especı́ficas de caracteres. Por exemplo, a palavra “while”, presente
em muitas linguagens de programação, pode ser considerada como uma sequência de 5
sı́mbolos, se se considerar cada caractere como um sı́mbolo, ou como um único sı́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 sı́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 sı́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 sı́mbolos x, determinar se
ela pertence ao conjunto {x ∈ J | x, ao ser executado, emite um sinal sonoro}.

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
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 serão apresentados na Seção A.2.
4 Editora Thomson Introdução aos fundamentos da computação

matemática, que estão revisados 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 é revisado de forma bastante concisa, mas suficiente para dar suporte ao apren-
dizado 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 capı́tulos restantes.

Exercı́cios
1. Encontre uma maneira de representar, por meio de uma sequência dos sı́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 Capı́tulo 5,

é: dado um programa (sem entrada), determinar se ele para. Lá no Capı́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
possı́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 quı́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 princı́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 nı́vel de instruções
de máquina até os nı́veis mais altos da programação de um computador, as linguagens
formais são uma presença constante.
Newton José Vieira Capı́tulo 1: Conceitos preliminares 5

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 linguagem 3 tem um alfabeto associado. Um alfabeto é um conjunto finito não
vazio de elementos que serão referidos como sı́mbolos. Uma palavra 4 sobre um alfabeto
Σ é uma sequência finita de sı́mbolos de Σ.5 O tamanho de uma palavra x, |x|, é o
número de sı́mbolos que a compõem. Em particular, existe a palavra vazia, constituı́da
de zero sı́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.

Seja a um sı́mbolo qualquer. A notação an , em que n ∈ N, será utilizada para

designar a palavra constituı́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,
13 012 = 111011 etc.
Uma linguagem sobre um alfabeto Σ é um conjunto de palavras sobre Σ. Denotando
o conjunto de todas as palavras sobre Σ por Σ∗ , diz-se, então, que uma linguagem sobre
Σ é qualquer subconjunto de Σ∗ .

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

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;
P
• {w ∈ Σ∗ | 1 ≤ |w| ≤ 5}. Contém 5i=1 2i palavras;
• {0n | n é um número primo}. Esta linguagem é infinita, já que existe uma infini-
dade de números primos;
• {0n 1n | n ∈ N}. Linguagem constituı́da de toda palavra de tamanho par cuja
primeira metade só contém 0s e cuja segunda metade só 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 .
Note que, por definição, o complemento de uma linguagem é constituı́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:
• 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 = a1 a2 . . . am e y = b1 b2 . . . bn é a palavra xy =
a1 a2 . . . am b1 b2 . . . 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.
Newton José Vieira Capı́tulo 1: Conceitos preliminares 7

Exemplo 5 Sejam x = aab e y = cc. Então yx = ccaab, x2 = xx = aabaab,

xy 2 = aab(cc)2 = aabcccc, axbbyc = aaabbbccc = a3 b3 c3 , λ(aa)3 λλy 3 λ = a6 c6 .

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 = a1 a2 . . . an , wR , é a sequência dos sı́mbolos de

w na ordem reversa, isto é, wR = an an−1 . . . a1 . Uma palavra w tal que w = wR é
um palı́ndromo. Veja que todo palı́dromo de tamanho par é da forma xxR , e que os
palı́ndromos de tamanho ı́mpar são da forma xaxR , em que a é um sı́mbolo do alfabeto
em questão.

Exemplo 7 Alguns reversos de palavras: λR = λ; aR = a; (c5 )R = c5 , (abcaabb)R =

bbaacba. Alguns palı́ndromos: λ, a, bb, ccc, aba, baab, abcacba.

A concatenação de duas linguagens L1 eL2 é dada por:

L1 L2 = {xy | x ∈ L1 e y ∈ L2 }.

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:
• L1 L1 = {w ∈ {0, 1}∗ | |w| = 10};
• L1 L2 = {w ∈ {0, 1}∗ | o sexto sı́mbolo de w é 0};
• L2 L1 = {w ∈ {0, 1}∗ | w começa com 0 e |w| ≥ 6};
• L2 L2 = {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−1 L para n ≥ 1.
L0 = {λ} porque, segundo o item b desta definição, tem-se que (para n = 1) L1 = L0 L,
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}.
8 Editora Thomson Introdução aos fundamentos da computação

A operação fecho de Kleene de uma linguagem L, L∗ , pode ser definida recursiva-

mente assim:
a) λ ∈ L∗ ;
b) se x ∈ L∗ e y ∈ L, então xy ∈ L∗ .
A partir desta e da definição de concatenação de linguagens, pode-se verificar que:
[
L∗ = Ln .
n∈N

Ou seja, L∗ = L0 ∪ L1 ∪ L2 ∪ · · · = {λ} ∪ L ∪ LL ∪ · · ·. Define-se também o fecho positivo

de Kleene de L: L+ = LL∗ . Pode-se verificar que:
[
L+ = Ln .
n∈N−{0}

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 ∅+ = ∅;
• {λ}∗ = {λ}+ = {λ};
• {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}];
Newton José Vieira Capı́tulo 1: Conceitos preliminares 9

g) o conjunto das palavras com um prefixo de um ou mais 0s seguido (imediatamente)

de um sufixo de 1s de mesmo tamanho: {0n 1n | n ≥ 1};

h) o conjunto das palavras formadas por concatenações de palavras da forma 0n 1n

para n ≥ 1: ∪k≥1 {0n 1n | 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
Capı́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 capı́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 capı́tulos posteriores, elas serão mais bem estudadas e exploradas pouco a pouco.

Exercı́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 sı́mbolos contêm exatamente k ocorrências de #?
d) Quantas palavras de n sı́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);
10 Editora Thomson Introdução aos fundamentos da computação

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 An B, AB n e (AB)n .

8. Sejam A = {λ, a} e B = {a, b}. Determine An B, AB n e An B n . Quantos elemen-

tos tem cada um desses conjuntos?

9. Encontre linguagens A, B e C tais que A(B − C) 6= AB − BC.

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 sı́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;
Newton José Vieira Capı́tulo 1: Conceitos preliminares 11

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 palı́ndromos que não tenham sı́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 sı́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}∗ ;
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 = {w ∈ D | w contém a letra l}.
A partir de tais conjuntos, usando operações sobre conjuntos, concatenações e
fechos de Kleene, descreva o conjunto das palavras:
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 sı́mbolos;
b) o conjunto das palavras que têm de 1 a 200 sı́mbolos;
12 Editora Thomson Introdução aos fundamentos da computação

c) o conjunto das palavras que começam e terminam com o mesmo sı́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) {01n 0 | 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.

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:

Newton José Vieira Capı́tulo 1: Conceitos preliminares 13

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) {0n 1n | n ∈ N};
b) {w ∈ {0, 1}∗ | w contém 00};
c) {w ∈ {0, 1}∗ | w é palı́ndromo};
d) {xx | x ∈ {0, 1}∗ };
e) {00 101 102 1 . . . 0n 1 | 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 capı́tulos, o estudo de gramáticas, associado a classes
especı́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.
O elemento fundamental das gramáticas é a regra.6 Uma regra é um par ordenado
(u, v), tradicionalmente escrito na forma u → v, em que u e v são palavras que podem
conter sı́mbolos de dois alfabetos disjuntos, um com sı́mbolos denominados variáveis,
ou não terminais, e outro com sı́mbolos chamados terminais. As variáveis são sı́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 substituı́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

6
Também chamada regra de produção, ou produção, simplesmente.
14 Editora Thomson Introdução aos fundamentos da computação

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 constituı́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 → λ
Toda derivação deve começar com a forma sentencial constituı́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 a L(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 0n P ;
em seguida,
Newton José Vieira Capı́tulo 1: Conceitos preliminares 15

• aplicar uma única vez a regra 2, produzindo 0n 1X; depois,

• aplicar k ≥ 0 vezes a regra 3, produzindo 0n 11k X; e, finalmente,
• aplicar uma única vez a regra 4, produzindo 0n 11k .

Logo, a linguagem gerada por G é L(G) = {0}∗ {1}+ .

Agora, define-se formalmente o que é gramática. 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 é constituı́do

das regras:

1. P → aP Bc

2. P → abc

3. cB → Bc

4. bB → bb

Toda derivação de H deve começar com a forma sentencial constituı́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 ⇒ aP Bc (regra 1)
⇒ aaP BcBc (regra 1)
⇒ aaabcBcBc (regra 2)
⇒ aaabBccBc (regra 3)
⇒ aaabbccBc (regra 4)
⇒ aaabbcBcc (regra 3)
⇒ aaabbBccc (regra 3)
⇒ aaabbbccc (regra 4)

Logo, a3 b3 c3 ∈ L(H). Na verdade, pode-se mostrar que L(H) = {an bn cn | n ≥ 1}.

16 Editora Thomson Introdução aos fundamentos da computação

É 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 substituı́das por:

P → 0P | 1X

X → 1X | λ

De forma análoga, as regras 1 e 2 da gramática do Exemplo 13 podem ser substituı́das

por:

P → aP Bc | 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
n
substituir uma ocorrência de u em x por v. A relação ⇒ é definida recursivamente
assim, utilizando-se ⇒:
0
a) x ⇒ x para todo x ∈ (V ∪ Σ)∗ ;
n n+1
b) se w ⇒ xuy e u → v ∈ R, então w ⇒ xvy para todo w, x, y ∈ (V ∪ Σ)∗ , n ≥ 0.
n
Quando x ⇒ 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
∗ n
ou mais passos, x ⇒ y, se existe n ≥ 0 tal que x ⇒ y.7 E de x deriva-se y em um ou
+ n
mais passos, x ⇒ y, se existe n ≥ 1 tal que x ⇒ y.8 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 → aP b | Bb
3 e 4. B → Bb | λ

O seguinte esquema de derivação mostra como toda palavra da forma an bn+1+k , para
n ≥ 0 e k ≥ 0 podem ser geradas :
n
P ⇒ an P bn (regra 1 n vezes, n ≥ 0)
⇒ an Bbn+1 (regra 2)
k
⇒ an Bbn+1+k (regra 3 k vezes, k ≥ 0)
⇒ an bn+1+k (regra 4)

7 ∗
Usando a terminologia da Seção A.3, x ⇒ y é o fecho transitivo e reflexivo da relação ⇒.
8 +
x ⇒ y é o fecho transitivo da relação ⇒.
Newton José Vieira Capı́tulo 1: Conceitos preliminares 17

Logo, pode-se derivar qualquer palavra an bn+1+k , para n, k ≥ 0, em n+k +2 passos, ou

seja, qualquer palavra an bm tal que n < m, ou ainda, observando-se que m = n + 1 + k,
m+1
então P =⇒ an bm . E como não é possı́vel gerar outras palavras, conclui-se que L(I) =
{an bm | 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 especı́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:
2
P ⇒ a2 P b2 (regra 1 duas vezes)
⇒ a2 Bb3 (regra 2)
1
⇒ a2 Bb4 (regra 3 uma vez)
⇒ a2 b4 (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).

Exemplo 15 Seja a gramática H do Exemplo 13. As duas derivações demonstram

1 8
que P ⇒ abc e P ⇒ a3 b3 c3 . É fácil mostrar que todas as palavras da forma an bn cn ,
para n ≥ 1, são geradas por H. Para isso, basta notar que tais palavras podem ser
geradas por derivações da forma:
k
P ⇒ ak P (Bc)k (regra 1 k vezes, k ≥ 0)
⇒ ak+1 bc(Bc)k (regra 2)
1
⇒ ak+1 bBcc(Bc)k−1 (regra 3 uma vez)
2
⇒ ak+1 bBBccc(Bc)k−2 (regra 3 duas vezes)
..
.
k
⇒ ak+1 bB k ck+1 (regra 3 k vezes)
k
⇒ ak+1 bk+1 ck+1 (regra 4 k vezes)

Isso mostra que se pode derivar palavras da forma ak+1 bk+1 ck+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:
(n−1)(n+4)/2+1
P =⇒ an bn cn para n ≥ 1.
Logo, conclui-se que {an bn cn | n ≥ 1} ⊆ L(H).
18 Editora Thomson Introdução aos fundamentos da computação

Para a gramática H do Exemplo 13, analisando-se as alternativas possı́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 an bn cn para n ≥ 1. Logo, L(H) = {an bn cn | 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-
terı́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
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)
Newton José Vieira Capı́tulo 1: Conceitos preliminares 19

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 “)”.

Exercı́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;
d) 0011.
Que linguagem é gerada?

2. Seja a gramática G = ({A, B}, {a, b}, R, A) em que R é constituı́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 Exercı́cio anterior.

4. Construa gramáticas para as seguintes linguagens:

20 Editora Thomson Introdução aos fundamentos da computação

a) {0}{0, 1}∗ {11};

b) {λ, 0}{11}∗ {λ, 0};
c) {w ∈ {a, b}∗ | o número de as em w é par};
d) {an bn | n ∈ N};
e) {w ∈ {a, b}∗ | w = wR };
f) {w ∈ {a, b}∗ | w = wR e w não contém sı́mbolos consecutivos idênticos};
g) {an bn cn dn | n ∈ N}.

5. Para as gramáticas dos itens (d) e (e) do exercı́cio anterior, determine o número
de passos necessário para gerar uma palavra de tamanho n.

6. Considere as gramáticas desenvolvidas no Exercı́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 constituı́do de:
A → 0A | A0 | 1
b) G2 = ({B}, {0, 1}, R2 , B), sendo R2 constituı́do de:
B → 0B00 | 1
c) G3 = ({S, A, B}, {0, 1}, R3 , S), sendo R3 constituı́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 → aP a | 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 | λ
Newton José Vieira Capı́tulo 1: Conceitos preliminares 21

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 → 0P 1 | 1P 0 | λ
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 | #
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.
Um problema de decisão (PD) é uma questão que faz referência a um conjunto finito
de parâmetros e que, para valores especı́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.
22 Editora Thomson Introdução aos fundamentos da computação

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 possı́vel dos valores que os parâmetros po-
dem assumir. Cada questão obtida dando aos parâmetros valores especı́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”, é constituı́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” é constituı́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”.

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”. Mas, 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 .
Newton José Vieira Capı́tulo 1: Conceitos preliminares 23

O problema de determinar se esta conjectura está correta é um PD que tem solução,

pois é um PD sem parâmetros e, portanto, constituı́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 possı́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 é constituı́do por
uma variável,9 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 princı́pio,
pode ser qualquer linguagem projetada para se expressar algoritmos para uma certa
noção especı́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
constituı́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 ∈ LsP . 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}+ ;
• LsP P = {w ∈ {0, 1}+ | η(w) é primo}.
Com isto, n é primo se e somente se w ∈ LsP P , em que w é tal que η(w) = n.
9
Esse tipo de gramática será definido na Seção 3.4 como uma gramática livre do contexto.
24 Editora Thomson Introdução aos fundamentos da computação

Exercı́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 raı́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 raı́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 é palı́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.
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 raı́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 raı́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
Newton José Vieira Capı́tulo 1: Conceitos preliminares 25

entrada x é idêntica ou complementar10 à 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 exercı́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.

1.5 Exercı́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.
10
A resposta complementar a sim é não, e a não é sim.
26 Editora Thomson Introdução aos fundamentos da computação

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 sı́mbolos na gramática
construı́da?

6. Faça definições recursivas das seguintes linguagens:

a) {w ∈ {0, 1}∗ | |w| é par};
b) {w ∈ {0, 1}∗ | w é palı́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};
2
f) {0n | 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 é constituı́da apenas
de 0s e 1s.
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 possı́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 sı́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 ∗ .
Newton José Vieira Capı́tulo 1: Conceitos preliminares 27

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 sı́mbolo à direita” assim:
a) λ ∈ Σ∗ ;
b) se x ∈ Σ∗ e a ∈ Σ, então xa ∈ Σ∗ .
Utilizando essa mesma operação de justapor um sı́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 sı́mbolo à direita e de justapor um sı́mbolo
à esquerda, defina recursivamente a operação reverso. Em seguida, prove por
indução que (xy)R = y R xR para todo x, y ∈ Σ∗ . Para isso, o resultado anterior
pode ser utilizado. Mostre também que se w é palı́ndromo, então w = vv R ou
w = vav R para algum v ∈ Σ∗ e a ∈ Σ.

12. Mostre que para quaisquer linguagens A e B (AB)R = B R AR . Observe que, por
definição, X R = {wR | w ∈ X}. Na demonstração você pode usar o fato de que
(xy)R = y R xR para quaisquer palavras x e y.

13. Mostre que se x, y e xy são palı́ndromos, então existe uma palavra z e números
naturais k e n tais que x = z k e y = z n .

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?
S S
16. Prove que L∗ = n∈N Ln . (Dica:
S Para provar que L ∗ ⊆ n
n∈N L , use indução
sobre |w|, e para provar que n∈N Ln ⊆ 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∗1 L∗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
28 Editora Thomson Introdução aos fundamentos da computação

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) {0n 12n+1 0n | n ∈ N};
c) {wwR | w ∈ {a, b}∗ e w contém pelo menos um a e um b};
d) {w0w | w ∈ {1, 2}∗ };
e) {an bn ck | 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 nı́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 raciocı́nio de natureza mais abstrata (matemática), há ampla coleção de
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 nı́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 capı́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 capı́-
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).