Teoria da Computação: Fundamentos e Objetivos

Prévia do material em texto

Engenheiro de Computação
Mestre em Ciência da Computação
@E-mail: carlos.bruno@estacio.br 
Aula 01
CCT0737 - TEORIA DA COMPUTAÇÃO
CENTRO UNIVERSITÁRIO ESTÁCIO DA AMAZÔNIA
Carlos Bruno Oliveira Lopes
EMENTA
• Linguagens formais (regulares, livres de contexto, sensíveis ao contexto);
• Autômatos finitos determinísticos e não determinísticos;
• Autômatos com pilha;
• Máquinas de Turing;
• Tese de Church;
• Proposições sobre Computabilidade;
• Conceitos básicos de classes de complexidade de linguagens.
2
OBJETIVOS GERAIS
• Obter conhecimentos sobre a teoria da computação a fim de permitir
uma visão ampla dos conceitos e técnicas dessa área que possibilitam o
entendimento de ferramentas e estruturas fundamentais para a
formação em ciência da computação como compiladores e linguagens
de programação;
3
CONTEÚDOS
Unidade 1. FUNDAMENTOS
Alfabetos e Linguagens;
Expressões regulares;
Autômatos finitos deterministas e não-deterministas;
Equivalência entre autômatos;
Linguagens regulares e suas propriedades;
Existência de linguagens não-regulares: teorema do 
bombeamento;
Unidade 2. LINGUAGENS REGULARES E LIVRES DE 
CONTEXTO
Conceito de gramáticas livres de contexto;
Gramáticas regulares;
Autômatos de pilha;
Linguagens livres de contexto e suas propriedades;
Determinismo;
Introdução à análise léxica e sintática;
Unidade 3. MÁQUINA DE TURING
Definição;
Computação com Máquinas de Turing;
Combinação de Máquinas de Turing;
Extensões das Máquinas de Turing;
Máquinas de Turing não-deterministas.
Unidade 4. TEORIA DA COMPUTABILIDADE
A tese de Church;
Funções primitivas recursivas;
Máquinas de Turing universais;
Não computabilidade;
O problema de parada em Máquinas de Turing;
Enumerabilidade, Aceitabilidade e Decidibilidade.
Unidade 5. COMPLEXIDADE COMPUTACIONAL
Máquinas de Turing limitadas em tempo e espaço;
Grau de crescimento de funções;
Simulações limitadas em tempo;
As classes P e NP;
NP-completude;
Hierarquia de complexidade.
4
AVALIAÇÃO
O processo de avaliação será composto de três etapas: Avaliação 1 (AV1),
Avaliação 2 (AV2) e Avaliação 3 (AV3).
Para aprovação na disciplina o aluno deverá:
1. Atingir resultado igual ou superior a 6.0, calculado a partir da média 
aritmética entre os graus das avaliações, sendo consideradas apenas as duas 
maiores notas obtidas dentre as três etapas de avaliação (AV1, AV2 e AV3). A 
média aritmética obtida será o grau final do aluno na disciplina.
2. Obter grau igual ou superior a 4.0 em, pelo menos, duas das três avaliações.
3. Frequentar, no mínimo, 75% das aulas ministradas.
5
BIBLIOGRAFIA BÁSICA
DIVÉRIO, Tiarajú A.; MENEZES, Paulo B. Teoria da Computação: Máquinas
universais e computabilidade. 3. ed. Porto Alegre: Bookman, 2011.
Glenn, J. Ciência da Computação: Uma visão Abrangente. 11 ed.. Porto
Alegre: Bookman, 2013.
MENEZES, Paulo B. Linguagens Formais e Autômatos. 6a. ed. Porto Alegure:
Bookman, 2011.
6
BIBLIOGRAFIA COMPLEMENTAR
AHO, Alfred V.; SETHI, Ravi; ULLMAN, Jeffrey D. Compiladores: princípios, técnicas e ferramentas. 2. ed.
Rio de Janeiro: LTC, 2008.
CARVALHO, André C. P. L. F.; LORENA, Ana C. Introdução à Computação: Hardware, Software e Dados. 1.
ed. Rio de Janeiro: LTC, 2017.
Fedeli, R. D. Polloni, E. G. F. Peres, F. E. Introdução à Ciência da Computação. 2. ed. São Paulo: Cengage
Learning, 2010.
LOUDEN, Kenneth C. Compiladores: princípios e práticas. São Paulo: Cengage Learning, 2004.
SANTOS, Pedro R.; LANGLOIS, Thibault. Compiladores da teoria à prática. 1. ed. Rio de Janeiro: LTC, 2018.
7
8
Fundamentos
Ao longo da história da computação três perguntas se destacaram em seus estudos e
desenvolvimento:
• O que é uma solução computável?
• Quais são os limites do que pode ser computado?
• Existem problemas sem solução computacional?
Elas caracterizam boa parte do escopo da teoria da computação
A teoria da computação estuda modelos de computação suficientemente genéricos para 
especificar qualquer função computável, assim como, explora os limites do que pode ser 
computado.
9
Fundamentos
David Hilbert (1862-1943): Problema de Decisão
“Encontrar um algoritmo que recebe como entrada a descrição de uma linguagem formal e uma sentença nesta linguagem e 
tem como saída “verdadeiro” ou “falso” dependendo se a sentença de entrada é verdadeira ou falsa.”
• Problema de decisão lógica de primeira ordem. Objetivo determinar se um sentença na lógica de primeira ordem é válida ou não.
Kurt Gödel (1906-1978): Teorema da não completude
“Demonstra que qualquer sistema axiomático que define a multiplicação e a adição no conjunto dos números naturais não 
pode ser simultaneamente completo e consistente: se é consistente, existem proposições que não podem ser verificadas 
nesta axiomatização (incompleto); se for completo, não poderá́ validar a si mesmo, (inconsistente)”
• Primeiro a identificar um formalismo para definir a noção de procedimento efetivo.
1928, Devid Hilbert
 Problema de Decisão
1931, Kurt Gödel
 Teorema da não completude
1936, Alonzo Church
 ● cálculo Lamba
 funções recursivas● 
, Alan Turing1936
 Máquina de Turing
1943, Sistema canônico de Post
, Algoritmo de Markov e Linguagem Snobol1954
1963, Máquina de registradores
, RASP (Random Acess Stored Programs)1964
1976, Máquina Norma
Procedimento efetivo: Descrição de todos os procedimentos possíveis que podem ser executados em um
computador por meio de um formalismos
10
Fundamentos
• Essas estudos desenvolveram os principais aspectos da teoria da computação:
• Criando abordagens próximas dos sistemas de computadores modernos;
• Permitindo o entendimento e associação dos problemas abstratos com os problemas típicos da 
ciência da computação atual;
Linguagem é um conceito fundamental em teoria da computação.
• Ela permiti-nos expressar problemas por meio de um desenvolvimento formal 
adequado a computabilidade.
o Ex.: Java, C, Pascal, HTML, etc.
11
Linguagens Formais
• O conteúdo de Linguagens Formais envolve três principais termos:
• Esses termos possuem conceitos próprios que estão relacionados entre si.
Linguagens Gramáticas Autômatos
Linguagens Enumeráveis 
Recursivamente ou Tipo 0
Linguagens Sensíveis ao Contexto 
ou Tipo 1
Linguagens livres de 
Contexto ou Tipo 2
Linguagens 
Regulares ou Tipo 3
Máquina de Turing
Máquina de Turing com fita limitada 
Autômatos à Pilha
Gramáticas Livres de Contexto
Autômatos Finitos 
Expressões Regulares 
Gramáticas Regulares
12
Linguagens Formais
Linguagens Formais construídas respeitam duas
restrições:
1. Sintaxe bem definida: sempre possível verificar se uma
sentença pertence ou não à linguagem
2. Semântica precisa: toda sentença da linguagem possui
um significado único
13
Alfabetos
Toda linguagem formal possui um alfabeto
▪ Conjunto finito e não vazio de símbolos.
O alfabeto de uma linguagem é representado
por Σ (sigma).
Definição Exemplo 01
Σ = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
• Permite representar números naturais na
base decimal
▪ 1
▪ 20
▪ 131
▪ 1235562
14
Alfabetos
Toda linguagem formal possui um alfabeto
▪ Conjunto finito e não vazio de símbolos.
O alfabeto de uma linguagem é representado
por Σ (sigma).
Definição Exemplo 02
Σ = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, "," , −
• Permite representar todos os números reais
na base decimal
▪ 9,80655
▪ -0,05
▪ 1,13
▪ 902
15
Alfabetos
Toda linguagem formal possui um alfabeto
▪ Conjunto finito e não vazio de símbolos.
O alfabeto de uma linguagem é representado
por Σ (sigma).
Definição Exemplo 03
Σ = 0, 1
• Permite representar sequências binárias
(de 0s e 1s)
▪ 0
▪ 10
▪ 101
▪ 110010
16
Alfabetos
Toda linguagem formal possui um alfabeto
▪ Conjunto finito e não vazio de símbolos.
O alfabeto de uma linguagem é representado
por Σ (sigma).
Definição Exemplo 04
Σ = 0
• Permite representar sequências de 0s
▪ 0
▪ 000
▪ 0000
▪ 00000000000000
17
Alfabetos
Toda linguagem formal possui um alfabeto
▪ Conjunto finito e não vazio de símbolos.
O alfabeto de umalinguagem é representado
por Σ (sigma).
Definição Exemplo 05
Σ = 𝑎, 𝑏, 𝑐, 𝑠
• Permite representar algumas palavras
▪ casa
▪ assa
▪ babaca
▪ abacaba
▪ aaaaaaaaaaaaaaaaaaa
18
Palavra
• Uma palavra sobre o alfabeto Σ é uma
sequência finita de símbolos de Σ.
• Tamanho de uma palavra p, representado 
por |p|
▪ Número de símbolos usados na palavra
Ex.:
o p = 0 , então |p| = 1;
o p = 100 , então |p| = 3;
o p = 1011 , então |p| = 4;
• Existe uma palavra vazia, ou seja, sem 
símbolos
▪ Representado por 𝜆 (|p| = 0)
Definição Exemplo
• Σ = 0, 1
▪ 011
▪ 10010
▪ 01001
▪ 010010
• Σ = 𝑎, 𝑏
▪ aab
▪ aba
▪ bbba
Palavras sobre
Palavras sobre
19
Linguagem
Linguagem
Uma linguagem sobre um alfabeto 𝜮 é um subconjunto (possivelmente infinito) de todas as possíveis
palavras sobre Σ.
Uma linguagem define quais palavras sobre Σ são “válidas” segundo algum critério preestabelecido.
Tamanho da Linguagem
O tamanho de uma linguagem L, representado por |L|, é o número de palavras da linguagem (possivelmente
infinito)
20
Linguagem
• Exemplo
Dada a linguagem 𝐿1 defina como “todas as palavras sobre o alfabeto Σ = 0, 1 com no máximo
3 símbolos”, temos:
𝐿1 = {𝜆, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, 111}
Tamanho de 𝐿1 é dado por 𝐿1 = 15
Dada a linguagem 𝐿2 definida como “todas as palavras sobre o alfabeto Σ = 𝑎, 𝑏, 𝑐 com dois
símbolos e que não começam com a”, temos:
𝐿2 = 𝑏𝑎, 𝑏𝑏, 𝑏𝑐, 𝑐𝑎, 𝑐𝑏, 𝑐𝑐
Tamanho de 𝐿2 é dado por 𝐿2 = 6
Dada a linguagem 𝐿3 definida como “todos os números binários com um dígito que começam 
com 0 e terminam com 1”
𝐿3 = ∅
Tamanho de 𝐿3 é dado por 𝐿3 = 0
21
Linguagem
• “A linguagem dos números naturais é constituída por todas as palavras sobre o
alfabeto Σ = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 que possuem pelo menos um dígito”
• “Uma palavra p sobre o alfabeto Σ = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 representa um número 
natural se, e somente se, |p| > 0”
• A linguagem dos números naturais é definida por 𝐿𝑁 = {
}
p é uma palavra
sobre Σ | p > 0
“Conjunto das palavras p sobre o alfabeto Σ tal que o tamanho de p é maior do que zero”
22
Linguagem
• “A linguagem dos números naturais é constituída por todas as palavras sobre o
alfabeto Σ = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 que possuem pelo menos um dígito”
• “Uma palavra p sobre o alfabeto Σ = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 representa um número 
natural se, e somente se, |p| > 0”
• A linguagem dos números naturais é definida por 𝐿𝑁 = {
}
p é uma palavra
sobre Σ | p > 0
“Conjunto das palavras p sobre o alfabeto Σ tal que o tamanho de p é maior do que zero”
Qual o valor de |𝐿𝑁|?
23
Palavra
• O alfabeto Σ = 0,1,2,3,4,5,6,7,8,9, ", ", −
pode representar números reais.
• Algumas palavras sobre Σ são “válidas”,
outras não
• Válidas
▪ 1958
▪ -55
▪ 2,1
▪ -9,44
• Inválidas
▪ -
▪ 1,2,3
▪ 20-7
▪ ,-2
24
Formalização de linguagens
• A linguagem dos números reais é constituída por todas as palavras sobre o alfabeto 
Σ = 0,1,2,3,4,5,6,7,8,9, ",", − que obedeçam às seguintes regras:
1. Possuem pelo menos um dígito 0 a 9 ;
2. Podem possuir um único hífen − , desde que seja o primeiro símbolo;
3. Possuem no máximo uma vírgula , , desde que seja precedida e seguida por pelo menos um 
dígito.
o Difícil de entender
o Difícil de verificar se está correta
o Difícil de escrever um algoritmo para verificar se uma palavra representa ou não um 
número válido
25
Operações Básicas
• Certas operações permitem a auxiliam na representação conveniente de linguagens
▪ Repetição
▪ Fecho de Kleene e Fecho Positivo de Kleene
▪ Agrupamento
▪ Concatenação
▪ União
▪ Interseção
▪ Subtração
▪ Complemento
26
Repetição
• O operador de repetição aparece como um “expoente” após um símbolo e indica o
número de repetições desse símbolo
Ex.:
o 02 é uma sequência de dois “0”s: 00
o 15 é uma sequência de cinco “1”s: 11111
o z3 é uma sequência de três “z”s: zzz
o k0 é uma sequência de zero “k”s: λ
• Qualquer símbolo repetido zero vezes gera λ (palavra vazia)
• O operador de repetição é muito útil na definição de linguagens: 𝐿 = {𝑎𝑘 | 𝑘 < 5}
27
Repetição
• O operador de repetição aparece como um “expoente” após um símbolo e indica o número
de repetições desse símbolo
Ex.:
o 02 é uma sequência de dois “0”s: 00
o 15 é uma sequência de cinco “1”s: 11111
o z3 é uma sequência de três “z”s: zzz
o k0 é uma sequência de zero “k”s: λ
• Qualquer símbolo repetido zero vezes gera λ (palavra vazia)
• O operador de repetição é muito útil na definição de linguagens: 𝐿 = {𝑎𝑘 | 𝑘 < 5}
“Conjunto de sequências de a’s dado que tenham menos de 5 letras”
𝐿 = 𝜆, 𝑎, 𝑎𝑎, 𝑎𝑎𝑎, 𝑎𝑎𝑎𝑎
28
Repetição
• O operador de repetição também pode ser aplicado sobre conjuntos (neste caso,
gera-se conjuntos de palavras)
o 𝐿 = 0, 1 2 é o conjunto de todas as palavras sobre {0, 1} que possuem tamanho 2
▪ 𝐿 = 00, 01, 10, 11
o 𝐿 = 𝑎, 𝑏 3 é o conjunto de todas as palavras sobre {a, b} que possuem tamanho 3
▪ 𝐿 = 𝑎𝑎𝑎, 𝑎𝑎𝑏, 𝑎𝑏𝑎, 𝑎𝑏𝑏, 𝑏𝑎𝑎, 𝑏𝑎𝑏, 𝑏𝑏𝑎, 𝑏𝑏𝑏
o 𝐿 = 0, 1 0 é o conjunto de todas as palavras sobre {0, 1} que possuem tamanho 0
▪ 𝐿 = 𝜆
• Só existe uma palavra de tamanho 0 (λ), independentemente do alfabeto!
29
Repetição
Exemplo 01
𝐿 = {p ∈ 0,1 𝑛 | 𝑛 ≤ 2}
“Conjunto das palavras sobre o alfabeto {0, 1} dado que o número de símbolos de {0,1} é 
no máximo 2”
ou
“Conjunto de palavras sobre {0,1} com no máximo dois dígitos”
𝐿 = 𝜆, 0, 1, 00, 01, 10, 11
30
Repetição
Exemplo 01
𝐿 = {p ∈ 0,1 𝑛 | 𝑛 ≤ 2}
“Conjunto das palavras sobre o alfabeto {0, 1} dado que o número de símbolos de {0,1} é no máximo 2”
ou
“Conjunto de palavras sobre {0,1} com no máximo dois dígitos”
𝐿 = 𝜆, 0, 1, 00, 01, 10, 11
Exemplo 02
𝐿 = {p ∈ 0,1 𝑛 | 𝑛 > 0}
“Conjunto das palavras sobre o alfabeto {0,1} com pelo menos um símbolo”
• Pode ser lido como “Conjunto de números binários”.
• Note que esta linguagem possui infinitas palavras, i.e., 𝐿 = ∞
31
Fecho de Kleene
• As repetições “zero ou mais vezes” e “uma ou mais vezes” são tão comuns que há
operadores específicos para elas:
o O Fecho de Kleene, representado por “elevado a asterisco”, aplicado a um conjunto e significa “repetido
zero ou mais vezes”
𝐿∗ = ራ
𝑛 ∈ ℕ
𝐿𝑛
Exemplos:
▪ 𝐿 = 𝑠 ∗, ou seja, 𝐿 = {𝜆, 𝑠, 𝑠𝑠, 𝑠𝑠𝑠, 𝑠𝑠𝑠𝑠, 𝑠𝑠𝑠𝑠𝑠, … }
▪ 𝐿 = 𝑎, 𝑏, 𝑐 ∗, ou seja, 𝐿 = {p ∈ 𝑎, 𝑏, 𝑐 𝑛 | 𝑛 ≥ 0} ∴
𝐿 = 𝜆, 𝑎, 𝑏, 𝑐, 𝑎𝑎, 𝑎𝑏, 𝑎𝑐, 𝑏𝑎, 𝑏𝑏, 𝑏𝑐, 𝑐𝑎, 𝑐𝑏, 𝑐𝑐, 𝑎𝑎𝑎, 𝑎𝑎𝑏, …
o Ou seja, sequências arbitrárias de 0 e 11, logo, neste linguagem o 1 nunca aparece sozinho.
32
Fecho de Kleene
• É comum o Fecho de Kleene aplicado diretamente ao alfabeto 𝐿 = Σ∗
Significando “a linguagem contendo todas as palavras sobre o alfabeto Σ”
FECHO POSITIVO DE KLEENE
• O símbolos do fecho é “elevado a mais”;
• Se aplica a um conjunto repetido uma ou mais vezes o seu alfabeto;
𝐿+ = ራ
𝑛 ∈ ℕ − 0
𝐿𝑛
Exemplo:
▪ 𝐿 = 0 + ∴ 𝐿 = 0, 00, 000, 0000, 00000,…
▪ 𝐿 = 0,1 + ∴ 𝐿 = {p ∈ 0,1 𝑛 | 𝑛 ≥ 1} e 𝐿 = {p ∈ 0,1 𝑛 | 𝑛 > 0}
o é uma representação concisa do conjunto de números binários!
▪ 𝐿 = 0,11 + ∴ 𝐿 = 0, 11, 00, 011, 110, 1111, 000, 0011,…
▪ 𝐿 = 𝜆, 0,11 +] ∴ 𝐿 = 𝜆, 0, 11, 00, 011, 110, 1111, 000, 0011,…
33
Fecho de Kleene
Casos interessantes:
• 𝐿 = ∅, então 𝐿∗ = {𝜆}
• 𝐿 = ∅, então 𝐿+ = ∅
• 𝐿 = 𝜆 , então 𝐿∗ = 𝜆
• 𝐿 = 𝜆 , então 𝐿+ = 𝜆
Em gera,
• 𝜆 ∈ 𝐿, então 𝜆 ∈ 𝐿+, caso contrário 𝜆 não pertence a 𝐿+.
34
Concatenação
• A concatenação de duas palavras é a palavra formada pelos símbolos da primeira
palavra seguidos dos símbolos da segunda palavra.
o A concatenação de duas palavras p e q é escrita pq;
Exemplos:
▪ 𝑝 = 1 e 𝑞 = 0 ∴ 𝑝𝑞 = 10
▪ 𝑟 = 1101 e 𝑠 = 01 ∴ 𝑟𝑠 = 110101
▪ 𝑚 = 𝑝𝑎𝑙𝑎 e 𝑛 = 𝑣𝑟𝑎 ∴ 𝑚𝑛 = 𝑝𝑎𝑙𝑎𝑣𝑟𝑎
▪ 𝑎 = 𝑎𝑎𝑏𝑎 e 𝑏 = 𝜆 ∴ 𝑎𝑏 = 𝑎𝑎𝑏𝑎
▪ 𝑐 = 𝜆 e 𝑑 = 𝜆 ∴ 𝑐𝑑 = 𝜆
35
Concatenação
• Concatenação de duas linguagens 𝐿1 e 𝐿2 é alinguagem contendo todas as
concatenações de cada palavra de 𝐿1 com cada palavra de 𝐿2.
o 𝐿1𝐿2 = 𝑝1𝑝2 para cada 𝑝1 ∈ 𝐿1 e 𝑝2 ∈ 𝐿2
Exemplos:
▪ 𝐿1 = 𝑎, 𝑏, 𝑐 e 𝐿2 = 𝑥, 𝑦 ∴ 𝐿1𝐿2 = {𝑎𝑥, 𝑎𝑦, 𝑏𝑥, 𝑏𝑦, 𝑐𝑥, 𝑐𝑦}
▪ 𝐿1 = 0, 00 e 𝐿2 = 𝜆, 1 ∴ 𝐿1𝐿2 = 0, 01, 00, 001
▪ 𝐿1 = {𝜆, 0} e 𝐿2 = 𝜆, 0 ∴ 𝐿1𝐿2 = {𝜆, 0, 00}
▪ 𝐿1 = 0
∗ e 𝐿2 = 𝜆, 1 ∴ 𝐿1𝐿2 = 𝜆, 1, 0, 01, 00, 001,…
▪ 𝐿1 = 0
∗ e 𝐿2 = 1
∗ ∴ 𝐿1𝐿2 = ?
36
Concatenação
• Se uma das linguagens concatenadas for vazia, o resultado também é um conjunto
vazio!
Exemplos:
o 𝐿1 = 𝑎, 𝑏, 𝑐 e 𝐿2 = ∅, 𝐿1𝐿2 = ∅
o 𝐿1 = ∅ e 𝐿2 = 𝜆 , 𝐿1𝐿2 = ∅
o 𝐿1 = ∅ e 𝐿2 = 0,1 , 𝐿1𝐿2 = ∅
o 𝐿1 = ∅ e 𝐿2 = ∅, 𝐿1𝐿2 = ∅
Cuidado! A linguagem  é diferente da linguagem {λ}!
37
Agrupamento
• O agrupamento é uma forma conveniente de especificar que uma operação de repetição se aplica sobre
uma sequência de outras operações;
• O agrupamento é representado por um par de parênteses em torno da sequência de símbolos: (sequência)
Exemplos:
▪ 𝐿1 = 𝑎 𝑎, 𝑏
2
o Linguagem formada por duas vezes a concatenação 𝑎 𝑎, 𝑏 ∴ 𝐿2 = {𝑎𝑎𝑎𝑎, 𝑎𝑎𝑎𝑏, 𝑎𝑏𝑎𝑎, 𝑎𝑏𝑎𝑏}
▪ 𝐿2 = 𝑎 𝑏
0
o Linguagem formada por zero vezes a concatenação 𝑎 𝑏 ∴ 𝐿2 = {𝜆}
▪ 𝐿4 = 𝑎, 𝑏 𝑐, 𝑑
∗
o Linguagem formada pelo fecho de Kleene sobre a concatenação 𝑎, 𝑏 𝑐, 𝑑 ∴ 𝐿4 =
𝜆, 𝑎𝑐, 𝑎𝑑, 𝑏𝑐, 𝑏𝑑, 𝑎𝑐𝑎𝑐, 𝑎𝑐𝑎𝑑, 𝑎𝑐𝑏𝑐, 𝑎𝑐𝑏𝑑, 𝑎𝑑𝑎𝑐, …
o 𝐿4 = {𝑎𝑐, 𝑎𝑑, 𝑏𝑐, 𝑏𝑑} ∗
▪ 𝐿5 = 𝑎, 𝑏 𝑐, 𝑑
+ ∗
o 𝐿5 = {𝜆, 𝑎𝑐, 𝑎𝑑, 𝑎𝑐𝑐, 𝑎𝑐𝑑, … , 𝑏𝑐, 𝑏𝑑, 𝑏𝑐𝑐, 𝑏𝑐𝑑, … , 𝑎𝑐𝑎𝑐𝑐, 𝑎𝑐𝑎𝑐𝑑, 𝑎𝑐𝑎𝑐𝑐𝑐,… , 𝑎𝑐𝑐𝑎𝑐, 𝑎𝑐𝑐𝑎𝑑, 𝑎𝑐𝑐𝑎𝑐𝑐, … }
o Sempre há uma sequência de c’s e/ou d’s após cada a e cada b!
38
União
• União de duas linguagens 𝐿1 e 𝐿2 é a linguagem que contém todas as palavras de 𝐿1 e
𝐿2.
• A união é representada pelo operador ∪
Exemplos:
▪ 𝐿1 = 0, 1, 01 e 𝐿2 = 𝜆, 0, 11 ∴ 𝐿1 ∪ 𝐿2 = 𝜆, 0, 1, 01, 11
▪ 𝐿1 = 𝑎
+ e 𝐿2 = 𝜆 ∴ 𝐿1 ∪ 𝐿2 = 𝑎
∗
▪ 𝐿1 = 0, 1
∗ 0 e 𝐿2 = 0, 1
∗ 1 ∴ 𝐿1 ∪ 𝐿2 = 0, 1
+
39
Interseção
• Interseção de duas linguagens 𝐿1 e 𝐿2 é a linguagem que contém todas as palavras
comuns a 𝐿1 e 𝐿2.
• A interseção é representada pelo operador ∩
Exemplos:
▪ 𝐿1 = 𝜆, 0, 1, 01 e 𝐿2 = 𝜆, 1, 111 ∴ 𝐿1 ∩ 𝐿2 = 𝜆, 1
▪ 𝐿1 = 𝑎𝑎
+ e 𝐿2 = 𝑎
𝑛 | 𝑛 ≤ 5 ∴ 𝐿1 ∩ 𝐿2 = 𝑎𝑎, 𝑎𝑎𝑎𝑎
▪ 𝐿1 = 0, 1
∗ e 𝐿2 = 0
∗ 1 ∗ ∴ 𝐿1 ∩ 𝐿2 = 𝜆, 01
40
Diferença
• Diferença entre duas linguagens 𝐿1 e 𝐿2 é a linguagem que contém as palavras de 𝐿1
que não pertencem a 𝐿2.
• A diferença é representada pelo operador −
Exemplos:
▪ 𝐿1 = 𝜆, 0, 1, 01 e 𝐿2 = 𝜆, 1, 111 ∴ 𝐿1 − 𝐿2 = 0, 01
▪ 𝐿1 = 𝑎𝑎
+ e 𝐿2 = 𝑎
𝑛 | 𝑛 ≤ 5 ∴ 𝐿1 − 𝐿2 = 𝑎
𝑛 | 𝑛 > 5
▪ 𝐿1 = 10
∗ e 𝐿2 = 01
∗ ∴ 𝐿1 − 𝐿2 = 10
+
41
Complemento
• Complemento de uma linguagem 𝐿 é a linguagem que contém as palavras que não 
pertencem a 𝐿.
Σ∗ − 𝐿
• O complemento é representado por uma barra sobre a linguagem ത𝐿 = Σ∗ − 𝐿
Exemplos:
▪ Σ = 𝑎, 𝑏 e 𝐿 = 𝑎 ∗ → ത𝐿 = 𝑎, 𝑏 ∗ 𝑏 𝑎, 𝑏 ∗
▪ Σ = 𝑎, 𝑏 e 𝐿 = 𝑎 + → ത𝐿 = 𝑎, 𝑏 ∗ 𝑏 𝑎, 𝑏 ∗ ∪ 𝜆
▪ Σ = 0, 1 e 𝐿 = 0,1 ∗ 1 → ത𝐿 = 1 , 0 ∗ 0 ∪ 𝜆
42
Exercício
1. Formalize as linguagens abaixo:
a) Conjunto de todos os números binários com tamanho par e cujos dígitos nas posições pares são 
obrigatoriamente 0.
b) Conjunto de todos os números binários que contenham a sequência 0000.
c) Conjunto de todos os números binários que contenham a sequência 0000 pelo menos três vezes.
43
Exercício
1. Formalize as linguagens abaixo:
a) Conjunto de todos os números binários com tamanho par e cujos dígitos nas posições pares são 
obrigatoriamente 0.
𝐿 = 0,1 + 0
b) Conjunto de todos os números binários que contenham a sequência 0000.
𝐿 = 0,1 ∗ 0000 0,1 ∗
c) Conjunto de todos os números binários que contenham a sequência 0000 pelo menos três vezes.
𝐿 = 0,1 ∗ 0000 0,1 ∗ 0000 0,1 ∗ 0000 0,1 ∗
44
Exercício
2. Descreva mais formalmente as seguintes linguagens sobre o alfabeto 0, 1 :
a) o conjunto das palavras com, no mínimo, um 0;
b) o conjunto das palavras de tamanho ímpar;
c) o conjunto das palavras que não têm 00 como prefixo, mas têm 00 como sufixo;
d) o conjunto dos palíndromos que não tenham símbolos consecutivos idênticos;
e) o conjunto das palavras de tamanho par cuja primeira metade é idêntica à segunda;