Resumo - LINGUAGENS FORMAIS E AUTÔMATAS - Estácio

Prévia do material em texto

Linguagens Formais E Autômatos 
TEMA 2 - CONCEITOS BÁSICOS DE AUTÔMATOS E LINGUAGENS
Módulo 1. Noções e Tecnologias Matemáticas
Definição de Conjunto
✅ Definição de Conjunto
· Um conjunto é uma coleção de elementos.
· Indica-se que um elemento x pertence ao conjunto S escrevendo: x ∈ S.
· Se x não pertence a S, escrevemos: x ∉ S.
· Um conjunto é considerado uma entidade única, sendo caracterizado por sua propriedade.
· Se p é a propriedade definida para os elementos de S, então S é denotado como: 
S = {x : x tem a propriedade p}
📌 Exemplo: Um conjunto pode ser especificado, incluindo algumas descrições de seus elementos, entre chaves.
· S = {x : x é natural}
· Significa que S é o conjunto de todos os números naturais, como S = {0, 1, 2}.
· O que distingue um conjunto de outro são seus elementos.
✅ Formas de Representar Conjuntos
· Usamos chaves “{}” e separamos os elementos por vírgulas.
📌 Exemplo: S = {0, 1, 2}
· Podemos usar reticências “...” para indicar continuação.
📌 Exemplo:
· {a, b, ..., z} → Conjunto de letras minúsculas do alfabeto.
· {1, 3, 5, ...} → Conjunto de números ímpares positivos.
· Também é possível usar notação explícita:
📌 Exemplo: S = {i : i > 0 e i é ímpar}
Lê-se: S é o conjunto de todo i, tal que i é maior que 0 e i é ímpar.
✅ Tipos de Conjuntos
· Finitos: possuem número limitado de elementos.
📌 Ex: S = {0, 1, 2, 3, 4, 5, 6, 7} → |S| = 8 (cardinalidade)
· “|S|”: Representa o tamanho de um conjunto finito e o número de elementos nele contidos 
· Infinitos: têm número ilimitado de elementos.
📌 Ex: S = {..., -3, -2, -1, 0, 1, 2, 3, ...}
· O tamanho “|S|” de um conjunto infinito não pode ser mensurado. 
· Unitário: contém apenas 1 elemento.
📌 Ex: {0}, {f}, {∅}
· 0 ∈ {0},
· f ∈ {f},
· ∅ ∈ {∅}
· Vazio: conjunto que não possui elementos.
· Representado por ∅ ou {} (nunca {∅}).
· Propriedades do conjunto vazio:
· 
· 
· 
· 
✅ Igualdade entre Conjuntos
· Dois conjuntos A e B são iguais se têm exatamente os mesmos elementos.
✅ Operações com Conjuntos
1. União ( ∪ )
Exemplo: A ∪ B = {x : x ∈ A ou x ∈ B}
2. Interseção ( ∩ )
Exemplo: A ∩ B = {x : x ∈ A e x ∈ B}
3. Diferença ( − )
Exemplo: A − B = {x : x ∈ A e x ∉ B}
✅ Propriedades das Operações com Conjuntos
	Propriedade
	União ( ∪ )
	Interseção ( ∩ )
	Idempotência
	A ∪ A = A
	A ∩ A = A
	Comutatividade
	A ∪ B = B ∪ A
	A ∩ B = B ∩ A
	Associatividade
	(A ∪ B) ∪ C = A ∪ (B ∪ C)
	(A ∩ B) ∩ C = A ∩ (B ∩ C)
	Distributividade
	(A ∪ B) ∩ C = (A ∩ C) ∪ (B ∩ C)
	(A ∩ B) ∪ C = (A ∪ C) ∩ (B ∪ C)
	Absorção
	(A ∪ B) ∩ A = A
	(A ∩ B) ∪ A = A
✅ Leis de Morgan
· A − (B ∪ C) = (A − B) ∩ (A − C)
· A − (B ∩ C) = (A − B) ∪ (A − C)
✅ Conjuntos Disjuntos: Os conjuntos A e B são disjuntos ou mutuamente exclusivos quando A∩B=∅.
· A ∩ B = ∅ → A e B não têm nenhum elemento em comum.
✅ Complemento de um Conjunto
· Dado um conjunto universal U, o complemento de Y é: Y̅ = {x : x ∈ U e x ∉ Y}
✅ Produto Cartesiano: O produto cartesiano para dois conjuntos A e B são denotados da seguinte forma:
· Produto entre dois conjuntos A e B: A × B = {(a, b) : a ∈ A e b ∈ B}
📌 Exemplo passo a passo: A × B = ?
A = {2, 3, 4, 5}, B = {4, 5} 
Resultado: A × B = {(2, 4), (2, 5), (3, 4), (3, 5), (4, 4), (4, 5), (5, 4), (5, 5)}. 
✅ Concatenação: A concatenação para dois conjuntos A e B são denotados da seguinte forma:
· A junção dos elementos de A com B, formando pares "colados": AB = {ab : a ∈ A e b ∈ B}
📌 Exemplo passo a passo: AB =?
A = {a, b}, B = {c, d}
Resultado: AB = {ac, ad, bc, bd}
✅ Subconjuntos e Conjunto Potência
· Se S₁ ⊂ S, então todo elemento de S₁ também está em S.
· Determinado conjunto normalmente possui muitos subconjuntos. 
· O conjunto de todos os subconjuntos de um conjunto S é chamado de conjunto potência (powerset) ou conjunto das partes de S, sendo designado por:
· (s é o número de elementos do conjunto S)
Relações entre conjuntos
✅ Produto Cartesiano
· O produto cartesiano de dois conjuntos A e B é o conjunto de todos os pares ordenados (a, b), onde:
· a ∈ A
· b ∈ B
· Representado por: A × B = {(a, b) : a ∈ A e b ∈ B}
🔹 Par ordenado:
· Escrito como (a, b).
· Importa a ordem: (a, b) ≠ (b, a), se a ≠ b.
📌 Exemplo passo a passo:
· A = {a, b, c}, B = {0, 1}
· Produto cartesiano A × B:
➡️ Resultado: A × B = {(a,0), (a,1), (b,0), (b,1), (c,0), (c,1)}
✅ Relação entre Conjuntos
· Uma relação R entre dois conjuntos A e B é um subconjunto do produto cartesiano A × B.
· Os elementos da relação são pares ordenados (a, b).
📌 Exemplo: Se A × B = {(a,0), (a,1), (b,0), (b,1)}
Uma relação possível R ⊆ A × B pode ser: R = {(a, 1), (b, 0)}
Termos Importantes:
	Termo
	Significado
	Conjunto A
	Domínio da relação (conjunto de partida)
	Conjunto B
	Contradomínio da relação (conjunto de chegada)
	Relação binária
	Envolve dois conjuntos
✅ Relação de Equivalência
· É uma relação especial que generaliza o conceito de igualdade.
· Representada por: 
· Para ser uma relação de equivalência, deve seguir 3 regras:
🔹 Reflexividade: Todo elemento se relaciona com ele mesmo.
→ 
🔹 Simetria: Se a está relacionado com b, então b está relacionado com a.
→ Se , então 
🔹 Transitividade: Se a está relacionado com b e b está com c, então a está com c.
→ Se e , então 
📌 Exemplo de relação de equivalência: No conjunto de inteiros não negativos, podemos definir uma relação 𝑥≡𝑦 se e apenas se x mod 3 = y mod 3, em que mod é o resto da divisão inteira de x por y. Dessa forma, 2≡5,9≡0 e 12≡0. Prove que, essa é uma relação de equivalência, pois ela satisfaz à reflexividade, à simetria e à transitividade.
· mod 3 (mod = resto da divisão inteira)
📌 Exemplos:
· 5 ÷ 3 = 1 com resto 2 → 5 mod 3 = 2
· 9 ÷ 3 = 3 com resto 0 → 9 mod 3 = 0
· 12 ÷ 3 = 4 com resto 0 → 12 mod 3 = 0
· 2 ÷ 3 = 0 com resto 2 → 2 mod 3 = 2
📌 Aplicando o exemplo:
1. 2 ≡ 5 → Verificamos se 2 mod 3 = 5 mod 3
· 2 mod 3 = 2
· 5 mod 3 = 2
Como os restos são iguais, então 2 ≡ 5
2. 9 ≡ 0 → Verificamos se 9 mod 3 = 0 mod 3
· 9 mod 3 = 0
· 0 mod 3 = 0
Portanto, 9 ≡ 0
3. 12 ≡ 0 → Verificamos se 12 mod 3 = 0 mod 3
· 12 mod 3 = 0
· 0 mod 3 = 0
Então, 12 ≡ 0
📌 Por que isso é uma relação de equivalência?
Porque essa relação cumpre as 3 regras obrigatórias:
	Regra
	Significado simples
	Verificação no exemplo
	Reflexiva
	Todo número está relacionado com ele mesmo
	Ex: 2 mod 3 = 2 mod 3 → 2 ≡ 2 ✅
	Simétrica
	Se x ≡ y então y ≡ x
	Se 2 ≡ 5 → então 5 ≡ 2 também ✅
	Transitiva
	Se x ≡ y e y ≡ z, então x ≡ z
	Se 0 ≡ 9 e 9 ≡ 12 → então 0 ≡ 12 ✅
✅ Intuição Final:
Essa relação de equivalência agrupa os números com mesmo resto na divisão por 3.
📌 Exemplo de grupos (chamados de classes de equivalência):
· Classe 0: {0, 3, 6, 9, 12, 15, ...}
· Classe 1: {1, 4, 7, 10, 13, ...}
· Classe 2: {2, 5, 8, 11, 14, ...}
Cada número pertence a uma classe, e todos os da mesma classe são equivalentes entre si.
Funções 
· As funções são definidas por certas relações.
· Por causa de sua generalidade, as funções aparecem em muitos contextos matemáticos e na computação.
✅ O que é uma função?
· Função é uma regra que associa cada elemento de um conjunto A (domínio) a um único elemento de outro conjunto B (contradomínio).
· Representação:
· f: A → B ,onde: 𝑓 é o nome da função, A é chamado de domínio, B é chamado de imagem.
Ou 
· y = f(x) , expressa a lei de correspondência (relação) dos elementos x em A com os elementos y em B.
Termos importantes:
	Termo
	Significado
	Domínio (A)
	Conjunto de entrada da função
	Contradomínio (B)
	Conjunto onde estão os possíveis resultados
	Imagem
	Elemento de B que é de fato associado a algum de A
✅ Condição essencial para ser uma função:
· Todos os elementos do conjunto A devem ter pelo menos uma imagem no conjunto B.
· Não pode haver um mesmo elemento de A relacionado a dois elementos diferentes de B.
Representação com pares ordenados:
· A função pode ser escrita como um conjunto de pares:
f = {(a, b)}, onde a ∈ A e b = f(a)
Exemplo: Se f(2) = 4 → isso é representado como o par (2, 4)
Diagrama de Venn:
· Utilizado para representar graficamente a associação entre os conjuntos.
· O diagrama de Venn mostra:se uma determinada condição for cumprida (transição de estado).
Fluxo de funcionamento de um autômato finito
✅ 8. Funções principais de um AF
1. Memoriza informações do passado: Guarda histórico do que já foi lido.
2. Descrição do comportamento: Espera por uma entrada específica para mudar de estado.
3. Transição de estado: Muda de estado ao receber uma entrada compatível.
✅ 9. Exemplos de uso dos Autômatos Finitos
· Automação de projetos eletrônicos
· Projeto de protocolos de comunicação (como redes)
· Análise e outras aplicações de engenharia
· Inteligência Artificial (representação de sistemas neurológicos)
· Linguística (modelagem de gramáticas de linguagens naturais)
Planos paralelos ou ortogonais aos planos e eixos cartesianos
✅ 1. Vetores normais aos planos cartesianos
Os vetores normais indicam a direção "perpendicular" de um plano: 
· Vetor (0, 0, 1) → normal ao plano XY
· Vetor (0, 1, 0) → normal ao plano XZ
· Vetor (1, 0, 0) → normal ao plano YZ
	1. O que é um vetor normal a um plano?
· Um vetor normal é um vetor que aponta perpendicularmente ao plano.
· É como se ele fosse uma seta apontando para fora do plano, formando um ângulo de 90° com ele.
🔎 Imagine uma folha de papel sobre uma mesa.
Se você coloca um lápis em pé sobre a folha, esse lápis é como um vetor normal: está em pé, formando 90° com a folha.
Equações de planos paralelos aos planos cartesianos
· Paralelos ao plano XY → equação: z − k = 0, onde k é real
· Paralelos ao plano XZ → equação: y − k = 0, onde k é real
· Paralelos ao plano YZ → equação: x − k = 0, onde k é real
📌 Esses planos mantêm a mesma "altura", "largura" ou "profundidade", dependendo do plano de referência.
Equações de planos ortogonais aos planos cartesianos
· Ortogonais ao plano XY → equação: ax + by − k = 0, onde a, b e k são reais.
· Ortogonais ao plano XZ → equação: ax + bz − k = 0, onde a, b e k são reais.
· Ortogonais ao plano YZ → equação: ay + bz − k = 0, onde a, b e k são reais.
📌 Esses planos "cortam" perpendicularmente o plano de referência.
✅ 4. Relação entre plano e reta: Paralelismo e Ortogonalidade
🔹 Plano e reta paralelos
➡ O vetor diretor da reta é perpendicular ao vetor normal do plano
➡ Resultado: produto escalar = 0
🔹 Plano e reta ortogonais
➡ O vetor diretor da reta é paralelo ao vetor normal do plano
➡ Resultado: os vetores são proporcionais (razões iguais entre os componentes)
✅ Exemplos 
📘 Exemplo 1: Determine o valor de k para que os planos e a reta ​ sejam ortogonais.
Determinar o valor de k para que o plano e a reta sejam ortogonais
· Plano: 
· Reta: 
· Vetor normal do plano: n = (2, −4, 2) 
· Vetor diretor da reta: v = (−1, 2, k)
Para serem ortogonais, n e v precisam ser paralelos, ou seja, os componentes são proporcionais:
Calculando:
✅ Resposta: k = −1
📘 Exemplo 2: Verifique se o plano e a reta ​ são paralelos.
Verificar se o plano e a reta são paralelos
· Plano: 
· Reta: 
· Vetor normal do plano: n = (2, 3, 1)
· Vetor diretor da reta: v = (−1, 2, −4)
Para serem paralelos, os vetores devem ser ortogonais, ou seja:
✅ Como o produto escalar é 0, a reta e o plano são paralelos
✅ 6. Relação com os eixos coordenados
Seguindo esse conceito das condições de ortogonalidade e de paralelismo entre reta e plano podemos agora analisar as equações dos planos que serão paralelos e ortogonais aos eixos coordenados.
🔸 Planos paralelos aos eixos:
· Planos paralelos ao eixo z têm equação do tipo → ax + by − k = 0, onde a, b e k reais.
· Planos paralelos ao eixo y têm equação do tipo → ax + bz − k = 0, onde a, b e k reais.
· Planos paralelos ao eixo x têm equação do tipo→ ay + bz − k = 0, onde a, b e k reais.
➡ Esses são os mesmos planos ortogonais aos planos XY, XZ e YZ.
🔸 Planos ortogonais aos eixos:
· Planos ortogonais ao eixo z têm equação do tipo → z − k = 0, onde k é real.
· Planos ortogonais ao eixo y têm equação do tipo→ y − k = 0, onde k é real.
· Planos ortogonais ao eixo x têm equação do tipo → x − k = 0, onde k é real.
➡ Esses são os mesmos planos paralelos aos planos XY, XZ e YZ.
	📌 Resumo Final: Como identificar se uma reta é paralela ou ortogonal a um plano no espaço?
1. O que precisamos saber primeiro?
· Cada reta no espaço tem um vetor diretor → indica sua direção.
👉 Exemplo: 
· Cada plano tem um vetor normal → aponta perpendicularmente ao plano.
👉 Exemplo: 
2. Ferramenta principal: Produto Escalar
O produto escalar entre dois vetores indica a relação de ângulo entre eles: 
🔹 Caso 1: Reta paralela ao plano
📌 Condição: 
🔎 O vetor diretor da reta é ortogonal ao vetor normal do plano.
✳️ Isso significa que a reta “desliza” pelo plano sem cruzá-lo, como um avião voando rente ao chão.
🔹 Caso 2: Reta ortogonal ao plano
📌 Condição: 
🔎 O vetor diretor da reta é paralelo ao vetor normal do plano.
Ou seja, eles são proporcionais:
​ 
✳️ Isso significa que a reta “entra” no plano em 90°, como um prego entrando reto numa tábua.
	Relação entre reta e plano
	Verificação
	Significado
	Paralela ao plano
	Produto escalar 
	Vetores são ortogonais
	Ortogonal ao plano
	Vetores proporcionais: 
	Vetores apontam na mesma direção
· Para saber se uma reta é paralela ou ortogonal a um plano:
· Use o produto escalar entre os vetores.
· Produto escalar = 0 → vetores ortogonais → reta paralela ao plano.
· Vetores proporcionais → reta ortogonal ao plano.
Funcionamento do Autômato Finito
✅ 1. O que é um Autômato Finito (AF)?
· É um modelo de máquina simples usado para reconhecer cadeias de símbolos (como 0 e 1).
· Ele tem:
· Estados (como q0, q1…)
· Transições entre os estados
· Um estado inicial
· Estados finais (de aceitação)
✅ 2. Sistema transicional
· O autômato finito é um sistema transicional em que cada nó ou vértice representa um estado, e um arco direcionado indica uma transição de estado. 
· O rótulo dado a esse arco representa uma entrada, uma saída ou ambos.
· Cada estado é um nó (ou vértice).
· Cada seta (transição) mostra para onde ir ao ler um símbolo.
· O símbolo (entrada) determina a transição.
✅ 3. Função de transição
· Representa como o AF reage à entrada:
· : Se não há entrada (cadeia vazia), o estado permanece o mesmo.
· Leitura em sequência: 
Isso significa: primeiro lê “a”, muda de estado, depois lê o resto “w”.
✅ 4. Quando uma cadeia é aceita?
Uma cadeia é aceita pelo AF se:
1. Todos os símbolos são lidos (a cadeia é totalmente percorrida);
2. O AF para em um estado final.
Exemplo 1: Cadeia 0110
Passo a passo com os estados:
· Começa em q0 (também é estado final).
· Lê 0 → permanece em q0
· Lê 1 → vai para q1
· Lê 1 → fica em q1
· Lê 0 → volta para q0
🔚 Final da leitura: o AF está em q0, que é estado final.
✅ Resultado: a cadeia 0110 é aceita.
Exemplo 2: Cadeia 01011
Passo a passo com os estados:
· Começa em q0
· Lê 0 → fica em q0
· Lê 1 → vai para q1
· Lê 0 → volta para q0
· Lê 1 → vai para q1
· Lê 1 → fica em q1
🔚 Final da leitura: o AF está em q1, que não é final.
❌ Resultado: a cadeia 01011 não é aceita.
✅ Que tipo de cadeias esse AF reconhece?
Vamos analisar o comportamento:
1. O estado q0 é inicial e também final → aceita cadeia vazia (λ).
2. Enquanto lê 0, permanece em q0 → aceita qualquer número de zeros: 0, 00, 000, etc.
3. Quando lê 1, vai para q1 e só volta a q0 se ler “0” depois.
4. Se terminar em q1, a cadeia não é aceita.
📌 Conclusão: 👉 O AF reconhece todas as cadeias que terminam em 0, incluindo nenhum zero (λ) e todas as cadeias com quaisquer números de “0” e “1”, desde que terminem em zero.
✅ Exemplos de cadeias aceitas:
· λ (vazia)
· 0, 00, 000
· 10, 110, 1010
· 0110, 1000
❌ Exemplos de cadeias não aceitas:
· 1, 11, 1011, 01011
Exemplos práticos
Exemplo 1. Vamos ver como se comporta o AF a seguir e qual expressão regular ele reconhece.
1. Objetivo do exemplo: Analisar o comportamento de um Autômato Finito (AF) com base em cadeias de entrada e descobrir qual expressão regular (ER) ele reconhece.
1. Descrição geral do AF
· Esse autômato finito (AF) tem 2 estados: q0 e q1.
· Estado inicial e final: q0 (representado com seta de entrada e círculo duplo).
· Transiçõessão baseadas nos símbolos de entrada: 0 e 1.
2. Condições para uma cadeia ser aceita por um AF
Para uma cadeia ser aceita:
· Toda a cadeia deve ser lida completamente.
· O AF deve terminar em um estado final.
Exemplo 1: Cadeia de entrada 0110
Passo a passo:
1. Começa no estado q0.
2. Lê 0 → permanece em q0
3. Lê 1 → vai para q1
4. Lê 1 → volta para q0
5. Lê 0 → permanece em q0
🔚 A cadeia foi totalmente lida e o AF terminou em q0, que é um estado final.
✅ Resultado: cadeia 0110 foi aceita.
Exemplo 2: Cadeia de entrada 01011
Passo a passo:
1. Começa em q0
2. Lê 0 → permanece em q0
3. Lê 1 → vai para q1
4. Lê 0 → permanece em q1
5. Lê 1 → volta para q0
6. Lê 1 → vai para q1
🔚 A cadeia foi lida, mas o AF terminou em q1, que não é estado final.
❌ Resultado: cadeia 01011 não foi aceita.
3. O que esse AF reconhece? (Expressão Regular)
Analisando o comportamento:
· ✅ Aceita a cadeia vazia (λ) → porque o estado inicial (q0) é final.
· ✅ Aceita qualquer número de 0 → porque 0 não muda de estado (permanece em q0).
· ✅ Aceita cadeias com número par de 1 → a cada par de 1, ele entra e sai de q1, voltando para q0.
· ❌ Rejeita cadeias com número ímpar de 1 → pois termina em q1 (estado não final).
4. Conclusão (Expressão Regular reconhecida)
📌 O AF reconhece a linguagem descrita por: o número de 1 em w é par
➡ Ou seja:
✔️ Pode ter qualquer quantidade de zeros, incluindo nenhum zero (λ)
✔️ Pode ter número par de uns: 0, 2, 4, 6... uns (sempre par)
❌ Não aceita número ímpar de uns: 1, 3, 5... uns (nunca ímpar)
✔️Exemplos de cadeias ACEITAS:
· λ (vazia)
· 0, 00, 000
· 11, 001100, 1010, 0110
❌ Exemplos de cadeias NÃO ACEITAS:
· 1, 01, 01011, 111
Exemplo 2. Vejamos o AF descrito a seguir:
1. Descrição geral do AF
· Esse autômato finito (AF) tem 4 estados: q0, q1, q2 e q3.
· Estado inicial e final: q0 (representado com seta de entrada e círculo duplo).
· Transições são baseadas nos símbolos de entrada: 0 e 1.
2. Como funciona esse AF?
· Ele muda de estado conforme lê cada símbolo da cadeia (um por vez).
· O objetivo é terminar a leitura no estado final q0, que representa que a cadeia foi aceita.
3. Condições para aceitar uma cadeia
Uma cadeia é aceita se:
1. Todos os símbolos forem lidos;
2. O AF terminar no estado final (q0).
4. Comportamento observado
· O autômato alterna entre os estados, controlando a quantidade de zeros e uns.
· Ele “acompanha” se há uma quantidade par ou ímpar de 0 e de 1.
5. O que o AF reconhece?
📌 O AF reconhece apenas cadeias com:
· Número par de zeros
· Número par de uns
6. Exemplos de cadeias aceitas (com explicação)
🔹 Exemplo 1: λ (cadeia vazia)
· Nenhum símbolo é lido → permanece em q0 → ✅ Aceita
🔹 Exemplo 2: 00
· q0 → (0) → q2
· q2 → (0) → q0
✅ Aceita (2 zeros, 0 uns)
🔹 Exemplo 3: 11
· q0 → (1) → q1
· q1 → (1) → q0
✅ Aceita (0 zeros, 2 uns)
🔹 Exemplo 4: 0101
· q0 → (0) → q2
· q2 → (1) → q3
· q3 → (0) → q1
· q1 → (1) → q0
✅ Aceita (2 zeros, 2 uns)
🔹 Exemplo 5: 1010
· q0 → (1) → q1
· q1 → (0) → q3
· q3 → (1) → q2
· q2 → (0) → q0
✅ Aceita (2 zeros, 2 uns)
🔹 Exemplo de cadeia não aceita: 0101110
· q0 → (0) → q2
· q2 → (1) → q3
· q3 → (0) → q1
· q1 → (1) → q0
· q0 → (1) → q1
· q1 → (1) → q0
· q0 → (0) → q2
🔚 Termina em q2, que não é estado final
❌ Não aceita
✅ Se remover o último zero: 010111
· q0 → (0) → q2
· q2 → (1) → q3
· q3 → (0) → q1
· q1 → (1) → q0
· q0 → (1) → q1
· q1 → (1) → q0
🔚 Termina em q0
✅ Aceita
7. Resumo final
✔️ O autômato aceita cadeias que tenham:
· Número par de zeros ou nenhum símbolo (λ)
· Número par de uns
❌ Rejeita cadeias com:
· Número ímpar de zeros ou
· Número ímpar de uns
Tipos de Autômatos Finitos
· Podem ser de dois tipos: 
· Autômatos Finitos com Saída 
· Autômatos Finitos Bidirecionais (2AFD)
📌 Autômatos Finitos com Saída
· Definição: São autômatos que, além de mudar de estado conforme a entrada, também emitem uma saída (0 ou 1).
· Cada estado tem uma saída associada.
· Ao entrar em um estado, a máquina emite automaticamente o valor associado a ele.
🔸Exemplo do funcionamento de um AF com saída:
· O autômato tem dois estados:
· q1/1: Estado q1 emite 1 (e é um estado final).
· q2/0: Estado q2 emite **0`.
🔄 Transições:
🔹 Como funciona?
· A máquina lê um símbolo da fita de entrada por vez.
· Com base no símbolo e no estado atual, ela:
· Muda de estado.
· Emite uma saída associada ao estado que ela entra.
🔹 Exemplo com entrada 0110
1. Estado inicial: q1
2. Lê 0 → permanece em q1 → emite 1
3. Lê 1 → vai para q2 → emite 0
4. Lê 1 → vai para q1 → emite 1
5. Lê 0 → permanece em q1 → emite 1
🔸 Cadeia de saída gerada: 1 0 1 1
🔹 Reconhecimento da cadeia
· A última saída define se a cadeia foi reconhecida:
· Última saída 1 → cadeia reconhecida (termina em estado final q1).
· Última saída 0 → cadeia não reconhecida (termina em q2).
✔️ Neste caso, como a saída final é 1, a cadeia 0110 foi aceita.
🔸 Características do AF com saída
· 📌 Determinístico: Suas ações em resposta a uma sequência de entrada são completamente previsíveis.
· ⏱️ Sincronizado por ciclos: Funciona em ciclos discretos (uma entrada por vez).
· 💾 Estados servem como memória das entradas anteriores.
· 🔁 Responde às entradas com saídas.
· 📉 Número finito de estados.
🧠 Conclusão sobre Autômatos Finitos com Saída:
· Esse tipo de autômato simula o comportamento básico de um computador simples.
· Ele lembra do passado por meio de seus estados e responde com saídas a cada leitura.
· O estado final e a saída final dizem se a entrada é aceita ou não.
📌 Autômatos Finitos Bidirecionais (2AFD)
· Definição: São autômatos finitos em que a cabeça de leitura pode se mover para a direita (R) ou para a esquerda (L).
· Diferente dos autômatos tradicionais, que leem apenas da esquerda para a direita, os 2AFD podem voltar e reler partes da cadeia.
· Permitem análises mais complexas de padrões nas cadeias de entrada.
🔹 Funcionamento básico
· O estado atual e o símbolo lido determinam:
· Qual será o próximo estado.
· Para qual direção a cabeça se moverá (R ou L).
· A entrada é lida por uma "fita", e o autômato pode andar para frente ou para trás enquanto processa os símbolos.
Exemplo: Considere o seguinte autômato finito determinístico bidirecional (2AFD), dado por sua tabela de transição de estados:
· A = Estado inicial: A
· B = Estado final: B
· R = move em direção à direita (Right)
· L = move em direção à esquerda (Left)
Exemplo: Cadeia de entrada 101001
Vamos verificar se essa cadeia é aceita.
1. Começa no estado A, lendo 1 → vai para B, move R
2. Estado B, lê 0 → continua em B, move R
3. Estado B, lê 0 → continua em B, move R
4. Estado B, lê 1 → vai para C, move L
5. Estado C, lê 0 → vai para A, move R
6. Estado A, lê 0 → continua em A, move R
7. Estado A, lê 1 → vai para B, move R
8. Estado B, lê (fim da cadeia) → parada
🎯 Como o autômato termina no estado final B→ Cadeia foi aceita.
Conclusão sobre Autômatos Finitos Bidirecionais
· 2AFD são autômatos que leem em duas direções, permitindo mais controle sobre o reconhecimento de padrões.
· Aceitação de uma cadeia ocorre se, após o processamento, o autômato termina em um estado final.
· No exemplo, a cadeia 101001 é aceita porque o 2AFD terminou no estado B após seguir corretamente suas transições.
✅ Resumo Final
	Tipo de AF
	Característica principal
	AF com saída
	Emite saída em cada transição
	AF bidirecional (2AFD)
	Leitura da fita vai para direita ou esquerda
Questão 1. Considere o seguinte AF:
Assinale a alternativa em que todas as cadeias são aceitas por esse autômato:
A. 011, 010, 0010, 110
B. 010, 1, 00100, 111
C. 00, 11, 00100, 011
D. 001, 010, 0011, 1100
E. 000, 1111, 1010, 0101
A cada entrada "1", o autômato muda de estado e só para no estado final q1, quando o número de "1" na cadeia for ímpar.
Questão 2. Considere o seguinte AF:
Representação de AF.
Assinale a alternativa em que todas as cadeias são aceitas por esse autômato:
A. 011, 010, 0010, 110
B. 010, 1, 00100, 111
C. 0010, 0111, 1101, 0100
D. 001, 010, 0011, 1100
E. 000, 1111, 1010, 0101
Esse AF só para no estado final q3 quando a entrada contiver umnúmero ímpar de zeros e uns. Caso contrário, ele para em estados não finais e não reconhece a cadeia.
Módulo 3. Autômatos finitos não determinísticos 
Características e representação
🔹 1. O que são AFD e AFN?
✅ AFD (Autômato Finito Determinístico)
· Em cada estado, lendo um símbolo de entrada, há apenas um próximo estado possível.
· O comportamento é previsível e único.
✅ AFN (Autômato Finito Não Determinístico)
· Para o mesmo estado e símbolo de entrada, pode haver mais de um próximo estado possível.
· O comportamento é não determinístico: a máquina pode "escolher" entre vários caminhos possíveis.
· A cadeia será aceita se ao menos um dos caminhos terminar em um estado final.
🔹 2. Representação de um AFN
Um AFN é definido por um conjunto:
M = {Q, I, fs, q0, F}, onde:
	Símbolo
	Significado
	Q
	Conjunto de estados
	I
	Alfabeto (símbolos de entrada)
	fs
	Função de transição ( )
	q0
	Estado inicial
	F
	Conjunto de estados finais
🔹 3. Diferença principal
· AFD: sempre sabemos qual será o próximo estado.
· AFN: pode haver múltiplas possibilidades, e alguns caminhos podem levar a estados finais, outros não.
🔹 Exemplo com tabela de transição (AFN):
Vejamos a representação gráfica desse AFN:
🔹 5. Análise do comportamento (exemplo com cadeia: 00101)
Vamos verificar se a cadeia é aceita a partir do estado inicial q0.
✳️ Passo a passo:
1. Lê 0 em q0 → pode ir para q0 ou q1 → bifurca!
2. Lê 0 novamente → continua a bifurcar em dois ou mais caminhos.
3. Lê 1 → alguns caminhos vão para q2, outros para q1, e assim por diante.
Resultado:
· Existem 3 caminhos possíveis ao processar a cadeia.
· Apenas um desses caminhos termina no estado final q2.
· Logo, a cadeia 00101 é aceita pelo AFN, porque pelo menos um caminho termina em estado final.
🔹 Conclusão sobre Autômato Finito Não Determinístico
· Uma cadeia é aceita por um AFN se existe ao menos um caminho possível (entre os vários) que leva a um estado final após ler todos os símbolos.
· Caso nenhum caminho leve a um estado final, a cadeia é rejeitada.
· AFD e AFN são equivalentes em poder expressivo, pois:
· Todo AFD é um AFN.
· Todo AFN pode ser transformado em um AFD equivalente, usando o conjunto das partes (construção de subconjuntos).
· O AFD equivalente pode ter mais estados.
Conversão de AFN para AFD
🔹 Diferença entre AFN e AFD
· AFD (Determinístico):
· Para cada símbolo e estado, há apenas um caminho possível.
· Fácil de analisar.
· Função: 
· AFN (Não Determinístico):
· Pode ter vários caminhos possíveis para a mesma entrada em um estado.
· É difícil saber se uma cadeia será aceita só observando uma execução.
· Função: (conjunto de subconjuntos dos estados)
🔹 Por que converter um AFN em AFD?
· No AFN, é difícil prever o comportamento, pois há múltiplas possibilidades.
· No AFD, a execução é determinística e mais fácil de implementar, especialmente em máquinas.
· ✅ O objetivo da conversão é transformar o comportamento "vários caminhos" (AFN) em "apenas um caminho" (AFD), sem perder nenhuma possibilidade de aceitação.
🎯 Como converter um AFN em AFD – Passo a Passo
· Imagine que no AFN você está em um estado, digamos q0, e recebe o símbolo 0. O AFN pode ir para mais de um estado, como q0 e q1. 
· No AFD, você junta esses possíveis estados e cria um novo estado: [q0, q1]. 
📍 Etapas com explicações:
1. Comece com o estado inicial do AFN
· Esse será o estado inicial do AFD.
· Ex: Se o estado inicial do AFN for q0, o AFD começa com [q0].
2. Descubra os próximos estados para cada símbolo
· Veja para onde o AFN pode ir com a entrada 0 e com a entrada 1 a partir do estado [q0].
· Se q0 → 0 → q0 e q0 → 0 → q1, você escreve:
· Com entrada 0: [q0, q1]
· Se q0 → 1 → q2, você escreve:
· Com entrada 1: [q2]
3. Crie novos estados para cada novo conjunto de estados
· Se [q0, q1] apareceu, trate isso como um novo estado do AFD.
· Repita o processo: veja para onde vai [q0, q1] com 0 e com 1.
4. Continue até não surgirem mais conjuntos novos
· Repita o processo para todos os novos estados formados.
· Quando nenhum conjunto novo aparecer, pare.
5. Determine os estados finais do AFD
· Se qualquer estado do conjunto conter um estado final do AFN, então esse conjunto é final no AFD.
· Ex: Se q2 é estado final no AFN e [q1, q2] aparece no AFD, então [q1, q2] é estado final no AFD.
🧩 Exemplo 1 – Conversão com a tabela:
AFN:
AFD gerado:
	Estado AFD (subconjunto)
	Entrada 0
	Entrada 1
	A = [q0]
	B = [q0, q1]
	E = [q2]
	B = [q0, q1]
	D = [q0, q1, q2]
	C = [q1, q2]
	C = [q1, q2]
	C = [q1, q2]
	C = [q1, q2]
	D = [q0, q1, q2]
	D = [q0, q1, q2]
	C = [q1, q2]
	E = [q2]
	F = [q1]
	E = [q2]
	F = [q1]
	E = [q2]
	F = [q1]
✅ Estados finais do AFD: → Todos os conjuntos que contêm q2 (estado final do AFN): C, D, E
Representação Gráfica Desse Autômato:
🧩 Exemplo 2 – Segundo exercício prático
AFN:
AFD resultante:
	Estado AFD (subconjunto)
	Entrada 0
	Entrada 1
	A = [q0]
	B = [q0, q1]
	A = [q0]
	B = [q0, q1]
	C = [q0, q1, q2]
	B = [q0, q1]
	C = [q0, q1, q2]
	E = [q0, q1, q2, q3]
	D = [q0, q1, q3]
	D = [q0, q1, q3]
	C = [q0, q1, q2]
	C = [q0, q1, q2]
	E = [q0, q1, q2, q3]
	E = [q0, q1, q2, q3]
	E = [q0, q1, q2, q3]
✅ Estado inicial: A = [q0]
✅ Estados finais: D e E (ambos contêm q3, estado final do AFN)
Representação Gráfica Desse Autômato:
🧠 Conclusão Final
· A conversão de AFN para AFD usa subconjuntos de estados como novos estados.
· Isso pode aumentar o número de estados, mas elimina a não determinismo.
· Todo AFN pode ser convertido em um AFD equivalente, e ambos reconhecem as mesmas linguagens regulares.
Questão 1. (POSCOMP - SBC - 2012) Seja um autômato finito não determinístico (AFN) com seis estados. Aplicando-se o algoritmo de conversão de um AFN para um autômato finito determinístico (AFD), em quantos estados, no máximo, resultaria o AFD, considerando-se os estados redundantes?
A. 12
B. 36
C. 64
D. 1024
E. 46656
Questão 2. Um autômato finito determinístico (AFD) pressupõe que, a partir de um estado atual, exista apenas um próximo estado possível a ser atingido. Já em um autômato finito não determinístico (AFN), ao ler um símbolo, há mais de uma possibilidade de estado a ser atingido. Assinale a alternativa cuja função permite que um AFN seja convertido em seu equivalente AFD:
A. Q × I → Q
B. Q × I → 2Q
C. Q × I → 2n
D. Q × I → Qn
E. Q x Q → In
Para converter um AFN em um AFD, é necessário realizar a conversão de todos os conjuntos de estados em estados únicos. Dessa forma, os Q estados do AFN darão lugar a 2Q estados no AFD.
Módulo 4. Fundamentos de linguagem regulares
Principais definições
📘 Expressões Regulares (ER)
🔹 O que são?
· São uma forma de descrever linguagens regulares, que pertencem à gramática do tipo 3 da hierarquia de Chomsky.
· São aceitas por autômatos finitos (AF).
· Utilizadas em programas de busca, como grep, e em linguagens como Perl.
· Também chamadas de: ER, regex ou regexp.
🔹 Por que "regulares"?
· Porque representam linguagens com padrões constantes.
· Qualquer linguagem que um AF reconhecer pode ser expressa com uma ER.
⚙️ Operações principais sobre expressões regulares:
1. União (| ou +): representa escolha entre dois conjuntos.
2. Concatenação (· ou justaposição): junta duas cadeias.
3. Fechamento de Kleene (*): repete um padrão 0 ou mais vezes.
🔸 Fechamentos: Diferença entre dois tipos
✅ Fechamento simples (R*)
· Repetição de uma mesma cadeia 0 ou mais vezes.
· Exemplo:
Se R = 01, então
R* = {λ, 01, 0101, 010101, ...}
✅ Fechamento de Kleene (Σ*)
· Conjunto de todas as combinações possíveis dos símbolos do alfabeto (incluindo λ).
· Exemplo:
Se Σ = {0,1}, então
Σ* = {λ, 0, 1, 00, 01, 10, 11, 000, ...}
📚 Conjuntos Regulares
🔹 Definição: São linguagens recursivamente definidas sobre um alfabeto finito Σ. Um conjunto é regular se pode ser construído usando apenas:
1. ∅ (vazio)
2. {λ} (palavra vazia)
3. {σ}, onde σ ∈ Σ
4. União (X ∪ Y)
5. Concatenação (XY)
6. Fechamento de Kleene (X*)
✅ Exemplo de linguagem regular:
Seja Σ = {0, 1}
→ Isso significa: qualquer número de 0s seguidos de qualquernúmero de 1s.
Exemplos de cadeias em L:
· λ (vazio)
· 0
· 1
· 00
· 01
· 011
· 000111, etc.
Representação por ER: 
🔄 Recursividade em Expressões Regulares
🔹 Regras recursivas:
1. ∅ → representa linguagem vazia
2. λ → representa a palavra vazia
3. σ ∈ Σ → representa o conjunto {σ}
4. Se x e y são ERs, então também são ERs:
· (x)
· x + y ou x | y → união
· xy ou x·y → concatenação
· x* → fechamento de Kleene
🔸 Representação alternativa (sem chaves e ∪)
· Note que, nas expressões regulares, é possível eliminar o uso dos símbolos “{” e “}”, bem como substituir o operador “∪” pelo operador “+” ou pela barra vertical “|”. 
· Além disso, podemos utilizar precedência sobre os operadores para as três operações sobre expressões regulares, o que reduz o emprego de parênteses. Veja a tabela a seguir:
	Precedência
	Operador
	Símbolo
	Mais alta 
	Fechamento
	x∗
	Intermediária
	Concatenação
	x.y ou xy
	Mais baixa
	União
	x|y ou x + y
✅ Exemplo com Linguagens Regulares:
Linguagens:
· 
· 
· 
· 
· 
· ER para L5: 
Propriedades
🚀 Lema do Bombeamento (Pumping Lemma)
📌 O que é?
· É uma propriedade essencial das linguagens regulares.
· Serve principalmente para provar que uma linguagem NÃO é regular, usando prova por contradição.
🔍 Definição Formal
Seja L uma linguagem regular, então:
· Existe um número inteiro p ≥ 1 (chamado de comprimento de bombeamento) tal que:
· Toda cadeia w ∈ L com |w| ≥ p pode ser dividida como: 
· y é a subcadeia que pode ser bombeada (removida ou repetida arbitrariamente).
E as seguintes condições devem ser satisfeitas:
✔️ Condições do lema:
1. |y| ≥ 1 → a parte y não pode ser vazia.
2. |xy| ≤ p → y está nos primeiros p caracteres.
3. Repetição arbitrária: Podemos repetir arbitrariamente (e omitir) a subcadeia y, e a cadeia xyz resultante pertencerá a L, ou seja, para todo i ≥ 0, a cadeia (ou seja, pode repetir y quantas vezes quiser — inclusive nenhuma — e ainda estar na linguagem).
📌 Intuição
· Você pode “bombear” (repetir ou remover) a parte y da cadeia, e a nova cadeia continuará sendo da linguagem, se ela for regular.
❗ Importância
· Se existe uma cadeia que não pode ser dividida em xyz satisfazendo essas condições, então a linguagem NÃO é regular.
❗ Linguagens finitas
· Sempre satisfazem o lema por vacuidade (não têm cadeias grandes o suficiente para violar o lema).
📉 Como usar o lema para provar que uma linguagem não é regular?
✨ Estratégia:
1. Supor que a linguagem L é regular.
2. Usar o lema: existe p ≥ 1.
3. Escolher uma cadeia w com |w| ≥ p.
4. Mostrar que qualquer forma de dividir w = xyz, com as condições acima, gera uma cadeia fora da linguagem após bombear y.
5. Concluir: L não é regular (contradição).
✅ Exemplo: 
Etapas:
1. Suponha que L é regular.
2. Então existe um p ≥ 1.
3. Escolha a cadeia: w = aᵖbᵖ (exemplo: aaa...aaabbb...bbb)
4. Por |xy| ≤ p, y será composto apenas por letras "a".
5. Bombeando y → aᵖ⁺ᵏbᵖ, que não tem o mesmo número de "a"s e "b"s.
6. Contradição! Portanto, L não é regular.
🤖 Lema do Bombeamento com Autômato Finito Determinístico (AFD)
✳️ A ideia:
· Em um AFD com p estados, ao ler uma cadeia com comprimento ≥ p, algum estado será visitado duas vezes (princípio da casa dos pombos).
· O caminho entre a primeira e segunda visita define a subcadeia y, que pode ser repetida ou omitida.
🧪 Exemplo com o autômato da imagem (cadeia abcd) 
Estados:
q0 --a→ q1 --b→ q2 --c→ q1 --d→ q3 (final)
Divisão:
· x = a
· y = bc (vai de q1 para q1)
· z = d
Cadeias aceitas:
· Original: abcd
· Bombeando y (repetindo): abcbcd
· Bombeando y (omitindo): ad
Conclusão: Esse autômato *aceita cadeias da forma a(bc)d
📌 Resumo Final
	Conceito
	Descrição
	Lema do Bombeamento
	Propriedade usada para mostrar que uma linguagem pode não ser regular
	Cadeia w = xyz
	Cadeia longa que pode ser dividida em 3 partes
	Subcadeia y
	Pode ser repetida ou omitida, mantendo w na linguagem
	Prova por contradição
	Mostra que a repetição ou omissão leva a uma cadeia fora da linguagem
Aplicação prática
📌 O que são Expressões Regulares?
· São padrões utilizados para buscar, validar ou substituir textos.
· Muito úteis para verificar se uma entrada do usuário segue um formato esperado (ex: CPF, CEP, nomes, e-mails).
· Usadas em linguagens como Java, Python, JavaScript, entre outras.
🧠 Conceitos básicos
· Uma expressão regular (regex) é uma cadeia de caracteres que define um padrão de correspondência (match).
· Usa caracteres especiais, chamados metacaracteres, como:
· \d: corresponde a um dígito de 0 a 9.
· .: representa qualquer caractere (exceto quebra de linha).
· ^: indica o início da string.
· $: indica o final da string.
· {n,m}: define a quantidade de repetições esperadas.
✍️ Exemplo 1 – Validação de CEP
🧾 Formato: 22540-050
· Queremos validar CEPs no formato: cinco dígitos, hífen, três dígitos.
Diferentes formas Regex:
✅ Regex: \\d\\d\\d\\d\\d-\\d\\d\\d . Significa que teremos cinco dígitos decimais separados de outros três dígitos decimais por meio de um caractere “-“
✅ Regex: ^\\d{5,5}\\-\\d{3,3}$ 
✅ Regex: ^\d{5}-\d{3}$
🔎 Explicação passo a passo:
	Símbolo
	Significado
	^
	Início da string
	\d{5}
	Exatamente 5 dígitos
	-
	Um hífen
	\d{3}
	Exatamente 3 dígitos
	$
	Fim da string
🧪 Exemplos válidos:
· 12345-678 ✅
· 98765-321 ✅
❌ Exemplos inválidos:
· 1234-567 ❌ (apenas 4 dígitos antes do hífen)
· 123456-78 ❌ (seis dígitos antes)
✍️ Exemplo 2 – Validação de CPF
🧾 Formato: 123.456.789-00
Diferentes formas Regex:
✅ Regex: ^\\d{3}\\.\\d{3}\\.\\d{3}\\-\\d{2}$
✅ Regex: ^\d{3}\.\d{3}\.\d{3}-\d{2}$
🔎 Explicação passo a passo:
	Símbolo
	Significado
	^
	Início da string
	\d{3}
	Três dígitos
	\.
	Um ponto (precisa ser escapado com \)
	(repetido 3x)
	\d{3}\.\d{3}\.\d{3} = 3 blocos com ponto
	-
	Hífen
	\d{2}
	Dois dígitos (dígitos verificadores)
	$
	Fim da string
🧪 Exemplos válidos:
· 123.456.789-00 ✅
❌ Exemplos inválidos:
· 12345678900 ❌ (sem pontos nem hífen)
✍️ Exemplo 3 – Validação de Nome Próprio
✅ Regex:
[A-Z][a-zA-Z]*
🔎 Explicação passo a passo:
	Símbolo
	Significado
	[A-Z]
	Primeira letra maiúscula
	[a-zA-Z]*
	Pode ter letras minúsculas ou maiúsculas após
	*
	Zero ou mais ocorrências (nome com 1 ou + letras)
🧪 Exemplos válidos:
· João ✅
· Maria ✅
❌ Exemplos inválidos:
· joão ❌ (primeira letra minúscula)
· mARIA ❌ (mistura fora do padrão)
Questão 1. A expressão regular que permite reconhecer a digitação correta de placas de automóveis no Brasil no modelo ABC-5789 é:
A. ^\\[A-Z]{3,3}\\-\\d{4,4}$
B. \\[A-Z]{3,3}\\d{2,2}\\[A-Z]{2,2}\\d{4,4}
C. ^\\[A-Z]{3,3}\\d{1,1}\\[A-Z]{1,1}\\d{2,4}
D. \\[A-Z]{3,3}\\d{1,1}\\[A-Z]{1,1}\\d{2,2}$
E. ^\\[A-Z]{3,3}\\d{1,1}\\[A-Z]{1,1}\\d{4,4}$
A expressão deve iniciar com "^", ter exatamente três letras maiúsculas iniciais e mais quatro dígitos decimais, separados por um caractere "-". A expressão deve terminar com o caractere "$"
Questão 2. A expressão regular que permite reconhecer a digitação correta de placas de automóveis no Brasil no modelo BSE3R52 é:
A. ^\\[A-Z]{3,3}\\-\\-\d{4,4}$
B. \\[A-Z]{3,3}\\d{2,2}\\[A-Z]{2,2}\\d{4,4}
C. ^\\[A-Z]{3,3}\\d{1,1}\\[A-Z]{1,1}\\d{2,4}
D. ^\\[A-Z]{3,3}\\d{1,1}\\[A-Z]{1,1}\\d{2,2}$
E. ^\\[A-Z]{3,3}\\d{1,1}\\[A-Z]{1,1}\\d{4,4}$
A expressão deve iniciar com "^", ter exatamente três letras maiúsculas iniciais seguidas por um dígito decimal, mais uma letra maiúscula seguida por dois dígitos decimais. A expressão deve terminar com o caractere "$"
TEMA 4 - LINGUAGENS LIVRES DE CONTEXTO
Módulo 1. Gramáticas livre de contexto	
📘Conceitos Básicos:
🔹 Símbolo
· É uma entidade abstrata, como um ponto na geometria.
· Exemplos: =, *, /, >,da cadeia original.
· Exemplo: Para w = 012, as subcadeias são:
· λ, 0, 1, 2, 01, 02, 12, 012
· Número total de subcadeias: 2ⁿ, onde n é o número de símbolos da cadeia.
🔹 Concatenação
· Operação de juntar duas cadeias formando uma nova.
· Exemplo: se x = 01 e y = 10, então x·y = 0110.
📘 Linguagem Formal
🔹 Definição
· Conjunto de cadeias válidas sobre um alfabeto.
· Usadas para representar linguagens de programação, como C, C++, Java.
· São precisas, matematicamente definidas e finitamente representadas.
📘 Gramática Formal
🔹 Objetivo: Define regras para gerar todas as cadeias válidas de uma linguagem formal.
🔹 Definição de Gramática
· Representada por uma quádrupla: G=(V,T,P,S) 
Onde:
· V: Variáveis ou símbolos não terminais (ex: S, A, B).
· T: Símbolos terminais (ex: a, b, 0, 1).
· P: Conjunto de regras de produção (ex: S → aA, A → b).
· S: Símbolo inicial da gramática (deve estar no lado esquerdo de pelo menos uma regra).
🔹 Regras de Produção (ou Derivação)
· Formato: a → b, onde:
· Lado esquerdo (LE): Contém pelo menos um símbolo não terminal.
· Lado direito (LD): Pode conter símbolos terminais, não terminais, ambos ou ser vazio (λ).
🔍 Resumo 
Símbolo → entidade abstrata (ex: =, *, /)
Alfabeto → conjunto finito de símbolos (ex: {0, 1})
Cadeia → sequência de símbolos (ex: 000111)
λ → cadeia vazia
Subcadeias → todas as combinações possíveis de símbolos da cadeia original
Concatenação → união de duas cadeias
Linguagem Formal → conjunto de cadeias válidas sobre um alfabeto
Gramática G = (V, T, P, S)
 V = variáveis (não terminais)
 T = terminais
 P = produções (regras)
 S = símbolo inicial
📘 Fechamento e Fecho de Kleene
🔹 Fechamento Reflexivo (Σ*)
· Representa todas as combinações possíveis de símbolos do alfabeto Σ, incluindo a cadeia vazia (λ).
· É chamado também de fecho de Kleene.
· Exemplo: Se Σ = {0, 1}, então: 
Σ* = {λ, 0, 1, 00, 01, 10, 11, 000, ...}
🔹 Fechamento Transitivo (Σ⁺)
· É também chamado de fechamento positivo.
· É igual a Σ*, mas sem a cadeia vazia (λ), ou seja, é Σ* - {λ}.
· Representa todas as palavras possíveis formadas com Σ, com pelo menos um símbolo.
· Exemplo:
Se Σ = {a, b}, então:
Σ⁺ = {a, b, aa, ab, ba, bb, aaa, ...} 
📘 Representação de Linguagens
· Uma linguagem formal é sempre um subconjunto de Σ*.
· Pode ser representada como: L = { w ∈ Σ* | w tem a propriedade P }
✅ Exemplo 1 – Cadeias com número igual de 0’s e 1’s
· Linguagem: L = { w ∈ {0,1}* | w consiste em n 0’s seguidos de n 1’s }
· Cadeias: {01, 0011, 000111, 00001111, ...}
· Propriedade: mesma quantidade de 0’s seguidos da mesma quantidade de 1’s.
📘 Fecho de Kleene (Σ*) – Explicação e Exemplos
· O fecho de Kleene inclui todas as cadeias possíveis, inclusive a cadeia vazia (λ).
✅ Exemplo: Σ = {0}
· Σ* = {λ, 0, 00, 000, ...}
✅ Exemplo: Σ = {0, 1}
· Σ* = {λ, 0, 1, 00, 01, 10, 11, 000, 001, ...}
✅ Fecho Positivo (Σ⁺)
· Mesmo que os exemplos acima, mas sem incluir λ.
📘 Exemplo: Linguagem que começa e termina com 'b'
Linguagem:
· "Qualquer combinação de a e b, começando e terminando com b."
Expressão com fecho de Kleene:
· L = b(a + b)*b
Passo a passo:
1. (a + b) → qualquer um dos dois símbolos.
2. (a + b)* → qualquer sequência (inclusive λ).
3. b no início e b no fim → garante que começa e termina com b.
Cadeias válidas:
· bb, bab, baab, bbb, babbbab, ...
📘 Exemplo: Linguagem dos Números Naturais (ℕ)
Alfabeto:
· D = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
Linguagem:
· Conjunto de números naturais decimais.
Expressão regular:
· ℕ = D D*
Explicação:
1. Primeiro D → garante que a cadeia começa com um dígito.
2. D* → permite zero ou mais dígitos a seguir.
Cadeias válidas:
· 0, 1, 5, 23, 109, 98765, ...
📘 Exemplo: Expressão: (a + b)*(aa + bb)
Passo a passo:
1. a e b denotam {a} e {b}, respectivamente.
2. a + b denota a união de {a} U {b} = {a, b}. 
3. (a + b)* → denota todas as combinações possíveis de a e b, incluindo nenhuma (λ)
4. aa → cadeia com dois a’s, ou seja, {a}{a}={aa}; 
5. bb → cadeia com dois b’s, ou seja, {b}{b}={bb}
6. aa + bb → denota a união de {aa, bb}
7. (a + b)*(aa + bb) → cadeia qualquer de a e b terminando com aa ou bb
Cadeias válidas:
· aa, bb, aaa, abb, baa, bbb, aabb, bbaa, ababaa, bababb, ...
✅ Resumo
	Conceito
	Representação
	Inclui λ?
	Exemplo (Σ = {a, b})
	Fechamento Reflexivo (Fechamento de Kleene)
	Σ*
	Sim
	{λ, a, b, aa, ab, ba, bb, aaa, ...}
	Fechamento Transitivo (Fechamento Positivo)
	Σ⁺
	Não
	{a, b, aa, ab, ba, bb, aaa, ...}
	Linguagem Formal
	Subconjunto de Σ*
	Depende
	Ex: {w ∈ Σ*...}
📘 Hierarquia de Chomsky 
· A Hierarquia de Chomsky classifica gramáticas formais em quatro tipos, da mais restrita (Tipo 3) à mais geral (Tipo 0).
· Cada tipo de gramática gera um tipo de linguagem formal, usada em linguagens naturais e de programação.
🔹 Gramática Tipo 0 – Irrestrita (com de estrutura de frase)
✳️ Características:
· Mais geral de todas.
· Sem restrições formais nas regras.
· Pode representar qualquer linguagem reconhecida por uma máquina de Turing.
📐 Forma das regras: 
· Onde:
· α (lado esquerdo) deve conter pelo menos um símbolo não terminal.
· β (lado direito) pode conter qualquer combinação de símbolos terminais e não terminais, inclusive a cadeia vazia (λ).
✅ Exemplo: Se α = X, β = aXb ou β = λ, então é uma produção tipo 0 válida.
🔹 Gramática Tipo 1 – Sensível ao Contexto (GSC)
✳️ Características:
· Sentenças válidas dependem do contexto em que os símbolos aparecem.
· São mais restritas que as do Tipo 0, porém mais poderosas que as livres de contexto.
· Muito usada para representar estruturas de linguagem natural e em linguagens de programação.
📐 Forma das regras: com 
· α (lado esquerdo) deve conter pelo menos um não terminal, cercado por qualquer sequência de símbolos.
· β (lado direito) pode conter qualquer combinação, porém não pode ter a palavra vazia (λ).
· O comprimento da direita é maior ou igual ao da esquerda
✅ Exemplo: Se α = aXb, β = aYb → válida (mesmo comprimento, substituição dentro do contexto).
🔹 Gramática Tipo 2 – Livre de Contexto (GLC)
✳️ Características:
· Regras são aplicadas independentemente do contexto.
· Muito usada para definir sintaxe de linguagens de programação e expressões matemáticas.
📐 Forma das regras: 
· Lado esquerdo: contém exatamente um símbolo não terminal (ex: S, A, B).
· Lado direito: pode conter qualquer combinação de símbolos, inclusive a palavra vazia (λ).
✅ Exemplo: As Gramáticas livre de contexto são importantes para definir linguagens de programação. Por exemplo, as linguagens que requerem o balanceamento de parênteses e são geradas pela gramática:
1. Regra: S → SS | (S) | λ
2. Explicação:
· Pode gerar cadeias como (), (()), ()(), (()()), etc.
· 👉 Essa gramática garante que os parênteses fiquem corretamente balanceados, típico das linguagens de programação.
· λ: Representa uma cadeia vazia (base da recursão).
· (S): Um par de parênteses contendo uma outra expressão S.
· SS: Duas expressões S lado a lado.
· Como o uso de conceitos recursivamente definidos aumentou, as GLC foram usadas mais e mais. 
· As primeiras aplicações das gramáticas eram principalmente para descrever a estrutura de linguagens de programação. Uma aplicação mais recente foi a utilização de GLC em uma parte essencial da Extensible Markup Language (XML).
🔹 Gramática Tipo 3 – Regular
✳️ Características:
· Mais restrita da hierarquia.
· Define linguagens regulares, aceitas por autômatos finitos.
· Muito usada para modelar reconhecimento de padrões, como palavras-chave e tokens.
📐 Forma das regras: ou 
· Lado direito: contém um símbolo terminal seguido, opcionalmente, por um símbolo não terminal.
✅ Exemplo:
1. Regras:
· S → aA
· A → b
2. Geração:
· S → aA → ab
3. Cadeia gerada: ab
📊 Resumo Comparativo
	Tipo
	Nome
	Forma do Lado Esquerdo
	Forma do Lado Direito
	Produz λ?
	Nível de Restrição
	Máquina Reconhecedora
	0
	Irrestrita
	Mínimo 1 não terminal
	Qualquer combinação de V ∪ T (inclusive λ)
	Sim
	Nenhuma
	Máquina de Turing
	1
	Sensível ao Contexto
	Pelo menos 1 não terminal e α ≤ β.
	Qualquer combinação deV ∪ T (exceto λ)
	Não
	Moderada
	Maquina linearmente limitada
	2
	Livre de Contexto (GLC)
	1 não terminal
	Qualquer sequência de V ∪ T (inclusive λ)
	Sim
	Mais restrita
	Autômato com pilha (PDA)
	3
	Regular
	A → aX ou A → a
	Um terminal seguido de no máx. um não terminal ou λ
	Sim 
(via A → λ)
	Mais restrita
	Autômato Finito (DFA/NFA)
🧠 Conclusão – Inclusão entre as Classes
Usando a teoria dos conjuntos:
· Toda gramática regular é também uma GLC.
· Toda GLC é sensível ao contexto.
· Toda GSC é uma gramática irrestrita.
📌 Hierarquia: Gramáticas Regulares ⊂ Livres de Contexto ⊂ Sensíveis ao Contexto ⊂ Irrestritas
📘 Gramáticas Livres de Contexto (GLC)
🔹 O que são?
· Uma GLC define uma linguagem chamada linguagem livre de contexto (LLC).
· Usada para descrever a estrutura de linguagens de programação e expressões matemáticas balanceadas.
🔹 Forma Geral de Produção
· Regra: onde e  
· Ou seja:
· O lado esquerdo (LE) tem apenas um símbolo não terminal (ex: S, A, B).
· O lado direito (LD) pode ter qualquer combinação de terminais e não terminais, inclusive a cadeia vazia λ.
🔹 Por que é "livre de contexto"?
· Porque o símbolo não terminal do lado esquerdo não depende do contexto (ou seja, nenhum símbolo o acompanha no LE).
· Regras de produção têm o formato: 
🧠 Conceito de Contexto (para comparação)
· A cadeia do LE tem um símbolo não terminal e a do LD contém uma combinação de terminais e não terminais. 
· Se algum símbolo estiver presente com o não terminal no LE da regra de produção, então esse símbolo extra é chamado de contexto. 
· Tipos de contexto:
· Contexto Esquerdo: símbolo aparece antes do não terminal.
· Contexto Direito: símbolo aparece depois do não terminal.
· Em uma gramática livre de contexto, no LE, há apenas um não terminal (nenhum contexto é adicionado com ele); por esse motivo, esse tipo de gramática é chamada de gramática livre de contexto.
📘 BNF – Forma Normal de Backus-Naur
🔹 O que é?
· É uma notação formal para descrever sintaxe de linguagens.
· É utilizada na descrição da linguagem ALGOL 60.
· Usada para definir:
· Linguagens de programação
· Conjuntos de instruções
· Protocolos de comunicação
· Linguagens naturais
🔹 Símbolos da BNF
	Símbolo
	Significado
	::=
	“é definido como”
	|
	“ou”
	
	Definem categorias (não terminais)
⚙️ Como funciona a BNF?
· BNF consiste em regras de derivação escritas no formato:
 ::= 
 ::= | 
· O lado esquerdo (LE) é sempre um não terminal.
· O lado direito (LD) pode conter terminais (símbolos concretos) ou não terminais (categorias).
· Terminais são elementos que não aparecem mais como LE em outras regras.
· Não-terminais são colocados entre colchetes angulares: 
✅ Exemplo 1: Endereço postal em BNF
 ::= 
 ::= 
 | 
 ::= "." | 
 ::= 
 ::= "-" 
✅ Tradução: Um endereço postal é composto por:
1. Uma parte com o nome da pessoa.
2. Um trecho com o endereço da rua.
3. Uma parte com o CEP e cidade/estado.
✅ Exemplo 2: Número decimal
 ::= | 
 ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
🔎 Explicação passo a passo:
· pode ser:
· Um único dígito (7)
· Ou um número seguido de mais dígitos (74, 743, etc.)
· Essa definição gera números com vários dígitos.
📘 BNF Estendida (EBNF)
· A versão estendida da BNF inclui operadores de expressões regulares, como:
· * → zero ou mais repetições
· + → uma ou mais repetições
✅ Exemplo 3: Identificador em linguagem de programação
 ::= letra (letra | dígito)*
 ::= a | b | c | ... | z | A | B | C | ... | Z
 ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
🔎 Explicação:
· Um identificador começa com uma letra.
· Depois, pode conter letras ou dígitos, em qualquer quantidade (inclusive nenhuma).
✅ Exemplo de identificadores válidos:
· x, nome1, contador123, A1b2C
✅ Resumo 
	Conceito
	Descrição
	GLC
	Gramática com um não terminal no LE, que gera cadeias com terminais e/ou não terminais
	Livre de contexto
	Porque o LE não depende de símbolos ao redor (sem "contexto")
	BNF
	Notação usada para definir sintaxe formal
	EBNF
	Versão estendida com símbolos como *, +
	Usos
	Definição de linguagens de programação, protocolos de redes, linguagens naturais
📘 Exemplos Práticos de GLC – Gramáticas Livres de Contexto
✅ Exemplo 1: Vamos construir uma GLC para a linguagem 
💡 Objetivo: Criar uma gramática que gera cadeias com qualquer palavra W, seguida da letra C, seguida de W invertida (W^R).
🧠 Explicação:
· W: qualquer combinação de a e b, incluindo a cadeia vazia, pois W ∈ {a, b}*.
· WR: reverso de W.
· C: símbolo fixo (central).
· A cadeia completa é como um espelho em torno do C.
✅ Exemplos de cadeias válidas:
· C (caso W seja vazio)
· abCba
· abbaCabba
🧱 Regras da gramática:
S → aSa | bSb | C
· aSa → adiciona a no início e fim (espelhado)
· bSb → mesma ideia com b
· C → caso base (meio da cadeia)
🔹 Definição formal da gramática:
· V = {S}
· T = {a, b, C}
· P = {S → aSa | bSb | C}
· Símbolo inicial: S
✅ Exemplo 2: Vamos construir uma GLC para a expressão: Cadeias da forma (0 + 1)* 0 1*
💡 Objetivo: Criar uma GLC para a linguagem descrita pela expressão regular:
· Cadeias com:
· Qualquer sequência de 0 e 1, ou nenhuma (λ)
· Seguido de um único 0 (fixo)
· Finalizando com qualquer quantidade de 1s, ou nenhuma (λ)
🔎 Exemplos válidos:
· 0
· 1001
· 001111, 101101111
🧠 Estratégia:
· Fixar o único 0 do meio.
· Criar duas partes:
· Parte antes do 0 → gerada por A (mistura de 0 e 1).
· Parte depois do 0 → gerada por B (apenas 1s).
🧱 Regras da gramática:
· S → ASB | 0 (regra principal com o 0 central)
· A → 0A | 1A | λ (gera qualquer sequência de 0s e 1s, inclusive nenhuma)
· B → 1B | λ (gera apenas 1s ou nada)
📋 Definição da GLC:
· Variáveis (V): {S, A, B}
· Terminais (T): {0, 1}
· Produções (P):
· S → ASB | 0
· A → 0A | 1A | λ
· B → 1B | λ
· Símbolo inicial (S): S
✅ Exemplo 3: Vamos construir uma GLC para uma cadeia na qual há um número igual de números binários.
💡 Objetivo: Construir uma GLC para gerar cadeias com a mesma quantidade de 0s e 1s, em qualquer ordem.
✅ Exemplos de cadeias válidas:
· λ (vazia – 0 zeros e 0 uns)
· 01, 10
· 0011, 1100, 0101, 1010, 0110, etc.
🧠 Estratégia:
· Cada regra insere um 0 e um 1 simultaneamente, em posições diferentes:
· 0S1 → 0 no início, 1 no fim
· 1S0 → 1 no início, 0 no fim
· A recursão garante que o número de 0s e 1s sempre será igual.
🔹 Explicação passo a passo:
· Garante que cada 0 seja pareado com um 1, mesmo em posições diferentes.
· Substituições se equilibram, resultando em quantidades iguais.
🧱 Regras da gramática:
· S → 0S1 | 1S0 | λ
📋 Definição da GLC:
· Variáveis (V): {S}
· Terminais (T): {0, 1}
· Produções (P): S → 0S1 | 1S0 | λ
· Símbolo inicial (S): S
Questão 1. A seguinte expressão define uma gramática livre de contexto P = {A→β | A ϵ V Λ β ϵ (V U T)*}. Avalie as afirmativas a seguir:
I. O lado esquerdo da produção contém exatamente uma variável.
II. No lado direito é possível qualquer combinação de símbolos do conjunto {V U T}*.
III. É uma gramática tipo 3, sendo importante para definir linguagens de programação.
Quais as afirmativas estão corretamente relacionadas com uma gramática livre de contexto?
A. II e III
B. I e III
C. I e II
D. I, II e III
E. II
Questão 2. Considere o seguinte subconjunto da gramática da linguagem C, expresso em BNF:
As regras para identificadores de variáveis em linguagem C são:
1. Um identificador é uma sequência de letras, dígitos e sublinhados.
2. Um identificador deve começar com uma letra ou sublinhado.
3. Os identificadores permitem letras maiúsculas e minúsculas.
Onde “|” representa “ou” e λ representaa cadeia vazia.
 ::= |
 ::= |||λ
 ::= a|b|...|z|A|B|...|Z
 ::= 0|1|...|9
 ::= _
Assinale a alternativa que representa corretamente a produção descrita no texto:
A. , e ϵ T
B. {a|b|...|z|A|B|...|Z} ϵ T*
C. → é uma regra de produção válida
D. {0|1|...|9} ϵ(V U T)*
E. ::= λ
Módulo 2. Simplificação de gramática livre de contexto
📘 Remoção de Símbolos Não Geradores em GLCs
🔹 Objetivo da Remoção
· Simplificar a gramática sem alterar a linguagem que ela define.
· Isso reduz a complexidade e facilita a análise e o processamento da gramática.
⚙️ Etapas para simplificar uma GLC
1. Remoção de símbolos inúteis
a) Símbolos não geradores:
· São símbolos que não produzem cadeias apenas com símbolos terminais.
Exemplo: Se um não terminal só gera combinações com outros não terminais sem chegar a terminais → ele é inútil.
· Remoção: eliminar todas as produções onde ele aparece (tanto no lado esquerdo quanto no direito).
b) Símbolos não alcançáveis:
· São símbolos que não podem ser alcançados a partir do símbolo inicial (S).
· Remoção: eliminar todas as produções com esse símbolo.
2. Remoção de produções unitárias
· Produções do tipo: A → B, onde um não terminal leva direto a outro.
3. Remoção de produções nulas
· Produções do tipo: A → λ, que geram a cadeia vazia.
✅ Resumo do Algoritmo para Remoção de Símbolos Inúteis
1. Identificar símbolos geradores:
· Comece pelos que geram diretamente terminais.
· Vá adicionando os que, indiretamente, também geram terminais.
2. Remover símbolos não geradores:
· Elimine todas as produções que contenham esses símbolos.
3. Identificar símbolos alcançáveis:
· Comece pelo símbolo inicial S.
· Vá marcando os símbolos que podem ser atingidos.
4. Remover símbolos não alcançáveis:
· Elimine todas as produções que os envolvam.
🔍 Exemplos passo a passo
✏️ Exemplo 1: Vamos remover os símbolos inúteis da seguinte GLC:
🎯 Gramática inicial:
S → AC
S → BA
C → CB
C → AC
A → a
B → aC | b
🔎 Passo 1: Símbolos geradores
· A → a e B → b → geradores.
· C → CB ou C → AC → sempre volta a não terminais → C não gera terminais.
· ✔️ C é não gerador → remover todas as produções com C.
✂️ Após remoção:
S → BA
A → a
B → b
🔎 Passo 2: Símbolos alcançáveis
· A partir de S, podemos chegar a B e A.
· ✔️ Nenhum símbolo inacessível → fim da simplificação.
✅ Gramática minimizada:
S → BA
A → a
B → b
✏️ Exemplo 2: Vamos remover os símbolos inúteis da seguinte GLC:
🎯 Gramática inicial:
S → aB | bX
A → BAd | bSX | a
B → aSB | bBX
X → SBD | aBx | ad
🔎 Passo 1: Símbolos geradores
· X → ad → gera terminais.
· S → bX → gera terminais (indiretamente).
· A → a, mas A → BAd e bSX usam B e S.
· 🛑 B não gera terminais (todas suas produções retornam a símbolos não terminais).
✔️ Remover todas as produções com B.
✂️ Após remoção:
S → bX
A → bSX | a
X → ad
🔎 Passo 2: Símbolos alcançáveis
· De S → bX, temos:
· S → X (alcançável).
· “A” nunca é usado por S → não alcançável.
· ✔️ Remover “A”.
✅ Gramática minimizada:
S → bX
X → ad
✅ Resumo: Benefícios da simplificação
	Antes
	Depois
	Mais símbolos e regras
	Menos símbolos e regras
	Mais etapas na geração da cadeia
	Geração mais rápida e direta
	Pode conter símbolos sem função
	Apenas símbolos úteis e acessíveis
📘 Remoção de Produções Unitárias em GLCs
🔹 O que são produções unitárias?
· São regras da forma:
A → B, onde A e B são não terminais.
· Elas não contribuem com novos símbolos terminais.
· Servem apenas como "ponte" para outras regras.
· Exemplo de produção unitária:
A → B (troca direta de um símbolo por outro).
🎯 Por que remover produções unitárias?
· Elas aumentam:
· o número de passos para gerar uma cadeia.
· a complexidade da gramática.
· Toda GLC pode ser reescrita sem produções unitárias, mantendo a mesma linguagem.
⚙️ Algoritmo de remoção
· A remoção de produções unitárias de uma GLC pode ser realizada a partir do seguinte algoritmo:
Enquanto (existir produção unitária na forma A→B)
{
         Selecione a produção unitária A→B
         Para (toda produção não unitária B→α)
         {
                Adicione a produção A→α à gramática.
                Elimine a regra A→B dessa gramática.
         }
}
Explicação: 
Enquanto houver uma produção unitária A → B:
1. Para cada produção não unitária de B (ex: B → α),
2. Adicione uma nova regra: A → α.
3. Remova a produção A → B.
🧪 Exemplo 1: Seja a seguinte GLC, vamos remover a produção unitária:
🎯 Gramática original:
S → AB 
A → E 
B → C 
C → D 
D → b 
E → a
🔎 Identificando produções unitárias:
· A → E
· B → C
· C → D
✅ Etapas de remoção:
1. A → E, e E → a → adiciona A → a
Gramática:
S → AB
A → a
B → C
C → D
D → b
E → a
2. C → D, e D → b → adiciona C → b, remove C → D
Gramática:
S → AB, 
A → a
B → C
C → b
D → b
E → a
3. B → C, e C → b → adiciona B → b, remove B → C
Gramática:
S → AB, 
A → a, 
B → b, 
C → b, 
D → b, 
E → a
🔎 Símbolos inutilizados (não alcançáveis): C, D, E → Remover
✅ Gramática final (minimizada):
S → AB 
A → a 
B → b
🧪 Exemplo 2: Remova a produção unitária da gramática a seguir:
🎯 Gramática original:
S → AB 
A → a 
B → C 
C → D 
D → b
🔎 Produções unitárias:
· B → C
· C → D
✅ Etapas de remoção:
1. C → D, e D → b → adiciona C → b, remove C → D
Gramática:
S → AB
A → a 
B → C
C → b
D → b
2. B → C, e C → b → adiciona B → b, remove B → C
Gramática:
S → AB, 
A → a
B → b
C → b
D → b
🔎 Símbolos não alcançáveis: C e D → Remover
✅ Gramática final (minimizada):
S → AB 
A → a 
B → b
✅ Conclusão
	Antes da Remoção
	Depois da Remoção
	Muitas regras indiretas
	Regras diretas e eficientes
	Mais passos para gerar sentenças
	Menos passos
	Produções redundantes (unitárias)
	Produções úteis e objetivas
📘 Remoção de Produções Nulas em GLCs
🔹 O que é uma produção nula?
· É uma regra da forma: NT → λ, onde NT é um não terminal e λ representa a cadeia vazia.
· Exemplo: A → λ
❗ Importante:
· Se a linguagem aceita a cadeia vazia, produções como S → λ não podem ser removidas.
· Caso não aceite a cadeia vazia, as produções nulas devem ser eliminadas para simplificar a gramática.
⚙️ Algoritmo para Remoção de Produções Nulas
Objetivo: Transformar uma gramática G em uma equivalente G′, sem produções nulas (exceto S → λ se necessário).
✅ Passos:
1. Identifique todas as produções do tipo NT → λ.
2. Procure todas as regras da gramática que tenham esse NT no lado direito.
3. Crie novas regras retirando o NT (simulando a ausência dele), sem eliminar as produções originais.
4. Substitua a produção nula por essas novas produções.
5. Remova a produção NT → λ, se a linguagem não aceitar cadeia vazia.
🧪 Exemplo 1: Remova a produção λ da gramática a seguir:
🎯 Gramática original:
S → aA 
A → b | λ
🔍 Identificando:
· Produção nula: A → λ
· Regra com ‘A’ no lado direito: S → aA
🔁 Substituindo:
· De S → aA, criamos S → a (simulando a ausência de A)
🔎 Nova gramática:
S → aA | a 
A → b
✅ Produção nula removida com sucesso.	
🧪 Exemplo 2: Remova a produção λ da gramática a seguir: 
🎯 Gramática original:
S → aX | bX 
X → a | b | λ
🔍 Identificando:
· Produção nula: X → λ
· Regras com ‘X’ no lado direito: S → aX, S → bX
🔁 Substituindo:
· S → aX gera S → a
· S → bX gera S → b
✅ Nova gramática:
S → aX | bX | a | b 
X → a | b
✅ Produção nula removida.
🚫 Quando não remover uma produção nula?
· Se a linguagem aceita a cadeia vazia (λ), então a produção S → λ não deve ser removida, pois ela é essencial para gerar essa cadeia.
✅ Conclusão
	Situação
	O que fazer?
	Produção do tipo NT → λ
	Eliminar com substituições
	Produção do tipo S → λ e λ ∈ linguagem
	Manter essa produção
	Substituições de NT → λ no LD
	Gerar versões alternativas sem o NT
	Linguagem não contém λ
	Remover todas produções nulas
Questão 1. Considerando os símbolos não geradores, avalie as seguintes alternativas:
 I. Não geram nenhuma sequência de terminais e não terminais.
II. Não geram nenhuma sequência de terminais.
III. Não geram nenhuma sequência deproduções.
 Qual opção inclui afirmativas corretas?
A. I e II
B. II e III
C. III
D. II
E. I
Questão 2. Qual das seguintes alternativas é uma produção unitária (T = Terminal e NT = Não terminal)?
A. (cadeia de NT)→(cadeia de NT)
B. (NT único)→(cadeia de NT)
C. (NT)→(NT único)
D. (cadeia de NT)→(NT único)
E. (T único)→(T único)
Produções unitárias são produções da forma A→B, em que A e B são não terminais, e costumam ser descartadas das GLC porque nada acrescentam às formas sentenciais às quais são aplicadas, constituindo mera renomeação de símbolos.
Módulo 3. Autômatos de pilha
Conceitos fundamentais
🔹 Autômatos Finitos (AF)
· O que é?
· É um modelo computacional simples com um número finito de estados.
· Também chamado de Máquina de Estados Finitos (MEF).
· Reconhece linguagens regulares.
· Como funciona?
· Sempre está em um único estado por vez (estado atual).
· Transições entre estados ocorrem com base nos símbolos de entrada.
· Exemplo: A imagem ao lado mostra dois estados (q0, q1) e como os símbolos 0 e 1 causam mudanças de estado.
· Componentes principais de um AF:
Um AF pode ser definido da seguinte forma: é um AF se:
· Q: conjunto de estados.
· I: alfabeto de entrada (símbolos permitidos).
· fs: função de transição (Q × I → Q).
· q0: estado inicial.
· F: estados finais (aceitam a cadeia).
🔸 Diagrama mecânico de um autômato finito
· Mecanicamente, autômatos finitos podem ser descritos como uma fita de entrada contendo os símbolos de entrada (I) com um cabeçote de leitura varrendo as entradas da esquerda para a direita. 
· As entradas são alimentadas ao controle finito que contém as funções de transição (fs). 
· De acordo com as funções de transição, ocorre a mudança de estado (Q).
🧠 Como funciona? 
· A fita de entrada contém os símbolos a serem processados.
· A cabeça de leitura varre a fita da esquerda para a direita.
· O controle finito usa a entrada para decidir qual será o próximo estado.
· A fita tem marcadores como @ (início) e $ (fim).
🔹 Pilha 
· O que é?
· Estrutura de dados do tipo LIFO (Last In, First Out).
· O último elemento inserido é o primeiro a ser removido.
· Operações básicas:
· Push: empilhar um elemento.
· Pop: desempilhar o elemento do topo.
· Funcionamento (imagem ao lado):
· Mostra o empilhamento dos números 1 a 6.
· Depois, mostra a remoção dos elementos na ordem inversa.
· Tipos de pilha:
· Stack: Permite consultar elementos abaixo do topo, além de realizar as operações de básicas de empilhamento e desempilhamento da pilha (push e pop).
· Pushdown: Permite o acesso apenas ao elemento armazenado no topo, através das operações de empilhamento e desempilhamento (push e pop). Não permite o endereçamento dos demais elementos. (usada em autômatos com pilha).
· Aplicações comuns:
· Controle de chamadas de função.
· Armazenamento temporário de dados durante execução de programas.
Autômatos de pilha
🔹 O que é um Autômato de Pilha (PDA, em inglês, push down automata)?
· É uma evolução dos autômatos finitos com o acréscimo de uma pilha.
· Serve para reconhecer linguagens livres de contexto (LLC), como exemplo: L = {aⁿbⁿ | n ≥ 1}.
· A pilha funciona como memória auxiliar, permitindo que o autômato “lembre” quantos símbolos viu.
🔸 Por que o PDA é necessário?
· Um autômato finito não reconhece a linguagem aⁿbⁿ pois não tem memória suficiente.
· O PDA podem memorizar o número de ocorrências de ‘a’ e combiná-lo com o número de ocorrências de ‘b’ com a ajuda da pilha, garantindo a correspondência.
🔹 Definição formal de um PDA
Um PDA é definido como uma 7-tupla:
M = (Q, Σ, Γ, δ, q₀, z₀, F)
· Q: conjunto finito de estados
· Σ: alfabeto de entrada
· Γ: alfabeto da pilha
· δ: função de transição → define como o autômato reage
· q₀: estado inicial
· z₀: símbolo inicial da pilha
· F: conjunto de estados finais
🔹 A função de transição δ:
· Formato: δ: Q × (Σ ∪ {λ}) × Γ → P(Q × Γ*)
· Interpretação: Com base no estado atual, símbolo da entrada (ou λ) e topo da pilha, decide o próximo estado e a operação na pilha (push/pop/nada).
🔸 Como funciona o PDA?
🧠 Memória: Pilha
· Armazena símbolos temporários.
· Opera com:
· Push: empilhar símbolo no topo.
· Pop: retirar símbolo do topo.
· Nada: pilha permanece igual.
· O símbolo z₀ representa a base da pilha.
⚙️ Etapas de funcionamento: 
1. O PDA lê o símbolo da fita com a cabeça de leitura (da esquerda para a direita).
2. Ele verifica o símbolo no topo da pilha.
3. A partir disso, decide:
· Mudar de estado?
· Empilhar símbolo?
· Desempilhar?
· Permanecer como está?
📘 Exemplo: L = {aⁿbⁿ | n ≥ 1}
🔁 Passo a passo com cadeia: aaabbb
1. Para cada ‘a’ lido: → Push(X) na pilha.
· Após aaa, a pilha terá: XXXz₀
2. Para cada ‘b’ lido: → Pop(X) da pilha.
· Após bbb, a pilha volta a conter apenas z₀.
3. Se a entrada acabar e a pilha estiver apenas com z₀, cadeia aceita.
🧠Explicação detalhada:
· Em autômatos finitos, a memória é limitada aos estados. Isso funciona bem para linguagens simples, como expressões regulares.
🧩 Por que precisamos de um PDA?
· Para linguagens como L = {aⁿbⁿ | n ≥ 1}, que exigem comparação entre partes da cadeia (mesma quantidade de 'a's e 'b's), os estados não são suficientes.
· Seria necessário um número infinito de estados para contar os símbolos, o que não é possível.
🛠️ Solução: Adicionar uma pilha
· Para cada ‘a’ lido, o PDA faz um push (empilha um símbolo).
· Quando começa a ler os ‘b’, o PDA faz pop (desempilha um símbolo para cada 'b').
· Se, no final, a pilha estiver vazia (ou com símbolo base), a cadeia é aceita.
✅ Conclusão: O PDA resolve limitações dos autômatos finitos ao usar a pilha como memória, tornando possível reconhecer linguagens mais complexas, como as livres de contexto.
🧩 Diagrama mecânico (resumo da estrutura)
· Fita de entrada: onde está a cadeia a ser lida.
· Cabeça de leitura: percorre a fita, símbolo por símbolo.
· Controle finito: decide o que fazer com base no símbolo lido e na pilha.
· Pilha: armazena símbolos temporariamente para garantir controle de estrutura da cadeia.
✅ Conclusão
· O PDA amplia os autômatos finitos, permitindo reconhecimento de estruturas mais complexas como expressões com simetria, recursividade ou balanceamento (como parênteses e chaves).
· É essencial para linguagens livres de contexto, como aquelas usadas em analisadores sintáticos de compiladores.
Funcionamento dos autômatos de pilha
📌 1. Descrição Instantânea (ID, instant description)
· Representa o estado atual do PDA.
· É uma tripla escrita como: (q, w, κ), onde:
· q: estado atual (pertence a Q),
· w: parte restante da cadeia de entrada,
· κ: conteúdo atual da pilha.
✅ 2. Formas de Aceitação de Cadeias
a) Por Pilha Vazia
· A cadeia é aceita quando a entrada termina e a pilha está vazia (inclusive o símbolo base z₀ foi removido).
· Notação: Se .
b) Por Estado Final
· A cadeia é aceita quando a entrada termina e o PDA atinge um estado final, mesmo que a pilha não esteja totalmente vazia.
· Notação: Se , então , com .
🧪 Exemplo: Vamos construir um PDA para aceitar a linguagem L = {aⁿbⁿ | n ≥ 1} tanto por pilha vazia quanto pelo estado final.
✅ Observações sobre a cadeia:
· A cadeia tem a mesma quantidade de ‘a’ e ‘b’;
· Todos os ‘a’ aparecem antes dos ‘b’;
· Linguagem não regular, mas livre de contexto (LLC).
⚙️ Funcionamento do PDA:
· Símbolos da pilha: z₀ (base), z₁ (para contar 'a').
· A pilha serve para lembrar quantos ‘a’ apareceram, empilhando z₁ para cada ‘a’.
· Quando começa a ler os ‘b’, desempilha um z₁ para cada ‘b’.
🔄 Transições δ (função de transição) 
1. Lendo ‘a’: 
· δ(q₀, a, z₀) → (q₀, z₁z₀) → empilha z₁ sobre z₀.
· δ(q₀, a, z₁) → (q₀, z₁z₁) → continua empilhando z₁.
2. Lendo ‘b’:
· δ(q₀, b, z₁) → (q₁, λ) → desempilha z₁ e muda para q₁.
· δ(q₁, b, z₁) → (q₁, λ) → continua desempilhando.
3. Final da cadeia:
· Se aceita por pilha vazia: 
· δ(q₁, λ, z₀) → (q₁, λ) 
· Se aceita por estado final: 
· δ(q₁, λ, z₀) → (qf, z₀)
🧾 4. Resumo da Definição do PDA
· Q = {q₀, q₁, qf} → estados
· Σ = {a, b} → alfabeto da entrada
· Γ = {z₀, z₁} → símbolos da pilha
· q₀ = estado inicial
· z₀ =símbolo inicial da pilha (pilha vazia)
· F = {qf} → conjunto de estados finais
🔁 5. Resumo das Regras δ
	Transição
	Significado
	δ(q₀, a, z₀) → (q₀, z₁z₀)
	Empilha z₁ sobre z₀
	δ(q₀, a, z₁) → (q₀, z₁z₁)
	Empilha z₁ sobre z₁
	δ(q₀, b, z₁) → (q₁, λ)
	Desempilha e muda para q₁
	δ(q₁, b, z₁) → (q₁, λ)
	Continua desempilhando
	δ(q₁, λ, z₀) → (q₁, λ)
	Finaliza (por pilha vazia)
	δ(q₁, λ, z₀) → (qf, z₀)
	Finaliza (por estado final)
✔️ Conclusão:
· O PDA consegue verificar a correspondência entre ‘a’ e ‘b’ usando a pilha como memória.
· O mesmo autômato pode aceitar uma cadeia por esvaziar a pilha ou por alcançar um estado final, conforme o modo de aceitação escolhido.
Questão 1. Analise as afirmativas relativas ao diagrama mecânico do PDA?
I. O PDA contém uma pilha.
II. A cabeça lê e escreve.
III. A cabeça se move da esquerda para a direita.
Quais as afirmativas verdadeiras?
A. I e II.
B. I e III.
C. I, II e III.
D. Somente I.
E. Somente III.
Questão 2. A descrição instantânea lembra:
A. As informações de estado e conteúdo da fita de entrada em uma determinada instância de tempo.
B. As informações da pilha e conteúdo da fita em uma determinada instância de tempo.
C. As informações da fita de entrada e do conteúdo da pilha em uma determinada instância de tempo.
D. As informações de estado, fita de entrada e conteúdo da pilha em uma determinada instância de tempo.
E. As informações de estado e conteúdo da pilha em uma determinada instância de tempo.
Módulo 4. Propriedade das linguagens livre de contexto
Propriedades de fechamento
✅ O que são Propriedades de Fechamento?
· Dizemos que uma linguagem é fechada sob uma operação (como união, concatenação, etc.) quando, ao aplicar essa operação em duas linguagens do mesmo tipo, o resultado também pertence àquele tipo.
· No nosso caso:
Se L₁ e L₂ são linguagens livres de contexto (LLC), queremos saber quando L₁ ∘ L₂ também é uma LLC.
🌐 O que é fechamento?
· Fechamento é uma propriedade de um conjunto quando fazemos uma operação entre dois elementos desse conjunto.
🟢 Definição: Uma operação tem fechamento sobre um conjunto quando o resultado da operação entre dois elementos do conjunto ainda está dentro do mesmo conjunto.
❌ Se o resultado sair do conjunto → não tem fechamento.
✅ Exemplo 1: Com Fechamento
Conjunto A = {números pares} = {…, -4, -2, 0, 2, 4, 6, …}
Operação: adição (+): Vamos testar se a adição tem fechamento no conjunto dos pares:
· 2 + 4 = 6 ✅ (6 é par → continua no conjunto)
· -2 + 8 = 6 ✅ (também é par)
➡️ Conclusão: A adição tem fechamento no conjunto dos pares ✅
❌ Exemplo 2: Sem Fechamento
Conjunto B = {números naturais} = {0, 1, 2, 3, 4, …}
Operação: subtração (-): Vamos testar se a subtração tem fechamento no conjunto dos números naturais:
· 3 - 1 = 2 ✅ (ainda é natural)
· 1 - 3 = -2 ❌ (não é natural, pois naturais não têm negativos)
➡️ Conclusão: A subtração não tem fechamento no conjunto dos naturais ❌
🧠 Exemplo 3: Agora com linguagens (nos estudos de autômatos):
Suponha que temos:
· L₁ = {“ab”, “cd”}
· L₂ = {“ef”}
· Operação: união (L₁ ∪ L₂) → Resultado: {“ab”, “cd”, “ef”}
Se L₁ e L₂ são linguagens livres de contexto (LLC) e o resultado também for uma LLC, dizemos que a operação união tem fechamento nas LLC ✅
🔵 1. Fechamento na União
📌 O que é? A união junta as palavras de duas linguagens:
· Se L₁ = {“ab”, “cd”} e L₂ = {“ef”}, então L₁ ∪ L₂ = {“ab”, “cd”, “ef”}
🔸 A LLC é fechada na união? ✔️ SIM!
💡 Como provar? Criamos uma nova gramática que:
· Usa todas as regras de L₁ e L₂;
· Adiciona uma nova regra que escolhe entre elas.
🧠 Exemplo de regra nova: S → S₁ | S₂ (S₁ gera L₁, S₂ gera L₂)
· Logo, se L₁ e L₂ são LLC, então L₁ ∪ L₂ também será LLC.
Exemplo: Sejam L₁ uma LLC com a GLC, e L₂ com a . Temos que provar que também é uma LLC.
Construção da gramática G₃:
· V₃ = V₁ ∪ V₂ ∪ {S₃} → junta os não terminais e adiciona um novo símbolo inicial.
· Σ₃ = Σ₁ ∪ Σ₂ → junta os alfabetos das duas linguagens.
· P₃ = P₁ ∪ P₂ ∪ {S₃ → S₁ | S₂} → junta as regras e adiciona uma nova que permite escolher entre S₁ e S₂.
Exemplo de interpretação: G₃ pode gerar qualquer cadeia que G₁ ou G₂ gerariam → por isso, L₃ = L₁ ∪ L₂.
🔵 2. Fechamento na Concatenação
📌 O que é? Concatenação junta palavras de duas linguagens em sequência.
· Se L₁ = {“a”} e L₂ = {“b”}, então L₁L₂ = {“ab”}
🔸 A LLC é fechada na concatenação? ✔️ SIM!
💡 Como provar? Criamos uma nova gramática que:
· Usa todas as regras de L₁ e L₂;
· Adiciona uma regra que coloca S₁ seguido de S₂.
🧠 Exemplo de regra nova: S → S₁ S₂ (S₁ gera L₁, depois S₂ gera L₂)
· Logo, se L₁ e L₂ são LLC, então L₁·L₂ (cadeias de L₁ seguidas de cadeias de L₂) também será LLC.
Exemplo: Sejam L₁ uma LLC com a GLC, e L₂ com a . Temos que provar que também é uma LLC.
Construção da gramática G₃:
· V₃ = V₁ ∪ V₂ ∪ {S₃}
· Σ₃ = Σ₁ ∪ Σ₂
· P₃ = P₁ ∪ P₂ ∪ {S₃ → S₁ S₂}
Explicação: A nova gramática permite derivar uma cadeia de L₁ usando S₁, seguida por uma de L₂ com S₂ → assim, L₁·L₂ é gerada.
🔵 3. Fechamento no Fecho de Kleene
📌 O que é? Permite repetir zero ou mais vezes uma linguagem.
· Se L₁ = {“ab”}, então L₁* = {λ, “ab”, “abab”, “ababab”, ...}
🔸 A LLC é fechada no fecho de Kleene? ✔️ SIM!
💡 Como provar? Criamos uma nova gramática que:
· Repete S₁ (com S → S₁ S ou λ)
· Isso permite gerar várias repetições de L₁ (ou nenhuma).
🧠 Exemplo de regra nova: S → S₁ S | λ
· Logo, o fecho de Kleene de uma LLC também é uma LLC, pois, se L₁ é LLC, então L₁* também será LLC.
Exemplo: Seja L₁ uma LLC com a GLC, . Temos que provar que L₁* também é uma LLC. Então, vamos construir uma gramática , usando a gramática G₁ como segue:
Construção da gramática G₂:
· V₂ = V₁ ∪ {S₂}
· P₂ = P₁ ∪ {S₂ → S₁ S₂ | λ}
Explicação passo a passo:
· A nova regra permite:
· S₂ → S₁ S₂ → repetir várias cadeias de L₁.
· S₂ → λ → parar a repetição (cadeia vazia).
· Assim, qualquer número de cadeias de L₁ (inclusive nenhuma) podem ser combinadas.
🔴 4. Interseção
📌 O que é? Pega apenas as palavras que existem nas duas linguagens.
· Se L₁ = {“abc”, “def”} e L₂ = {“abc”, “ghi”}, então L₁ ∩ L₂ = {“abc”}
🔸 A LLC é fechada na interseção? ❌ NÃO!
🧠 Exemplo que mostra isso:
· L₁ = { aⁿ bⁿ cᵐ | n ≥ 0, m ≥ 0 }
· L₂ = { aⁿ bᵐ cᵐ | n ≥ 0, m ≥ 0 }
· As duas são LLC.
· Mas a interseção é: L₁ ∩ L₂ = { aⁿ bⁿ cⁿ } → não é LLC, é linguagem sensível ao contexto (tipo 1).
· L₁ ∩ L₂ não é uma LLC, mesmo que L₁ e L₂ sejam.
· ❌Essa linguagem não é livre de contexto! (precisa de mais memória para comparar os 3 blocos).
· 🔁 Conclusão: A interseção pode gerar uma linguagem mais complexa, fora da classe LLC.
🔴 5. Complementação
📌 O que é? Complemento é tudo que não está na linguagem. 
🧠 Exemplo: Se L = {“a”, “b”}, então seu complemento (em Σ = {“a”, “b”, “c”}) seria {“c”, “aa”, “abc”...}
🔸 A LLC é fechada no complemento? ❌ NÃO!
💡 Por quê? Existe uma regra chamada Lei de D’Morgan: ou 
· Se LLC fosse fechada em complemento, a interseção também seria — o que a gente já viu que é falso. Logo, não é fechada no complemento.
· 🔁 Conclusão: Como interseção não é garantida, o complemento também não pode ser garantido.
✅ 6. Toda Linguagem Regular é uma LLC?
✔️ Sim, toda linguagem regular também é uma linguagem livre de contexto.
💡 Por quê? As linguagens regulares são construídas com:
· ∅ (vazio), λ (cadeia nula) e símbolos terminais;
· Operações de União ( + ), concatenação e fecho de Kleene (*)
Como as LLC também são fechadas nessas operações, todas as linguagens regulares podem ser geradas por uma gramática livre de contexto (GLC).
📋 Resumo:
	Operação
	LLC é fechada?
	Descrição
	Observações
	União
	✅ Sim
	Junta cadeias das duas
	GLC com nova regra inicial S → S₁|S₂
	Concatenação
	✅ Sim
	Junta cadeias em sequência
	GLC com regra S → S₁ S₂
	Fecho de Kleene
	✅ Sim
	Repete 0 ou mais vezes
	GLC com S → S₁ S | λ 
	Interseção
	❌ Não
	Exemplo: aⁿbⁿcⁿ não é LLC
	Contraexemplo: aⁿbⁿcⁿ não é LLC
	Complemento
	❌ Não
	Contradiz a interseção
	Contradição com De Morgan
	Linguagem regular
	✅ É uma LLC
	Linguagem regular ⊆ LLC
	Toda regular pode ser gerada porGLC
Lema da altura da árvore de derivação
🌳 1. O que é uma Árvore de Derivação?
· É uma representação em forma de árvore que mostra como uma cadeia é derivada a partir do símbolo inicial de uma gramática.
· A raiz é o símbolo inicial da gramática.
· Os nós internos representam variáveis (não-terminais).
· Os nós folhas são os símbolos terminais (que formam a cadeia derivada).
🧠 Importância: Árvores de derivação são muito usadas para analisar linguagens formais e compiladores, pois mostram a estrutura da linguagem.
📏 2. Profundidade e Altura da Árvore
· Profundidade de um nó: número de passos desde a raiz até o nó.
· Altura da árvore: maior profundidade de todos os nós.
· Exemplo: 
Profundidade do nó E = 3, 
Altura da árvore = 4
🧱 3. Forma Normal de Chomsky (CNF)
· Uma gramática livre de contexto (GLC) está em forma normal de Chomsky quando as produções seguem estas regras:
· A → BC (duas variáveis)
· A → a (um terminal)
· Isso limita o crescimento da árvore, pois cada regra gera no máximo duas ramificações por vez.
🛑 Não pode: Produções como A → aA ou A → aa (com mais de um terminal ou terminal misturado com variável)
Exemplo válido na CNF:
S → AB
A → a
B → b
✅ Está na forma normal de Chomsky!
Exemplo inválido (violam as condições da CNF):
S → AAB ❌ (três símbolos no lado direito)
A → aa ❌ (dois terminais juntos)
· Logo, qualquer gramática livre de contexto tem uma gramática equivalente na forma normal de Chomsky.
🧮 3. Lema da Altura da Árvore de Derivação
· Se uma GLC está em CNF e “A” é uma árvore de derivação com caminho mais longo de comprimento k, então a altura da árvore é menor ou igual a .
🧠 O que isso quer dizer?
· Quanto maior a profundidade de derivação, mais alta a árvore.
· Porém, como na CNF cada passo da derivação divide em no máximo dois filhos, a altura total da árvore cresce de forma controlada, limitada por uma fórmula: 
Altura ≤ , onde k é o comprimento máximo do caminho.
🧪 Demonstração com Indução
 ➡️ Passo 1: Base da indução (k = 1)
· Quando o caminho mais longo da árvore tem comprimento 1, isso quer dizer:
· A raiz tem um filho apenas que é um símbolo terminal (como A → a).
· Então a altura da árvore = 1
· Pois: ✅
➡️ Passo 2: Passo indutivo (k > 1)
· Como estamos em CNF, a raiz tem dois filhos: S → S₁S₂ (CNF: A → BC).
· Cada subárvore tem caminho com comprimento .
· Pela hipótese de indução, cada subárvore tem altura .
· Então, a altura da árvore total é:
 
· Logo a altura total da árvore é 
🌟 5. Resumo:
· 🌳 Árvores de derivação representam o processo de geração de uma cadeia por uma gramática.
· 📏 A altura da árvore é a profundidade máxima de seus nós.
· ⚙️ Gramáticas em Forma Normal de Chomsky têm produções restritas a A → BC ou A → a.
· 📐 O lema da altura diz que se o caminho mais longo tem comprimento k, então a altura da árvore .
· 📊 A prova usa indução matemática, considerando que cada nível pode gerar no máximo o dobro do anterior.
Lema do bombeamento
🧠 1. O que é o Lema do Bombeamento?
· É uma técnica para provar que uma linguagem NÃO é livre de contexto, ou seja, que não são regulares.
· Ele não garante que uma linguagem seja LLC, mas pode provar que ela não é, se quebrar as condições do lema.
· Funciona como uma prova por contradição: Você supõe que a linguagem é LLC e usa o lema para mostrar que ela não pode ser.
· O lema do bombeamento mostra que LLC têm padrões repetitivos específicos (como a imagem ao lado).
· Se uma linguagem não respeita esse padrão, então ela não é LLC.
📘 2. Condições do Lema do Bombeamento para LLC
· Se L for uma linguagem livre de contexto, então existe um número natural n tal que:
· Qualquer cadeia z ∈ L com comprimento z ≥ n pode ser escrita como:
✅ z = u v w x y (cinco partes da palavra)
· E precisa obedecer às 4 condições abaixo:
1. 📏 |vx| ≥ 1 → as partes v e x não podem ser vazias ao mesmo tempo.
2. 🔢 |vwx| ≤ n → as partes v, w e x juntas não podem ultrapassar o valor n.
3. 🔁 Para todo k ≥ 0, a cadeia uvᵏwxᵏy também deve pertencer à linguagem → ou seja, podemos “bombear” (repetir ou remover) v e x quantas vezes quiser e a cadeia ainda precisa estar na linguagem.
🔎 Se ao tentar aplicar isso dá errado, temos uma contradição → a linguagem não é LLC.
⚠️ 3. Como usamos esse lema na prática?
Para provar que uma linguagem NÃO é LLC, siga estes passos:
1. Assuma que a linguagem é livre de contexto.
2. Pegue uma cadeia z da linguagem tal que |z| ≥ n.
3. Divida z como z = uvwxy, respeitando as regras.
4. Escolha um valor de k (normalmente k = 0 ou 2) e bombeie: uvᵏwxᵏy.
5. Se essa nova cadeia não pertence à linguagem, então existe contradição.
6. Portanto, a linguagem não é LLC.
✍️ Exemplo: Mostre que L = { aⁿbⁿcⁿ | n ≥ 1 } não é livre de contexto.
Objetivo: Provar que a linguagem L = { aⁿbⁿcⁿ | n ≥ 1 } não é livre de contexto.
✅ Passo 1: Assuma que L é uma LLC.
· Pelo lema, existe um número n tal que qualquer cadeia com tamanho ≥ n pode ser escrita como uvwxy, respeitando as 4 condições.
✅ Passo 2: Escolha uma cadeia da linguagem com tamanho ≥ n.
· Use a cadeia z = aⁿbⁿcⁿ → tem n a's, n b's e n c's. → ela tem 3n letras
· Então |z| = 3n ≥ n, logo pode aplicar o lema.
✅ Passo 3: Divida z = uvwxy, com:
· |vx| ≥ 1
· |vwx| ≤ n
⚠️ Como vwx tem no máximo n símbolos, ele não cobre a cadeia toda. Então, ele fica dentro de no máximo 2 blocos de letras. Isso significa que v ou x não podem conter todos os três símbolos (a, b e c). Ex: só entre os a's e b's, ou entre b's e c's).
✅ Passo 4: Analisando os possíveis casos:
🔁 CASO 1: v ou x contém só “a” e “b” → ao repetir, parte das letras “c” não será repetida → ❌ não está mais no formato aⁿbⁿcⁿ.
🔁 CASO 2: v ou x contém só “b” e “c” → repetir muda o número de “a” em relação aos outros → ❌ não está em L
🔁 CASO 3: v ou x contém apenas um símbolo repetido (só “a”, “b” ou “c”)
· Se fizermos k = 2 → repetimos v e x → o número de uma letra aumenta → ❌ sai do padrão aⁿbⁿcⁿ
· Se fizermos k = 0 → removemos v e x → o número de uma letra diminui → ❌ sai do padrão
✅ Conclusão:
· Em todos os casos, após bombear, a cadeia sai da linguagem.
· Isso contradiz o lema.
· 🎯 Portanto, L = {aⁿbⁿcⁿ | n ≥ 1} NÃO é livre de contexto.
🧾 Resumo:
· O lema do bombeamento para LLC ajuda a provar que uma linguagem NÃO é livre de contexto.
· Divide a cadeia em 5 partes: uvwxy, com regras específicas.
· Se qualquer bombeamento faz a cadeia sair da linguagem, então a linguagem não é LLC.
· Exemplo clássico: {aⁿbⁿcⁿ} não é LLC pois exige comparação entre 3 partes, o que LLCs não conseguem fazer (elas só comparam 2 grupos).
Propriedades decidíveis
📌 O que são propriedades decidíveis?
· São problemas que têm resposta “sim” ou “não” e para os quais existe um algoritmo capaz de resolver a questão.
· No contexto de gramáticas livres de contexto (GLC), duas propriedades principais podem ser decididas:
 1. Decidir se uma linguagem é vazia (vaziez)
💡 Pergunta: A gramática gera pelo menos uma cadeia formada apenas por símbolos terminais?
✔️ Como saber? Use o algoritmo de remoção de símbolos inúteis:
· Passo 1: Verifique quais símbolos geram cadeias de terminais.
· Passo 2: Se o símbolo inicial S não gerar uma cadeia só com terminais → L(G) é vazia.
· Caso contrário → L(G) não é vazia.
🧠 Importante: É possível eliminar produções nulas antes, para facilitar a verificação.
 2. Decidir se uma linguagem é finita
💡 Pergunta: A gramática gera um número limitado de cadeias, ou pode gerar infinitas?
✔️ Como saber? Basta analisar o grafo direcionado construído a partir das regras de produção da gramática.
🔁 Passo a passo para verificar finitude:
· Passo 1: Transforme a gramática em um grafo
· Cada não terminal vira um vértice.
· Cada produção vira uma seta (aresta).
Exemplo: Se há a produção S → AB, você cria uma seta de S para A e uma de S para B.
· Passo 2: Verifique se há ciclos (loops) no grafo
· Sem ciclos → A linguagem é finita.
· Com ciclos → A linguagem é infinita.
🔍 Exemplos práticos com os diagramas enviados
✅ Exemplo de linguagem finita
📘 Gramática: 
S → AB
A → BC
B → a
C → a
📊 Grafo (imagem· Domínio → elementos de entrada
· Contradomínio → possíveis saídas
· Imagem → saídas realmente utilizadas
Exemplo de funções: 
✅ É uma função, pois todo elemento do conjunto A possui um correspondente em B.
✅ É uma função. Por mais que exista um elemento no conjunto B que não é correspondente de nenhum elemento do conjunto A, esse fato não contradiz a definição, pois todos os elementos do A possuem um único correspondente em B.
✅ É uma função. Por mais que exista um elemento no conjunto B que é correspondente de dois elementos no conjunto A, essa relação também é uma função, pois as restrições são para o conjunto A, ou seja, um elemento de A não pode ter dois correspondentes em B, mas um elemento de B pode ser correspondente de dois elementos em A.
✅ O que NÃO é uma função: 
· Se um único elemento do domínio se liga a dois ou mais elementos diferentes do contradomínio, então não é função.
📌 Exemplo: 
❌ Isso não é uma função, pois existe um elemento de A que não possui nenhum correspondente em B.
❌ Isso não é uma função, pois existe um mesmo elemento de A relacionado a dois elementos diferentes de B.
✅ Tipos de funções
· Quando analisamos a relação entre o domínio e o contradomínio, existem três classificações possíveis: uma função pode ser injetora, sobrejetora e bijetora.
Função Injetora (um-para-um) 
· Cada elemento de A vai para um elemento diferente em B. 
· Não há dois elementos diferentes de A indo para o mesmo elemento em B. 
📌 Regra: (∀x1, x2∈ A)x1 ≠ x2 ⇒ f(x1) ≠ f(x2)
Lê-se: Para quaisquer elementos x₁ e x2 pertencentes ao conjunto A, se x₁ ≠ x₂, então f(x₁) ≠ f(x₂).
	
Elementos diferentes do conjunto A possuem imagens diferentes no conjunto B.
Função Injetora
	
Dois elementos diferentes do conjunto A que possuem o mesmo correspondente no conjunto B, o que faz com que essa função não seja injetora.
Função Não Injetora
Função Sobrejetora
· Todo elemento de B é "alvo" de pelo menos um elemento de A.
· A imagem da função é igual ao contradomínio. 
📌 Regra: (∀y)y ∈ B ⇒ ∃x ∈ A : f(x)=y
Lê-se: Para todo y, onde y ∈ B, então existe x ∈ A, tal que f(x) = y.
	
Todos os elementos do seu contradomínio (B) são imagem de pelo menos um elemento no domínio (A).
Função Sobrejetora
	
Um elemento do conjunto B que não é imagem de nenhum dos elementos do conjunto A, logo dizemos que essa função não é sobrejetora.
Função Não Sobrejetora
Função Bijetora
· É injetora e sobrejetora ao mesmo tempo.
· Ou seja:
· Cada elemento de A se liga a um único e exclusivo elemento de B.
· E todos os elementos de B são usados. 
· Importante notar que eles apresentam o mesmo número de elementos.
Função Bijetora
· O domínio dessa função é o conjunto A = {-1, 0, 1, 2}. 
· O contradomínio reúne os elementos, B = {4, 0, -4, -8}. 
· O conjunto imagem da função é definido por: Im(f) = {4, 0, -4, -8}. ← A imagem e o contradomínio são iguais.
✅ Gráfico de uma função
· É o conjunto de pares ordenados (x, f(x)). 
· Forma:
{(x, f(x)) : x ∈ D} ou {(x, y) ∈ D x I : x ∈ D e y=f(x)}
· Ou seja, você plota no plano cartesiano os pontos da função.
📌 Exemplo gráfico da função y = x (função identidade) 
Grafos
✅ O que é um grafo?
· Um grafo é uma estrutura que representa relações entre elementos.
· É formado por:
· V: conjunto de vértices (também chamados de nós)
· A: conjunto de arestas ou arcos, que ligam os vértices.
· Representação: G = (V, A)
📌 Dois vértices vi e vj são adjacentes se existe uma aresta entre eles:
 → (vi, vj) ∈ A
Exemplo de Grafo
Dados:
Grafo desenhado com círculos (vértices) conectados por linhas (arestas).
· G1 = (V1,A1)
· V1 = {0, 1, 2, 3}
· A1 = {(0, 1), (0, 2), (0, 3), (1, 3)} 
➡️ Isso representa um grafo com 4 vértices e 4 arestas ligando:
· 0 | 1, 2, 3
· 1 | 3
✅ Aplicações dos Grafos
· Usados na construção de autômatos finitos (máquinas que mudam de estado conforme entradas).
· Representam redes, caminhos, conexões, mapas, entre outros.
Árvore 
✅ O que é uma árvore?
Uma árvore é um tipo especial de grafo que:
· É simples (sem laços e sem arestas repetidas),
· É acíclica (não forma ciclos),
· É conexa (todos os vértices estão conectados entre si por algum caminho).
✅ Características de Árvores
· Tem um nó raiz (o início da estrutura).
· Os ramos se estendem da raiz até os outros nós.
· Normalmente, a raiz fica no topo e os nós "crescem" para baixo.
· Os arcos apontam para baixo, da raiz para os filhos.
· A ordem da esquerda para a direita importa na visualização.
✅ Tipos de Árvores
🌿 Árvore n-ária
· Cada nó pai pode ter até n filhos.
🌿 Árvore binária
· Cada nó pai pode ter no máximo dois filhos.
· Pode ser:
· Vazia (sem elementos),
· Com uma raiz e duas subárvores (esquerda e direita),
· Cada nó tem um único caminho até a raiz.
📌 Em uma árvore binária:
· Folhas: nós sem filhos.
· Vértices internos: nós com pelo menos um filho (inclui a raiz, se não for folha).
✅ Profundidade e altura
· Profundidade de um nó (vértice): número de passos da raiz até ele.
· ALTURA (PROFUNDIDADE) DE UM NÓ – Representa o maior caminho existente entre o nó e nó folha (descendente dele) de maior nível. As folhas têm sempre altura igual a 1.
· Altura da árvore: Representa a número de nós do maior caminho. Representa a distância entre a raiz e um nó folha do maior nível da árvore.
✅ Aplicações de Árvores
· Muito usadas em:
· Derivações em linguagens computacionais
· Linguagens formais (especialmente importante)
· Aplicadas na prática para a análise e a construção de compiladores
Exemplo: Estrutura de frase (árvore de derivação)
Frase: 👉 “Antônia escreveu um livro de receitas”
· Sentenças dessa natureza geralmente seguem uma regra geral:
· SN = sintagma nominal (sujeito)
· SV = sintagma verbal (verbo + predicado)
· Cada uma dessas duas partes divide-se em outras menores, formando uma árvore de derivações.
· A sentença expressa é:  = 
· O SN tem um nome ou substantivo como núcleo do sujeito (N = Antônia).
· O SV tem seu núcleo no verbo (V = escreveu), mais o predicado (P = um livro de receitas).
🔹 A estrutura da frase pode ser representada como uma árvore:
➡️ Cada parte da frase é decomposta em partes menores até chegar nas palavras.
Questão 1. Sabendo que o conjunto A = {0, 1, 3, 4, 5, 7} e A – B = {1, 3, 5, 7}, então o conjunto B é:
A. {0, 1, 4, 5}
B. {0, 1, 4, 5, 7}
C. {0, 4}
D. {0, 1, 5}
E. {}
Resposta: B = {0, 4}
Questão 2. Considere o conjunto A com 3 elementos; o B, com 4; e o C, com 5. Nesse caso, verificamos que:
A. A∩B tem, no máximo, 2 elementos.
B. A∪C tem, no máximo, 5 elementos.
C. (A∪B)∩C tem, no máximo, 3 elementos.
D. (A∩B)∩C tem, no máximo, 3 elementos.
E. A∩C tem 3 elementos, pelo menos.
Resposta: 
💡 DICA IMPORTANTE: Quando não sabemos quais são os elementos dos conjuntos, usamos valores extremos (mínimo e máximo possíveis) para analisar o problema, com base nas quantidades dadas.
🔍 Analisando Alternativa por Alternativa:
A) A ∩ B tem, no máximo, 2 elementos.
· A tem 3 elementos.
· B tem 4 elementos.
👉 No máximo, A e B podem ter todos os 3 elementos de A também em B, se forem iguais.
✅ Então, a interseção pode ter até 3 elementos, e não só 2.
❌ Alternativa errada.
B) A ∪ C tem, no máximo, 5 elementos.
· A tem 3 elementos.
· C tem 5 elementos.
👉 Se não houver elementos repetidos entre A e C, então a união terá 3 + 5 = 8 elementos.
👉 No caso mais extremo (todos os 3 elementos de A também estiverem em C), a união teria apenas os 5 elementos de C, então:
✅ A ∪ C pode ter no máximo 8 elementos, e no mínimo 5.
Mas a alternativa diz que tem "no máximo 5 elementos", o que só seria possível se todos os elementos de A já estivessem em C, o que não pode ser garantido.
❌ Alternativa errada.
C) (A ∪ B) ∩ C tem, no máximo, 3 elementos.
Vamos entender isso por partes:
· A ∪ B → No máximo 3 (de A) + 4 (de B) = 7 elementos (se forem todos diferentes).
· Agora, (A ∪ B) ∩ C → Estamos comparando esse conjunto com C (que tem 5 elementos).
👉 A interseção entre (A ∪ B) e C pode ter no máximo os elementos que estão tanto em (A ∪ B) quanto em C.
👉 Comoao lado):
· S → A, S → B
· A → B, A → C
· (B e C não levam a ninguém, são terminais)
· ✅ Não há ciclos → linguagem é finita
🔄 Exemplo de linguagem infinita
🧮 Derivação: S → AB → BCB → aaB → aaa
📘 Gramática:
S → AB
A → SC | a
B → SC | a
C → AB | b
📊 Grafo (imagem ao lado):
· A → S
· S → A
· B → S
· C → A
· E várias outras conexões recursivas...
· ✅ Há ciclos → linguagem é infinita
✅ Conclusão:
	Propriedade
	Como verificar?
	Resultado com grafo
	Vaziez
	Ver se o símbolo inicial gera cadeia terminal
	Se não gera → linguagem é vazia
	Finitude
	Procurar ciclos no grafo de produções
	Se há ciclo → linguagem infinita
Exemplos Práticos
✅ 1. Toda linguagem regular é uma LLC
· Toda linguagem regular pode ser gerada por uma gramática livre de contexto (GLC).
· Isso significa que as linguagens regulares estão contidas dentro das linguagens livres de contexto.
📌 Teorema: Toda linguagem regular é gerada por uma GLC.
🛠️ Como transformar um AFD em GLC: Se temos um autômato finito determinístico (AFD), podemos construir uma GLC que gera a mesma linguagem:
· Cada estado do AFD vira um não terminal na GLC.
· O estado inicial do AFD vira o símbolo inicial S da GLC.
· Para cada transição δ(q1, a) → q2:
· Crie a produção q1 → a q2.
· Se q2 é estado final, adicione também:
· q1 → a (indicando que pode terminar ali).
· ✅ Isso garante que a gramática construída é livre de contexto.
✅ 2. Aplicação prática das GLCs: Analisadores sintáticos
· Um compilador usa uma GLC para verificar a sintaxe do código.
· Se a entrada satisfaz a gramática, o compilador gera uma árvore de derivação.
· Se não satisfaz, ele exibe mensagens de erro de sintaxe.
🧪 Exemplo: Identificadores na linguagem C
Gramática para identificadores:
 ::= letra (letra | dígito)*
 ::= a|b|c|...|z|A|B|C|...|Z
 ::= 0|1|2|3|4|5|6|7|8|9
🧾 Exemplo de código: Um programador declara as seguintes variáveis:
int capital; // OK
int r_o_i; // OK
int year; // OK
int 1st_year_interest; // ❌ Erro: começa com dígito
✅ Regra: identificadores devem começar com uma letra.
✅ 3. Construção de uma GLC para inteiros ímpares
🎯 Objetivo: Criar uma gramática que gere números inteiros ímpares, com sinal positivo ou negativo.
ℹ️ Regras:
· Um número ímpar termina em: 1, 3, 5, 7, 9.
· Um número pode começar com + ou -.
🧱 Construção da gramática
Símbolos não terminais: {S, , , , , }
📐 Regras de produção:
S → 
 → + | -
 → 
 → | λ
 → 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
 → 1 | 3 | 5 | 7 | 9
🧪 Exemplo prático passo a passo:
· Entrada válida: +1247
Passos:
1. S → 
2. → +
3. → 
4. → 2 4 (parte intermediária)
5. → 7 (termina com dígito ímpar)
✅ Resultado: Cadeia aceita pela GLC
· Entrada inválida: -1248
❌ Rejeitado porque o último dígito (8) não pertence ao conjunto de dígitos ímpares (1, 3, 5, 7, 9).
Questão 1. Considerando que um conjunto é fechado se e somente se a operação em dois elementos do conjunto produz outro elemento do próprio conjunto, avalie as seguintes opções relacionadas com uma linguagem livre de contexto:
(F) Não fechada para união
(V) Fechada para concatenação
(V) Não fechada para complementação
(V) Fechada para fecho de Kleene
(V) Fechada para diferença
Quais as afirmativas são verdadeiras (V) e falsas (F)?
A. V, V, V, V, V
B. F, V, V, F, V
C. F, V, V, V, V
D. F, V, F, V, V
E. V, V, V, F, F
Uma linguagem livre de contexto é fechada para união, concatenação, fecho de Kleene e diferença, não sendo fechada para interseção e complementação.
Questão 2. Considerando que o lema do bombeamento é uma ferramenta eficaz para mostrar que certas linguagens não são regulares, analise as seguintes afirmativas:
I - O lema de bombeamento para linguagens regulares é baseado no fato de que todas as cadeias em uma linguagem regular devem apresentar um certo padrão repetitivo.
II - O lema de bombeamento para LLC é usado para provar que certos conjuntos não são livres de contexto.
III - O lema de bombeamento pode ser outro tipo de forma normal, além da BNF, onde o número de símbolos à direita de uma produção é estritamente limitado.
Quais são as afirmativas verdadeiras?
A. I e II.
B. I e III.
C. I, II e III.
D. Somente I.
E. Somente III.
A forma normal de Chomsky é um outro tipo de forma normal, além da BNF, onde o número de símbolos à direita de uma produção é estritamente limitado, o que invalida a opção III.
TEMA 5. COMPUTABILIDADE E A MÁQUINA DE TURING
Módulo 1. A tese de Church-Turing
Máquina de Turing (MT)
📌 Principais conceitos da Máquina de Turing
· Tese de Church-Turing
· É uma hipótese formulada por Alonzo Church e Alan Turing.
· Afirma que qualquer cálculo feito por um artefato mecânico (como um computador) pode ser representado por algoritmos que a máquina de Turing consegue executar.
· Origem da Máquina de Turing
· Criada por Alan Turing em 1936, antes da existência dos computadores.
· É uma máquina abstrata que simula o funcionamento de qualquer processo computacional.
· O que é a Máquina de Turing (MT)?
· Um modelo matemático teórico capaz de reproduzir qualquer algoritmo.
· Baseia-se em linguagem irrestrita, ou seja, pode interpretar qualquer tipo de linguagem (incluindo aquelas muito complexas).
· Importância da MT na computabilidade
· Mostra o que é possível ou impossível de calcular usando algoritmos.
· Serviu de base para criar a teoria dos problemas indecidíveis.
· ❌ Problemas Indecidíveis
· São situações em que não existe nenhum algoritmo capaz de resolver o problema.
· Mesmo os computadores mais avançados não conseguem dar uma resposta.
· 🛠️ Por que a Máquina de Turing é chamada de “modelo”?
· A Máquina de Turing é um modelo teórico e abstrato de computação.
· Ela representa, de forma simplificada, como qualquer computador moderno pode processar informações e executar algoritmos.
· Apesar de não existir fisicamente, ela é usada para entender os princípios fundamentais da computação e o que é computável ou não.
· 📌 Papel fundamental do modelo
· Mostra os limites da computação, ou seja, quais problemas podem ser resolvidos por algoritmos e quais são indecidíveis.
· Influenciou diretamente a criação da lógica dos computadores atuais, como processadores, algoritmos e linguagens de programação.
🧠 O que é o Diagrama Mecânico da MT?
É uma descrição do funcionamento interno da máquina — como ela lê, grava e se movimenta sobre a fita. Isso é feito por meio de transições de estado, com base no símbolo lido na fita e no estado atual da máquina.
⚙️ Componentes da MT:
1. Fita de entrada
· Parecida com uma esteira infinita, com várias células.
· Cada célula contém um símbolo do alfabeto de entrada (como a, b, etc.) ou um espaço em branco (B).
· É infinita para os dois lados, o que permite memória ilimitada.
· Armazena os dados que serão processados.
2. Cabeçote de leitura e gravação
· Se move pela fita, lendo o símbolo atual e escrevendo um novo símbolo, se necessário.
· Também decide para onde vai se mover: esquerda (L), direita (R) ou ficar parado (H).
3. Controle finito
· É o “cérebro” da máquina.
· Possui um conjunto de estados (q0, q1, etc.) e funções de transição, que definem o comportamento da máquina com base na leitura atual. 
🔄 Como a Máquina funciona?
Imagine a MT como um robô que anda por uma fita e decide o que fazer com base em instruções:
Etapa 1: Leitura
· A cabeça lê o símbolo atual da fita (por exemplo, lê “a”).
Etapa 2: Consulta à função de transição (δ)
· O controle finito verifica:
· "Estou no estado “q0”, e li um “a”. O que devo fazer?"
Etapa 3: Execução da ação definida por δ
Com base na resposta da função de transição, a MT:
1. Escreve um novo símbolo na célula (por exemplo, escreve “X” no lugar do “a”).
2. Muda de estado (por exemplo, permanece em “q0” ou muda para “q1”).
3. Move-se para a esquerda (L) ou direita (R) na fita.
4. Se não houver mais nenhuma instruçãopossível, ela para (H).
🧠 Comparação com autômatos finitos
· Um autômato finito apenas lê os dados — não os modifica.
· A Máquina de Turing lê e escreve na fita, o que lhe dá muito mais poder computacional.
✅ Quando uma cadeia é aceita
· Autômato finito: aceita se a leitura termina em um estado final.
· Máquina de Turing: aceita se a fita é lida e a máquina chega a uma parada (halt)
✅ Resumo do ciclo de funcionamento
· A cabeça lê o símbolo atual da fita.
· A função de transição δ define:
· O novo estado
· O novo símbolo a ser escrito
· A direção do movimento
· A cabeça executa a instrução e continua ou para.
Descrição Instantânea (DI) da máquina de Turing:
· Representa o estado atual da máquina (fita, posição da cabeça, estado)
· A DI geralmente é escrita assim:
🧾 Definição formal da MT:
A MT é definida como: 
· Q: conjunto de estados
· Σ: alfabeto de entrada
· Γ: alfabeto da fita (inclui Σ e o branco B)
· δ: função de transição
· q0: estado inicial
· B: símbolo branco
· F: estados de aceitação (finais)
🔄 Função de transição: 
A transição é uma quíntupla: , ou seja: 
· s: estado atual
· i: símbolo lido na fita
· s’: próximo estado
· i’: símbolo escrito na fita
· d: direção do movimento (L = esquerda, R = direita, H = parar)
Regras:
➡️ Regra 1: Não pode haver duas quíntuplas com o mesmo início (s, i)
👉 Isso quer dizer que, para cada combinação de estado e símbolo lido, a MT deve ter uma única ação possível.
· Exemplo: Se a MT tem a quíntupla: 
· Ela não pode ter outra do tipo: pois ambas começam com → isso quebraria a regra.
🧠 Por quê isso é importante? Porque isso torna a MT determinística:
· Ou seja, não há dúvida sobre o que fazer em cada situação.
· Para cada símbolo lido e estado atual, a máquina tem apenas uma escolha.
➡️ Regra 2: Se não houver quíntupla correspondente, a máquina para
👉 Se a máquina estiver em um certo estado e ler um símbolo da fita, mas não existir uma quíntupla que comece com essa combinação, ela para automaticamente.
· Exemplo: Se o estado atual é e o símbolo lido é , mas não há quíntupla do tipo , então a máquina para.
✅ Exemplo: O exemplo abaixo mostra o movimento da cabeça de leitura/gravação e o conteúdo da fita de entrada para a cadeia 'abba' percorrida por uma MT que possui a seguinte função de transição de estados:
⚙️ Regras de transição da MT: 
δ(q0, a) → (q0, X, R)
δ(q0, b) → (q0, b, R)
δ(q0, B) → (q1, B, L)
δ(q1, b) → (q1, Y, L)
δ(q1, X) → (q1, X, L)
δ(q1, B) → (q1, B, H)
🔁 Interpretação:
· No estado q0, ao ler a, escreve X e anda para a direita.
· No estado q0, ao ler b, mantém b e anda para a direita.
· Quando lê B, muda para estado q1 e volta à esquerda.
· No estado q1, ao ler b, escreve Y e anda para a esquerda.
· Ao ler X, mantém e continua andando para a esquerda.
· Quando lê B novamente, a máquina para (H).
🧮 Passos do processamento (imagem):
1. Entrada: B a b b a B → Cabeça sobre o primeiro a, estado q0
2. Lê a, escreve X, anda p/ direita → Estado ainda q0
3. Lê b, mantém, anda p/ direita
4. Lê outro b, mantém, anda p/ direita
5. Lê a, escreve X, anda p/ direita
6. Lê B, muda p/ estado q1, anda p/ esquerda
7. Lê X, mantém, anda p/ esquerda
8. Lê b, escreve Y, anda p/ esquerda
9. Lê b, escreve Y, anda p/ esquerda
10. Lê X, mantém, anda p/ esquerda
11. Lê B, máquina para (H)
🎯 Resultado Final na Fita: B X Y Y X B
✅ Conclusão:
· A MT é uma máquina teórica que lê, escreve e decide com base em regras.
· É mais poderosa que autômatos finitos, pois modifica a fita.
· O exemplo mostra como ela processa a palavra ‘abba’, marcando os a com X e os b com Y, e depois para.
Construção da máquina de Turing
Exemplo: Vamos construir uma Máquina de Turing (MT) que reconhece a linguagem , e mostrar uma descrição instantânea (DI) para a cadeia “aaabbb”
📘 Objetivo: Criar uma Máquina de Turing que reconhece cadeias onde:
· A quantidade de letras “a” é igual à de letras “b”.
· Todos os “a” aparecem antes dos “b”.
· Exemplo: ab, aabb, aaabbb, etc.
⚙️ Etapas da construção da MT (de forma simplificada)
🔁 Ideia geral do funcionamento: A máquina funciona marcando os símbolos já processados:
· Substitui o primeiro a por X
· Procura o primeiro b à direita e o substitui por Y
· Volta ao início e repete o processo
· Ao final, verifica se todos os a viraram X e todos os b viraram Y
· Se tudo estiver correto, a máquina para e aceita a cadeia
📌 Funções de transição principais:
	Transição
	Explicação
	δ(q0, a) → (q1, X, R)
	Marca o primeiro a com X e vai à direita
	δ(q1, a) → (q1, a, R)
	Continua passando por a
	δ(q1, b) → (q2, Y, L)
	Marca o primeiro b com Y e volta à esquerda
	δ(q2, a) → (q2, a, L)
	Volta passando pelos a
	δ(q2, X) → (q0, X, R)
	Ao encontrar o X, volta ao início para repetir o processo
	δ(q1, Y) → (q1, Y, R)
	Pula os Y já marcados
	δ(q2, Y) → (q2, Y, L)
	Pula os Y enquanto volta
	δ(q0, Y) → (q3, Y, R)
	Ao não encontrar mais a, passa para a verificação final
	δ(q3, Y) → (q3, Y, R)
	Continua passando pelos Y
	δ(q3, B) → (q4, B, H)
	Encontra um branco e para (cadeia aceita!)
🧪 Exemplo passo a passo: cadeia "aaabbb"
🔹 Estado inicial da fita:
B B B B a a a b b b B B B
 ↑ (cabeça em `a`, estado q0)
🔹 Etapas principais (com base nas imagens):
1. Lê “a” no estado q0 → escreve X, vai para q1
2. Lê dois “a” em q1 → só anda pra direita
3. Encontra primeiro “b” → escreve Y, muda pra q2, volta para a esquerda
4. Volta até X, muda para q0 e repete o processo
5. Marca mais um “a” como X e o próximo “b” como Y, e assim por diante...
6. Quando todos os “a” viram X e os “b” viram Y, entra no estado q3
7. Passa por todos os Y e encontra B → entra em q4 e para.
🔹 Resultado final: ✅ B X X X Y Y Y B → MT parou → cadeia aceita! 
✅ Resumo didático em tópicos:
· A MT marca pares de ‘a’ e ‘b’, transformando-os em X e Y.
· Repete o processo até que não haja mais ‘a’ para marcar.
· Então verifica se tudo virou X e Y e para ao encontrar branco.
· Se parar corretamente, a cadeia está em aⁿbⁿ → aceita.
Tipos de máquinas de Turing
Há dois tipos principais de Máquina de Turing (MT):
· Máquina de Turing Não Determinística (MTN)
· Máquina de Turing Universal (MTU)
🔷 1. Máquina de Turing Não Determinística (MTN)
📌 O que é?
· É uma máquina teórica que pode tomar decisões diferentes ao mesmo tempo.
· Ela funciona como se explorasse vários caminhos ao mesmo tempo, como se fosse "multiplicar" cópias de si mesma e testar todas as possibilidades.
· É uma variação da máquina de Turing comum.
· Diferença principal: Pode haver mais de uma transição possível, para uma mesma entrada.
· A função de transição retorna várias opções de movimento, como se a máquina pudesse "tentar vários caminhos ao mesmo tempo". 
· Exemplo simples: Imagine que você está em uma estrada e chega a um cruzamento.
· Uma MT normal escolhe um único caminho.
· Uma MTN segue todos os caminhos ao mesmo tempo.
🧠 Como funciona?
· Imaginamos que a MTN tenta todas as possibilidades ao mesmo tempo.
· Se uma das opções leva à aceitação, a cadeia é aceita.
· Para simular isso, usamos uma árvore de possibilidades (como um jogo de decisões).
🔧 Definição Formal: 
A MTN é definida como: (Q, Σ, Γ, δ, q0, B, F)
· Q: Conjunto de estados
· Σ: Alfabeto de entrada
· Γ: Alfabeto da fita
· δ: Função de transição com várias opções possíveis: 
· q0: Estado inicial
· B: Branco (símbolo especial)
· F: Conjunto de estados finais
✨ Exemplo simples de transição:
δ(q0, 0) → (q0, 0, R) e (q1, 1, R)
🧠 Isso significa que:
· No estado q0 lendo 0, a máquina pode:
· Ficar em q0, manter o 0, ir para a direita
· OU ir para q1, escrever 1, e também ir para a direita
🌳 Como simular uma Máquina de Turing Não Determinística (MTN) a partir de uma MT determinística?
· Constrói-se uma árvore de computação com todos os caminhos possíveis.
· A MT determinística (T2) faz uma busca em largura nessa árvore:
· Analisa todas as configurações de um nível.
· Gera os “filhos” (novas configurações) para o próximo nível.
· Se algum ramo leva ao estado de parada, a máquina aceita a cadeia.
📌 Importante: Toda linguagem aceita por uma MTNtambém pode ser aceita por uma MT comum — mas com tempo maior, geralmente exponencial.
🧪 Exemplo: Construir uma MT sobre {a, b} que contém uma subcadeia ‘abb’.
🔹 Linguagem desejada: Todas as cadeias sobre {a, b} que contenham ‘abb’ como subcadeia
🔹 Expressão regular correspondente: 
🔁 Funções de transição:
δ(q1,a) → (q1,a,R) , (q2,a,R) ← aqui está o não determinismo!
δ(q1,b) → (q1,b,R)
δ(q2,b) → (q3,b,R)
δ(q3,b) → (q4,b,R)
δ(q4,a) → (q4,a,R)
δ(q4,b) → (q4,b,R)
δ(q4,B) → (qf,B,H) ← aceitação
🧭 Explicação passo a passo:
1. Estado inicial: q1
· Se ler ‘a’: duas opções:
· Continua em q1 (ainda procurando o início de ‘abb’)
· Vai para q2, iniciando o reconhecimento da subcadeia ‘abb’
2. Em q2, se ler ‘b’ → vai para q3
3. Em q3, se ler outro ‘b’ → vai para q4
4. Em q4, ignora o restante da fita e vai até o branco (B)
5. Se chegar ao branco, para em qf → cadeia aceita
✅ Conclusão:
· A MTN é mais poderosa na prática, pois pode explorar vários caminhos em paralelo.
· Embora a MT determinística consiga simular a MTN, ela o faz de forma mais lenta.
· O não determinismo permite decisões "em paralelo", como se a máquina pudesse tentar várias possibilidades ao mesmo tempo.
🔷 2. Máquina de Turing Universal (MTU)
O que é uma Máquina de Turing Universal (MTU)?
· É uma versão especial da Máquina de Turing que pode simular qualquer outro computador ou máquina de Turing. 
· Equivale, em poder computacional, a um computador digital. 
· Uma máquina de Turing é chamada de máquina de Turing universal se simular o comportamento de um computador digital.
· Pode executar qualquer algoritmo, desde que receba:
· O algoritmo (programa)
· Os dados de entrada
🧠 Diferença entre MT comum e um computador real:
· A máquina de Turing é projetada para executar apenas um programa.
· Computadores reais são reprogramáveis.
✅ A MT se torna Universal quando: Ela aceita:
· 📥 Dados de entrada
· ⚙️ Algoritmo (programa) para processar os dados
📜 Requisitos que definem um algoritmo válido para uma MTU:
1. ✅ Conjunto finito de instruções, escritas com símbolos finitos
2. 🔁 Sempre termina após um número finito de passos
3. ✍️ Pode ser feito com papel e lápis, sem computador
4. 🧠 Não exige inteligência – requer apenas que seja seguida as instruções
📌 Exemplo: Algoritmo de Euclides para calcular o MDC (máximo divisor comum) entre dois números é um exemplo de algoritmo que a MTU pode executar.
💡 Por que a MTU é importante?
· Porque ela simula qualquer máquina de Turing projetada para tarefas diferentes.
· Ou seja, é como um computador universal capaz de rodar qualquer programa.
🔧 Como criar uma MT Universal? (em teoria)
Embora seja complexo na prática, uma MTU pode ser construída com:
· 📀 Várias cabeças de leitura e gravação (MT de múltiplas cabeças)
· 📄 Várias fitas de entrada (MT de múltiplas fitas)
· 🧱 Movimento em várias direções (MT com várias dimensões – MT k-dimensional)
· 🗂️ Memória extra, como uma pilha (semelhante a uma pilha de dados)
Essas técnicas aumentam a capacidade da MT sem mudar sua natureza teórica.
🎯 Conclusão sobre MTU:
· A Máquina de Turing Universal é o modelo teórico mais próximo de um computador real.
· Ela não é prática para uso direto, mas é fundamental para entender o que é possível calcular.
· Todo programa de computador, se puder ser descrito com um algoritmo, pode ser executado por uma MTU.
✅ Resumo Final
	Tipo de MT
	Características principais
	MT Determinística
	Uma única transição por estado e símbolo
	MT Não Determinística (MTN)
	Várias possibilidades para o mesmo estado/símbolo
	MT Universal (MTU)
	Simula qualquer outra MT; funciona como um computador
Tese de Church-Turing 
📌 1. O que é a Tese de Church-Turing?
· A tese afirma que qualquer algoritmo pode ser representado por uma máquina de Turing.
· Ou seja, qualquer coisa que possa ser calculada por um computador pode ser feita por uma máquina de Turing.
🧠 2. Quem são Church e Turing?
· Alonzo Church: matemático que propôs que funções computáveis representam algoritmos.
· Alan Turing: criou a Máquina de Turing, um modelo teórico que simula qualquer algoritmo possível.
💡 3. Qual a ideia central?
· Se você consegue escrever um programa, então esse programa pode ser simulado por uma máquina de Turing.
· Por isso, nenhum outro modelo de computação seria mais poderoso do que a máquina de Turing.
· Todo computador digital moderno, por mais avançado, tem o mesmo poder teórico de uma máquina de Turing. A única diferença está na velocidade e memória.
✅ 4. Por que isso é aceito?
Porque até hoje:
· Nenhum exemplo foi encontrado de algoritmo computável que uma máquina de Turing não consiga resolver.
· Outros modelos propostos não são mais poderosos.
· Todo programa de computador pode ser traduzido para uma máquina de Turing.
· O contrário também é verdadeiro: qualquer máquina de Turing pode ser traduzida para linguagens como Python, C, Java...
🔎 Resumo prático: A tese diz que tudo que você consegue fazer em um programa (como em Python, por exemplo), pode ser feito por uma máquina de Turing.
🧱 Hierarquia de Chomsky 
A Hierarquia de Chomsky classifica as linguagens formais de acordo com sua complexidade. Existem 4 tipos:
	Tipo
	Nome da Gramática
	Tipo de Linguagem
	Máquina Reconhecedora
	0
	Irrestrita
	Recursivamente enumerável
	Máquina de Turing
	1
	Sensível ao contexto
	Sensível ao contexto
	Autômato linearmente limitado
	2
	Livre de contexto
	Livre de contexto
	Autômato com pilha (PDA)
	3
	Regular
	Regular
	Autômato finito (DFA/NFA)
🔁 Como lembrar:
· Tipo 0 → mais geral → qualquer linguagem computável → máquina de Turing
· Tipo 3 → mais simples → regras simples como "só aceitar palavras com 'ab'" → autômatos finitos
📌 Conclusão:
· A Tese de Church-Turing define o limite do que é possível calcular.
· A Hierarquia de Chomsky organiza as linguagens e os autômatos que podem reconhecê-las.
· Tudo o que pode ser programado em um computador, pode ser descrito por uma máquina de Turing, e por isso a tese é amplamente aceita.
Questão 1. A máquina de Turing é o formato de máquina para reconhecer a linguagem
A. tipo 0.
B. tipo 1.
C. tipo 2.
D. tipo 3.
E. tipo 4.
Questão 2. A máquina de Turing (MT) é um dispositivo teórico conhecido como máquina universal, que foi concebido pelo matemático britânico Alan Turing, muitos anos antes de existirem os modernos computadores digitais. Analise as afirmativas relacionadas com a MT:
I. A máquina de Turing não aceita linguagem regular.
II. A máquina de Turing aceita linguagem livre de contexto.
III. A máquina de Turing aceita linguagem sensível ao contexto.
Quais são as opções verdadeiras?
A. I, II e III
B. I e II
C. I e III
D. II e III
E. I
Módulo 2. Decidibilidade
Linguagens recursivas e recursivamente enumeráveis
📌 1. Tese de Church e Máquina de Turing
· Segundo a Tese de Church, qualquer algoritmo computacional pode ser executado por uma máquina de Turing (MT).
· Mas... existem problemas que não têm solução algorítmica. Isso nos leva aos conceitos de decidibilidade:
· Problema decidível: existe um algoritmo que sempre resolve o problema.
· Problema indecidível: não existe algoritmo que resolva o problema para todas as entradas.
🔁 2. Função Recursiva – O que é?
· Uma função recursiva é uma função que chama a si mesma até atingir um caso base.
· Ela termina em um número finito de passos.
✅ Exemplo: Fatorial
fatorial(3) = 3 * fatorial(2)
 = 3 * (2 * fatorial(1))
 = 3 * (2 * 1 * fatorial(0))
 = 3 * 2 * 1 * 1 = 6
→ Note que há um caso base: fatorial(0) = 1.
📦 3. Conjunto Recursivo (ou Decidível)
· É um conjunto para o qual existe um algoritmo que decide (em tempo finito) se um elemento pertence ou não a ele.
Exemplos:
· Números pares
· Números primos
· Conjunto vazio
· Conjunto de todos os naturais
Exemplo: Verificar se um número é par
Leia i.
Se i == 0, pare e diga sim.
Se iseus elementos (talvez para sempre).
· Pode ou não parar se o elemento não estiver no conjunto.
Exemplo: Um programa que imprime todos os resultados de uma função f(i) com i = 0, 1, 2, 3...
1. i = 0
2. imprima f(i)
3. i = i + 1
4. vá para 2
O programa gera os elementos um a um, mas nunca decide se um número não pertence ao conjunto (ele apenas continua tentando).
🔤 5. Linguagem Recursiva
· É uma linguagem para a qual existe uma máquina de Turing que sempre para e:
· Aceita se a entrada está na linguagem.
· Rejeita se a entrada não está na linguagem.
Exemplo: Linguagens sensíveis ao contexto (como anbncn) são recursivas.
🔄 6. Linguagem Recursivamente Enumerável (RE)
· É uma linguagem para a qual existe uma máquina de Turing que:
· Aceita a cadeia válida (e para).
· Pode rejeitar ou entrar em loop para uma cadeia inválida.
➕ Características:
· A MT pode não parar para entradas inválidas.
· Ela apenas "reconhece" ou enumerará os elementos da linguagem.
Exemplo: A linguagem que contém todas as cadeias com algum padrão (por exemplo, todas que têm a subcadeia abb) pode ser recursivamente enumerável, mas não necessariamente recursiva.
🔁 7. Diferença entre Linguagem Recursiva e RE
	Linguagem
	Máquina de Turing
	Para em todos os casos?
	Tipo de decisão
	Recursiva
	Para e aceita/rejeita
	✅ Sim
	Decidível
	RE (enumerável)
	Pode aceitar ou entrar em loop
	❌ Não
	Semidecidível
📌 8. Resumindo com uma analogia simples:
· Linguagem Recursiva: é como um juiz que sempre dá o veredito, seja sim ou não.
· Linguagem RE: é como um juiz que só dá veredito se for sim. Se for não, ele fica pensando para sempre e nunca responde.
Linguagens vs. máquina de Turing
📌 1. Como uma Máquina de Turing (MT) aceita uma linguagem?
· Uma linguagem L é aceitável, se houver uma MT que para e aceita L ou para e rejeita.
· Ou seja, uma cadeia w é aceita por uma MT se ela para (Halt) em um estado de aceitação ():
· Se a MT não parar, há duas possibilidades ():
· ❌ Não há função de transição para o símbolo atual → a cadeia não pertence à linguagem ⇒ a MT para, mas rejeita.
· 🔁 A máquina entra em loop infinito → não é possível afirmar se a cadeia pertence ou não.
📘 2. Tipos de Linguagens para MT
Existem dois tipos principais de linguagens relacionadas à Máquina de Turing:
	Tipo de Linguagem
	Nome técnico
	MT sempre para?
	A resposta é sempre clara?
	Recursiva
	Turing-decidível
	✅ Sim (aceita ou rejeita)
	✅ Sim
	Recursivamente enumerável
	Turing-reconhecível
	❌ Nem sempre (pode entrar em loop)
	❌ Não sempre
✅ 3. Linguagem Recursiva (Turing-decidível)
· Existe uma MT que sempre para, para qualquer entrada.
· Ela diz sim se a cadeia está na linguagem e não se não estiver.
🎯 Exemplo: Verificar se um número é primo:
· Se X é primo, a MT para e aceita.
· Se não for, a MT para e rejeita.
➡️ Problemas assim são chamados de problemas de decisão (resposta: sim ou não).
🔁 4. Linguagem Recursivamente Enumerável (Turing-reconhecível)
· A MT para e aceita se a cadeia está na linguagem.
· Mas se a cadeia não estiver, a MT pode:
· Parar e rejeitar ou
· Entrar em loop infinito (não para nunca!).
⚠️ Isso é chamado de semidecidibilidade.
🧪 5. Exemplo prático de semidecidibilidade
Considere esta máquina que procura o símbolo X:
· Funções de transição:
δ(q0, B) → (q0, B, R) → continua procurando
δ(q0, X) → (qf, H) → encontrou o X e para
👣 Exemplo 1:
· Fita de entrada: BBXBBB
· A máquina encontra o X ⇒ para no estado final ⇒ aceita.
👣 Exemplo 2:
· Fita de entrada: BBBBBB
· A máquina nunca encontra o X, continua rodando para sempre ⇒ loop infinito ⇒ não decide.
📌 6. Resumo Visual da Diferença
	Situação
	Linguagem Recursiva
	Linguagem RE (enumerável)
	Cadeia está na linguagem (w ∈ L)
	MT para e aceita ✅
	MT para e aceita ✅
	Cadeia não está na linguagem (w ∉ L)
	MT para e rejeita ❌
	MT pode rejeitar ou entrar em loop 🔁
	MT sempre para?
	✅ Sim 
	❌ Não (pode nunca parar)
🔁 7. Toda linguagem recursiva é RE?
· ✅ Sim. Toda linguagem recursiva também é recursivamente enumerável.
· Mas nem toda linguagem RE é recursiva, pois pode não parar para algumas entradas. 
🧠 8. Resumo final
· Uma linguagem recursiva é aquela em que a MT sempre responde: sim ou não, e sempre para.
· Uma linguagem recursivamente enumerável é aquela em que a MT:
· Diz sim se a cadeia pertence.
· Não garante resposta se a cadeia não pertence.
Modificando a hierarquia de Chomsky
📚 1. O que é Gramática Irrestrita?
· É o tipo mais geral de gramática na hierarquia de Chomsky (tipo 0).
· Irrestrita significa que não há regras fixas para as produções.
· As regras têm a forma:
🔹 LE → LD, onde:
· LE (lado esquerdo) pode ter qualquer combinação de símbolos, exceto a cadeia vazia.
· LD (lado direito) pode ter qualquer sequência de símbolos.
✅ Exemplo: Se temos os símbolos:
· Terminais: a, b
· Não terminais: A, B
Uma regra como:
· aAB → BbaA é permitida numa gramática irrestrita.
🧠 2. Relação com a Máquina de Turing (MT)
· Toda gramática irrestrita pode ser reconhecida por uma MT.
· Ou seja:
· A gramática irrestrita é reconhecida pela máquina de Turing.
· A linguagem aceita por uma máquina de Turing é chamada de linguagens recursivamente enumeráveis
· Qualquer conjunto gerado por gramáticas irrestritas são recursivamente enumeráveis.
🏗️ 3. Hierarquia de Chomsky Modificada 
A hierarquia de Chomsky original possui:
· Tipo 0: Gramática irrestrita
· Tipo 1: Sensível ao contexto
· Tipo 2: Livre de contexto
· Tipo 3: Regular
🚧 Modificação: O Tipo 0 (gramática irrestrita) é dividido em dois grupos:
1. Linguagens Recursivamente Enumeráveis (MT pode aceitar, mas nunca parar)
2. Linguagens Recursivas (MT sempre para, aceitando ou rejeitando)
🧾 Resumo em tópicos:
· ✔️ Gramática irrestrita (Tipo 0):
· Pode ter qualquer forma de produção, exceto a cadeia vazia no lado esquerdo.
· É aceita pela Máquina de Turing.
· Gera linguagens recursivamente enumeráveis.
· 🔁 Linguagens recursivamente enumeráveis:
· MT pode aceitar (parar em estado final) ou ficar em loop.
· São mais gerais.
· ✅ Linguagens recursivas:
· MT sempre para, aceitando ou rejeitando.
· São um subconjunto das recursivamente enumeráveis.
· 🧱 Modificação da Hierarquia:
· O nível Tipo 0 agora é dividido entre:
· Linguagens recursivamente enumeráveis
· Linguagens recursivas (mais restritas)
Indecidibilidade
🧠 O que é indecidibilidade?
· Um problema decidível é aquele que possui um algoritmo (ou seja, pode ser resolvido por uma máquina de Turing que sempre para).
· Um problema indecidível é aquele para o qual não existe nenhum algoritmo que resolva todos os casos corretamente.
· Em computação, indecidível = não pode ser resolvido por nenhum programa, nunca, jamais.
⚙️ O Problema da Parada (Halting Problem)
Pergunta central do Problema da Parada: Dada a descrição de uma máquina de Turing “M” e uma cadeia de entrada w, será que “M” vai parar (finalizar a execução) quando iniciada na configuração inicial (q0, w), ou vai entrar em loop infinito?
🛑 Por que esse problema é indecidível?
· Porque não existe uma única máquina (nem um programa) que consiga garantir a resposta certa para todas as combinações de “M” e w.
· Não podemos apenas "esperar para ver" se ela para — ela pode rodar por muito tempo ou ficar em loop infinito.
· Exemplo: Imagine que você escreveu um programa (M) e quer saber se ele sempre para com uma certa entrada (w).
· Esse problema não tem solução geral.
· Ou seja: ninguém pode criar um programa que resolva isso para qualquer código.
✅ Tipos de Problemas Computacionais
	Tipo de problema
	Definição simples
	Resultado da Máquina de Turing
	Decidível (resolvível)
	Existe um algoritmo que sempre responde corretamente
	A MT aceita ou rejeita e sempre para
	Reconhecível (semi-decidível)
	Existe uma MT que aceita as entradas certas, mas pode nunca parar nas erradas
	MT aceita, ou rejeita ou entra em loop
	Indecidível
	Não existe nenhum algoritmo que resolva o problema em todos os casos
	MT não pode tomar uma decisão certa para todas as entradas
🔁 Relação com a tese de Church-Turing
· A tese deChurch-Turing diz que tudo que pode ser resolvido por um algoritmo pode ser resolvido por uma máquina de Turing.
· Portanto, se não existe MT que resolva um problema, então esse problema é indecidível.
❌ Exemplos de problemas indecidíveis:
1. Comparar gramáticas: Dadas duas gramáticas G1 e G2, decidir se elas geram a mesma linguagem:
· ❌ Não existe algoritmo geral para isso.
2. Aceitação geral: Existe uma MT que aceita todas as cadeias de comprimento par?
· ❌ Também é indecidível.
3. Interseção vazia: Verificar se a linguagem gerada por uma gramática irrestrita G1 e uma gramática regular G2 tem interseção vazia:
· ❌ Outro problema indecidível.
📌 Resumo 
· Indecidibilidade significa que nem com computador conseguimos resolver o problema para todos os casos.
· O problema da parada é o exemplo mais famoso: não é possível saber se qualquer programa vai parar ou travar para sempre.
· Existem problemas resolvíveis, reconhecíveis e indecidíveis, cada um com limitações diferentes.
· Esse conceito é essencial na teoria da computação, pois mostra os limites do que computadores podem fazer.
Questão 1. Analise os tipos de problemas encontrados nas seguintes declarações:
I. Existe uma MT M tal que M aceita e para em cada cadeia em L e rejeita e para em cada cadeia que não pertence a L.
II. O problema da parada.
III. O conjunto dos naturais pares.
Agora assinale a alternativa correta:
A. indecidível, decidível, recursivo.
B. decidível, indecidível, recursivo.
C. decidível, decidível, recursivo.
D. indecidível, recursivo, decidível.
E. recursivo, indecidível, recursivo.
Questão 2. Considere as seguintes afirmativas:
I. Uma linguagem é recursivamente enumerável se uma MT para e aceita.
II. Uma linguagem é recursivamente enumerável se uma MT para e rejeita.
III. Uma linguagem é recursivamente enumerável se uma MT entra em loop infinito.
IV. Uma linguagem é recursivamente enumerável se uma MT não entra em loop finito.
 Assinale a alternativa correta:
A. Apenas a afirmativa I e IV estão corretas.
B. Apenas a afirmativa II está correta.
C. Apenas as afirmativas I e III estão corretas.
D. Apenas as afirmativas II e IV estão corretas.
E. As afirmativas I, II e III estão corretas.
Módulo 3. Redutibilidade
Redução
🧩 O que é Redução?
· Redução é o processo de transformar um problema A em outro problema B, de forma que resolver B ajude a resolver A.
· É uma ferramenta muito usada para mostrar se um problema é decidível ou indecidível.
· Não resolve diretamente o problema, mas aproveita a solução de outro problema já conhecido.
🎯 Intuição com exemplos do dia a dia
· Exemplo 1 – Viagem a uma nova cidade:
· Problema A: Encontrar qual ônibus pegar.
· Problema B: Ler um guia de transporte da cidade.
· Você reduz o problema A (achar o ônibus) ao problema B (usar o guia). Se você tem o guia (resolução de B), consegue resolver A.
· Exemplo 2 – Medir a área de um retângulo:
· Problema A: Medir área.
· Problema B: Medir largura e altura.
· Você resolve A usando a solução de B, pois área = largura × altura.
⚙️ Aplicação em Computação
· Suponha dois problemas: A e B
· Se A pode ser transformado (reduzido) em B, dizemos que A é redutível a B.
· Se B já é resolvido, então A também pode ser resolvido com base nele.
📌 Propriedades importantes da Redução:
1. Resolver A não pode ser mais difícil que resolver B.
2. Se A se reduz a B e B é decidível, então A também é decidível.
3. Se A é indecidível e A se reduz a B, então B também é indecidível.
👉 Usamos isso para provar que um novo problema é indecidível.
🚨 Redução e indecidibilidade
· A redução é o principal método usado para provar que um problema é indecidível.
· A ideia é pegar um problema conhecido como indecidível (ex: Problema da parada) e mostrar que ele pode ser transformado em outro problema.
 Exemplo: Detecção de vírus em computador
· Problema: Detectar se um programa contém vírus.
· Redução: Esse problema pode ser reduzido ao Problema da Parada (sabidamente indecidível).
· Conclusão: Como o problema da parada é indecidível, então o problema da detecção de vírus também é.
· 🧠 Resultado curioso:
· Não existe um antivírus perfeito que detecte todos os vírus possíveis.
· O que os antivírus fazem: comparam com uma lista de vírus conhecidos.
· Por isso precisam de atualizações frequentes — novos vírus não são reconhecidos automaticamente.
✅ Resumo 
· A redução transforma um problema em outro para usar a solução existente.
· É muito útil para provar se um problema é decidível ou indecidível.
· Principal ferramenta teórica em teoria da computação para estudar o que os computadores conseguem resolver.
· Não diz como resolver o problema, mas sim se ele pode ser resolvido com base em outro.
Aplicações das reduções
🔄 O que é Redução?
· Redução é transformar um problema A em outro problema B, de forma que resolver B ajuda a resolver A.
· Isso é muito usado para:
· Mostrar que um problema é indecidível
· Comparar a dificuldade de dois problemas
· Classificar problemas em decidíveis ou indecidíveis
🧠 Redução em tempo polinomial
· Uma redução em tempo polinomial acontece quando conseguimos transformar o problema A no problema B rapidamente, ou seja, em tempo "razoável".
· É feita por uma Máquina de Turing determinística (uma máquina com apenas um caminho possível de execução).
· Se A é reduzido a B em tempo polinomial, então:
· Se B é fácil e decidível, A também é decidível.
· Se A é indecidível (difícil), B também é indecidível.
✏️ Exemplo prático (intuitivo): Para saber a área de um retângulo (problema A), basta medir base e altura (problema B). → Logo, resolver A é tão fácil quanto resolver B. 
📘 Redução muitos-para-um
· Também chamada de redução de Post.
· Transformamos várias instâncias de um problema (ex: várias perguntas diferentes sobre o problema A) em uma única instância do problema B.
· Muito usada para provar problemas NP-completos e indecidíveis.
📉 Problema da Correspondência de Post (PCP)
📌 O que é:
· Proposto por Emil Post em 1946.
· É um problema indecidível, ou seja, não existe algoritmo que resolva todos os casos.
· Muito útil para provar que outros problemas também são indecidíveis (via redução).
🃏 Como funciona o PCP? Para entender a ideia do PCP, vamos jogar um jogo. Sejam N cartões em que cada um deles é dividido em duas partes. Cada cartão contém uma sequência superior e uma sequência inferior.
· Temos N cartões.
Cada cartão tem:
· Uma sequência na parte de cima
· Uma sequência na parte de baixo
· 🎯 Objetivo do jogo: Organizar as cartas de tal maneira que as cadeias na parte superior e inferior fiquem iguais.
Exemplo 1 (com solução): Seja N = 5 e as cartas sejam as seguintes.
Cartões: 
Cartão 1: 0 | 10 
Cartão 2: 011 | 00 
Cartão 3: 0 | 11 
Cartão 4: 011 | 0 
Cartão 5: 1 | 11 
Solução: sequência: 4, 3, 2, 5, 1 
➡ Parte de cima: 011 + 0 + 011 + 1 + 0 = 011001110
➡ Parte de baixo: 0 + 11 + 00 + 11 + 10 = 011001110
✅ As duas sequências são iguais → problema tem solução.
Exemplo: Resumo das regras do jogo:
· Cartas disponíveis:
· Existem 4 tipos diferentes de cartas (imagem ao lado).
· Cada tipo tem 5 cópias → total de 20 cartas.
· Jogadores:
· Participam 4 jogadores.
· Cada jogador recebe 5 cartas aleatórias no início.
· Dinâmica do jogo:
· O jogo começa com a troca de uma única carta.
· Cada jogador:
· Recebe uma carta do jogador à esquerda.
· Entrega uma carta ao jogador à direita.
· Objetivo para vencer:
· Mostrar 5 cartas organizadas em uma sequência específica.
· A sequência deve ter: Cadeias idênticas na parte superior e inferior das cartas.
Solução: sequência 2, 1, 4, 3, 2
✅ Dá certo.
⚠️ Mas nem sempre há solução
· Em muitos casos, não conseguimos formar duas sequências iguais.
· E não dá para saber de antemão se vamos conseguir ou não.
· Por isso, o Problema da Correspondência de Post é indecidível.
💡 Importância do PCP
· Usado como base para provar que outros problemas também são indecidíveis.
· Se você conseguir reduzir o PCP a outro problema, então esse outro problema também é indecidível.
· Ajuda a classificar problemasdecidíveis e indecidíveis.
✅ Resumo
· Reduções transformam um problema difícil em outro.
· A redução em tempo polinomial é usada em complexidade computacional.
· O PCP é um problema indecidível, muito usado como ferramenta para provar a indecidibilidade de outros problemas.
· Reduções ajudam a entender a dificuldade dos problemas computacionais e se eles têm solução geral ou não.
Questão 1. O que é verdadeiro para redutibilidade?
A. Converter um problema em outro problema.
B. Converter um problema não resolvido em outro problema não resolvido.
C. Converter um problema resolvido em outro problema não resolvido.
D. Converter um problema não resolvido em outro problema resolvido para resolver o primeiro problema.
E. Converter um problema não resolvido em outro problema.
Questão 2. Analise as seguintes afirmativas relacionadas com a redutibilidade:
I. Se A é redutível a B e B é um problema decidível, então A é um problema indecidível.
II. A redutibilidade trata da solubilidade de A na presença de um método para resolver B.
III. Quando A é reduzido a B, resolver A não pode ser mais difícil do que resolver B.
Assinale a alternativa correta:
A. Apenas as afirmativas II e III estão corretas.
B. Apenas a afirmativa II está correta.
C. Apenas as afirmativas I e III estão corretas.
D. Apenas as afirmativas I e II estão corretas.
E. Apenas a afirmativa I está correta.
Módulo 4. Complexidade computacional
Tipos de complexidade computacional
🧠 O que é Complexidade Computacional?
· É o estudo do custo de execução de um algoritmo, ou seja:
· Quanto tempo ele leva para rodar?
· Quanta memória ele usa?
🔁 Tipos de Complexidade
1. Complexidade de Tempo
· Mede o número de passos (instruções) que um algoritmo precisa para resolver um problema.
· Depende do tamanho da entrada: quanto maior a entrada, mais passos podem ser necessários.
✏️ Exemplo: Se um algoritmo percorre uma lista de n elementos uma vez, ele tem complexidade de tempo T(n) = n.
2. Complexidade de Espaço
· Mede quanta memória o algoritmo precisa para funcionar.
· Também depende do tamanho da entrada.
· Representa quantos objetos (ou posições de fita da MT) precisam ser armazenados durante a execução.
✏️ Exemplo: Se o algoritmo só usa duas variáveis (independente do tamanho da entrada), sua complexidade de espaço é constante, ou seja, S(n) = O(1).
🧮 Complexidade no Pior Caso
· Normalmente usamos a complexidade do pior caso, ou seja, o cenário mais demorado possível para o algoritmo.
· Isso nos ajuda a garantir que o algoritmo será eficiente mesmo nos casos mais difíceis.
⏱️ Notação Big O (O-grande)
📌 Serve para:
· Descrever como o tempo (ou espaço) cresce conforme o tamanho da entrada aumenta.
· Ignora constantes e termos de menor importância para focar no crescimento principal.
✏️ Exemplos de Funções e Crescimento: 
	Função
	n = 0
	n = 2
	n = 10
	n = 20
	f₁(n) = 2n
	0
	4
	20
	40
	f₂(n) = n²
	0
	4
	100
	400
	f₃(n) = 2n²
	0
	8
	200
	800
	f₄(n) = 2ⁿ + 3
	4
	7
	1027
	1.048.579
🔍 Observações:
· f₂(n) e f₃(n) crescem de forma parecida (ambas são polinômios).
· f₄(n) (exponencial) cresce muito mais rápido do que as outras para valores maiores de n.
🧠 Definição formal de O(g(n)):
Dizemos que f(n) é da ordem de g(n) → f(n) = O(g(n))
Se existe uma constante C e um valor k tal que: f(n) ≤ C * g(n) para todo n ≥ k
💬 Em palavras simples: Dizemos que f(n) = O(g(n)) quando a função f(n) cresce no máximo tão rápido quanto g(n), ignorando detalhes pequenos, como multiplicar por uma constante ou começar a valer só a partir de um certo ponto.
✅ Exemplo fácil: Imagine que o tempo que um algoritmo leva seja: f(n) = 3n + 2
Agora queremos comparar com g(n) = n.
Será que f(n) é da ordem de n?
Sim! Porque a partir de certo ponto (ex: n ≥ 1), sempre teremos:
f(n) = 3n + 2 → desprezando constantes
Então: ✅ f(n) = O(n)
📌 Moral da história: Se f(n) for menor ou igual a uma constante vezes g(n) para valores grandes de n, então dizemos que f(n) é da ordem de g(n).
📏 Regras com Notação O
· Sejam duas funções de n, a saber, F1 (n) e F2 (n), de ordem O(f(n)) e O(g(n)), respectivamente, então:
Sabemos que:
· F₁(n) = O(f(n))
· F₂(n) = O(g(n))
Então:
1. Soma: F₁(n) + F₂(n) = máx(O(f(n)), O(g(n))) → escolhe a maior complexidade
2. Multiplicação: F₁(n) * F₂(n) = O(f(n) * g(n)) → multiplica as complexidades
3. Multiplicação por constante: C * F₁(n) = O(f(n)) (C não muda a ordem) → despreza constantes
Exemplo: Um algoritmo A é executado em t=5s para uma entrada de tamanho n=25. Se o algoritmo e quadrático, ou seja O(n2), quanto tempo em segundos ele gastará aproximadamente no mesmo computador, se a entrada tiver tamanho n=50?
Sabe-se que:
· O algoritmo A é quadrático, ou seja, sua complexidade é O(n²).
· Quando a entrada é n = 25, ele leva t = 5 segundos.
· Queremos saber quanto tempo ele levará para n = 50.
Passo 1. Entender o crescimento: Se o algoritmo é O(n²), isso quer dizer que o tempo de execução cresce com o quadrado do tamanho da entrada.
Passo 2. Compare os tamanhos das entradas:
50/25=2 
Ou seja, a nova entrada é 2 vezes maior.
Passo 3. Aumente o tempo proporcional ao quadrado do fator de crescimento:
Como a complexidade é O(n2), o tempo aumentará por:
22=4 vezes 
Passo 4. Multiplique o tempo original:
5×4=20 segundos 
✅ Resposta final: Se a entrada dobrar de tamanho (de 25 para 50), o tempo será aproximadamente 20 segundos, pois um algoritmo quadrático cresce com o quadrado do tamanho da entrada.
	🧠Etapas para resolver problemas semelhantes:
Passo 1. Identifique a complexidade do algoritmo
Geralmente será dada no formato:
· O(1) → constante
· O(log n) → logarítmica
· O(n) → linear
· O(n²) → quadrática
· O(n³) → cúbica
· O(2ⁿ) → exponencial
(etc.)
Passo 2. Veja o tempo gasto com a entrada inicial e qual a entrada final
Exemplo:
· Tamanho da entrada inicial: n1
· Tempo gasto: t1
· Novo tamanho da entrada: n2​
· 
Passo 3. Calcule o fator de crescimento do tamanho da entrada
Onde:
· n2​ é o novo tamanho da entrada.
Passo 4. Aplique a complexidade ao fator
Use a complexidade para calcular de quanto será o aumento no tempo.
	Complexidade
	Fator de aumento no tempo
	O(1)
	Tempo não muda
	O(log n)
	Tempo cresce como log(n)
	O(n)
	Multiplica pelo fator
	O(n²)
	Multiplica pelo fator²
	O(n³)
	Multiplica pelo fator³
	O(2ⁿ)
	Tempo dobra para cada +1 em n
✅ 5. Multiplique o tempo original pelo fator obtido
🧪 Exemplos práticos
🔹 Exemplo 1: O(n²)
· Tempo original: 5s para n = 25
· Novo tamanho: n = 50
· Fator: 50/25=2
· Como é O(n²): tempo multiplica por 22=4
· Novo tempo: 5×4=20s 
🔹 Exemplo 2: O(n³)
· Tempo original: 2s para n = 10
· Novo n: 20 → fator = 2
· Tempo multiplica por 23=8
· Novo tempo: 2×8=16s
🔹 Exemplo 3: O(log n)
· Tempo original: 3s para n = 8
· Novo n: 64 
· log2(8) = 3, log2(64) = 6 → fator de aumento: 6/3=2
· Novo tempo: 3×2=6s
✅ Conclusão
· A complexidade computacional ajuda a escolher algoritmos eficientes.
· Os dois tipos principais são:
· Tempo: passos que o algoritmo executa.
· Espaço: memória que o algoritmo usa.
· A notação O permite comparar a eficiência dos algoritmos, especialmente em grandes entradas.
· Exponenciais são muito menos eficientes que polinômios conforme n cresce.
Tipos de complexidade de tempo
✅ O que é complexidade de tempo?
· Complexidade de tempo mede quanto tempo um algoritmo leva para rodar dependendo do tamanho da entrada (n).
· Serve para comparar algoritmos e escolher os mais eficientes.
· É usada principalmente na análise de algoritmos e na teoria da complexidade computacional.
📚 Tipos de complexidade de tempo:
🟩 1. Complexidade de tempo constante – O(1)
· Definição: O tempo de execução não depende do tamanho da entrada.
· Mesmo que n cresça, o tempo continua igual.
📌 Exemplo: Se f(n) = 10, então:
· Não importa o valor de n, a função sempre retorna 10.
· Isso é O(1), pois é constante.
🟦 2. Complexidade de tempo logarítmica – O(log n)
· Definição: O tempo cresce muito lentamente, mesmo com grandes entradas.
· Normalmente aparece em algoritmos que cortam o problema pela metade.
📌 Exemplo: Buscabinária (em listas ordenadas)
· A cada passo, elimina metade da lista.
· Assim, com n = 16 elementos, ela faz no máximo log₂16 = 4 comparações.
· Por isso, complexidade = O(log n).
🟨 3. Complexidade de tempo linear – O(n)
· Definição: O tempo cresce proporcionalmente ao tamanho da entrada.
· Se a entrada dobra, o tempo também dobra.
📌 Exemplo: Se f(n) = 3n – 2:
· Podemos estimar f(n) ≤ 4n para n ≥ 0.
· Assim, dizemos que a função tem ordem O(n).
🟧 4. Complexidade de tempo polinomial – O(nᵏ)
· Definição: O tempo cresce como um polinômio, tipo n², n³, etc.
· É razoavelmente eficiente dependendo do grau do polinômio.
📌 Exemplo: Se f(n) = 6n³ + 5n + 1:
· Para n ≥ 1, temos:
· f(n) ≤ 6n³ + 5n³ + 1n³ = 12n³ → considera maior grau que neste caso é n3
· Então: f(n) = O(n³)
🟥 5. Complexidade de tempo exponencial – O(2ⁿ)
· Definição: O tempo explode rapidamente à medida que n aumenta.
· Muito ineficiente para entradas grandes.
· Problemas desse tipo são considerados difíceis ou quase impossíveis de resolver em tempo viável.
📌 Exemplo de comportamento:
· Para n = 10 → 2¹⁰ = 1.024 passos.
· Para n = 20 → 2²⁰ = 1.048.576 passos.
(O tempo dobra a cada aumento de 1 em n!)
📌 Conclusão
· Avaliar a complexidade de tempo ajuda a entender se um algoritmo é prático ou não.
· O(1) → super rápido
· O(log n) → muito eficiente
· O(n) → aceitável
· O(n²), O(n³) → pode ser lento
· O(2ⁿ) → evite para entradas grandes
As classes P
✅ 1. O que é a Classe P?
· P = "Problemas polinomiais"
· Inclui todos os problemas que podem ser resolvidos por um algoritmo determinístico (normal, como os que usamos nos computadores) em tempo polinomial, como O(n²), O(n³), etc.
· Exemplos: ordenação, busca binária, multiplicação de matrizes.
📌 Definições:
· A classe P contém todos os problemas de decisão que podem ser resolvidos por uma Máquina de Turing determinística em tempo polinomial.
✅ 2. O que é a Classe NP?
· NP = "Nondeterministic Polynomial time" (tempo polinomial não determinístico)
· São problemas que:
· Não sabemos resolver rapidamente, mas...
· Se alguém der uma solução, conseguimos verificar se está correta em tempo polinomial.
📌 Definição formal:
· Um problema NP se pode ser resolvido por uma Máquina de Turing não determinística em tempo polinomial.
🔄 Diferença entre P e NP
	Classe
	Resolução rápida?
	Verificação rápida?
	Tipo de Máquina
	P
	✅ Sim
	✅ Sim
	Determinística
	NP
	❌ (em geral, não)
	✅ Sim (polinomial)
	Não determinística
📌 Exemplo: Problema do Caixeiro Viajante (TSP)
Descrição:
· Um vendedor precisa visitar todas as cidades uma única vez e voltar para a cidade de origem com o menor custo/distância total possível.
Na imagem fornecida:
· Há 4 cidades (nós) e os custos entre elas (como um grafo e uma matriz de distâncias).
📍Exemplo de caminho: 
· Tente caminho: 1 → 2 → 4 → 3 → 1
· Some as distâncias:
· 1 → 2: 20
· 2 → 4: 30
· 4 → 3: 12
· 3 → 1: 30
· Total: 20 + 30 + 12 + 30 = 92
Você pode testar todos os caminhos possíveis. O número de caminhos cresce rapidamente com o número de cidades — esse crescimento é exponencial, por isso o problema está em NP.
📌 Complexidade do Problema do Caixeiro Viajante: O(n · 2ⁿ) — Muito difícil de resolver conforme n cresce.
🧩 4. O que é NP-completo (NPC)?
· Um problema é NP-completo se:
1. Está na classe NP.
2. Todo outro problema NP pode ser reduzido a ele em tempo polinomial.
📌 Em resumo:
· É o mais difícil dos problemas NP.
· Se resolver qualquer problema NP-completo de forma eficiente, todos os NP também poderiam ser resolvidos eficientemente.
✅ Resumo final
· Classe P: Problemas que conseguimos resolver e verificar rapidamente.
· Classe NP: Problemas que não sabemos resolver rapidamente, mas conseguimos verificar a resposta.
· Problemas NP-completos: Os "chefões" da classe NP. Resolver um deles eficientemente resolve todos.
Questão 1. Para os problemas X e Y, Y é NP completo e X se reduz a Y em tempo polinomial. Qual das seguintes alternativas é verdadeira?
A. Se X pode ser resolvido em tempo polinomial, então Y também pode.
B. X é NP completo.
C. X é NP difícil.
D. X é NP fácil.
E. X está em NP, mas não necessariamente em NP completo.
Se X se reduz a Y que é NP completo, então X também deve ser NP completo.
Questão 2. Considerando que a complexidade de tempo da computação prática reside dentro de limites de tempo polinomial, sendo essas classes de problemas escritas como problemas da classe P, avalie as seguintes afirmativas considerando o que é verdadeiro para o problema da classe P:
I. O número de passos (ou tempo) necessários para completar o algoritmo é uma função polinomial de n.
II. É computável por uma máquina de Turing determinística em tempo não polinomial.
III. Ele contém todos os conjuntos nos quais a pertinência pode ser decidida por um algoritmo cujo tempo de execução é limitado por um polinômio.
A. Assinale a alternativa correta:
B. Apenas a afirmativa I está correta.
C. Apenas a afirmativa II está correta.
D. Apenas as afirmativas I e III estão corretas.
E. Apenas as afirmativas II e III estão corretas.
F. As afirmativas I e III estão corretas.
No contexto de problemas da Classe P, é computável por uma máquina de Turing determinística em tempo polinomial. Logo, apenas a II não está correta.
Recebe uma entrada
Verifica se há uma transição possível
Vai para o próximo estado
Repete o processo até a entrada acabar
Aceita ou rejeita a cadeia de entrada
Estado atual
image3.png
image4.png
image5.png
image6.png
image7.png
image8.png
image9.jpeg
image10.png
image11.png
image12.png
image13.png
image14.png
image15.png
image16.png
image17.png
image18.png
image19.png
image20.png
image21.png
image22.png
image23.png
image24.png
image25.png
image26.png
image27.png
image28.png
image29.png
image30.png
image31.png
image32.jpeg
image33.png
image34.png
image35.png
image36.png
image37.png
image38.png
image39.png
image40.png
image41.png
image42.png
image43.png
image44.jpeg
image45.jpeg
image46.png
image47.png
image48.png
image49.png
image50.png
image51.png
image52.png
image53.png
image54.jpeg
image55.jpeg
image56.jpeg
image57.jpeg
image58.jpeg
image59.jpeg
image60.jpeg
image61.png
image62.png
image63.png
image64.png
image65.png
image66.png
image1.png
image67.png
image68.png
image69.png
image70.png
image71.png
image72.png
image73.png
image74.png
image75.png
image76.png
image2.png
image77.png
image78.png
image79.png
image80.png
image81.png
image82.png
image83.pngC tem 5 elementos, e (A ∪ B) tem no máximo 7, a interseção pode ter no máximo 5 elementos.
Portanto, dizer que o máximo é 3 não é garantido.
❌ Alternativa errada.
D) (A ∩ B) ∩ C tem, no máximo, 3 elementos.
Vamos por partes:
· A ∩ B → Interseção de A (3 elementos) com B (4 elementos) → pode ter no máximo 3 elementos.
· Agora, interseção com C (que tem 5 elementos).
👉 Então:
· (A ∩ B) tem no máximo 3 elementos.
· E agora interseção com C → pode ter no máximo 3 elementos (se todos estiverem também em C).
✅ Sim! O máximo possível é 3. Não há contradição aqui.
✔️ Alternativa correta!
E) A ∩ C tem 3 elementos, pelo menos.
· A tem 3 elementos.
· C tem 5 elementos.
Mas não sabemos quais são os elementos de A e C.
👉 Pode ser que nenhum elemento de A esteja em C, então A ∩ C poderia ter zero elementos.
❌ Alternativa errada.
	🧠 Como Resolver Questões Semelhantes?
Aqui vai um guia prático para resolver questões parecidas:
1. Leia com atenção os tamanhos dos conjuntos.
· Anote quantos elementos cada conjunto tem.
2. Entenda a operação pedida.
· União → soma os diferentes elementos.
· Interseção → pega apenas os elementos em comum.
3. Use sempre os extremos.
· Para união, o máximo é a soma dos elementos (se forem todos diferentes).
· Para interseção, o máximo é o número de elementos do menor conjunto.
· O mínimo da interseção é zero (se não houver elementos em comum).
4. Cuidado com frases como "no máximo" ou "pelo menos"
· "No máximo X": quer dizer que pode ser até X, mas também menos.
· "Pelo menos X": quer dizer que o mínimo é X, pode ser mais, mas não pode ser menos — cuidado com isso, geralmente está errado quando não há garantias sobre os elementos.
Módulo 2. Símbolos e Cadeias
Símbolos
· Definição geral de simbolo: Um símbolo é uma representação gráfica única e indivisível.
Pode conter um ou mais caracteres, como letras, números ou palavras.
· Também chamados de:
· Tokens (em inglês)
· Átomos (pois são unidades básicas e indivisíveis)
· Importante: Não há uma definição formal. O símbolo é um conceito primitivo, como o "ponto" na geometria — sabemos o que é, mas não se define formalmente.
Exemplos de símbolos:
· a
· abc
· begin
· if
· 5
· 1048
· 2018
✅ Mesmo que contenham vários caracteres (como begin), são tratados como um único símbolo.
Cadeias
· Definição de cadeia: Uma cadeia é uma sequência (ou justaposição) de símbolos vindos de um alfabeto.
· Comprimento de uma cadeia: É o número de símbolos que a cadeia contém.
Notação: |α| significa "o comprimento da cadeia α".
· Cadeia elementar ou unitária: É formada por um único símbolo.
Exemplo:
· Se α = a, então |α| = 1
· Exemplos explicados:
· α = a → 1 símbolo → |α| = 1
· β = abc → 3 símbolos (a, b, c) → |β| = 3
· χ = begin → 5 símbolos (b, e, g, i, n) → |χ| = 5
· φ = 1048 → 4 símbolos (1, 0, 4, 8) → |φ| = 4
· Cadeia vazia:
· Representada por ɛ (épsilon)
· Não contém nenhum símbolo
· Comprimento: |ɛ| = 0
· 🔎 Exemplo do mundo real: é como o valor null em linguagens de programação.
Alfabeto
· Definição de alfabeto: Um alfabeto é um conjunto finito e não vazio de símbolos, a partir do qual formamos cadeias.
· Exemplo 1 – Alfabeto hexadecimal: ∑ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f}
· Com esse alfabeto, podemos formar cadeias como:
· 1234b
· a0b5c
· f5dc
· Exemplo 2 – Alfabeto binário:∑ = {0, 1}
· Com ele, formamos cadeias como:
· 0
· 101
· 11001
✅ Resumo Final
· Símbolos são as menores unidades de uma linguagem (como a, if, 1048).
· Cadeias são sequências desses símbolos (como abc ou f5dc).
· Cadeia vazia (ɛ) representa uma sequência com zero símbolos.
· Alfabeto é o conjunto de símbolos permitidos para formar as cadeias.
Estrutura das cadeias
· Cadeia: É uma sequência de símbolos de um alfabeto. Pode ser composta por símbolos individuais ou outras cadeias.
· Concatenação: É a operação de juntar duas cadeias.
· Notação: α · β ou simplesmente αβ
· Significa colocar os símbolos de β no final de α
· Exemplos com alfabeto ∑ = {a, b, c, d}:
· α = abc (comprimento 3)
· β = baca (comprimento 5)
· σ = a (comprimento 1)
· Passo a passo:
· α · β = abc + baca = abcbaca → |αβ| = 3 + 5 = 8
· β · α = baca + abc = bacaabc → |βα| = 5 + 3 = 8
· α · σ = abc + a = abca → |ασ| = 3 + 1 = 4
· σ · β = a + baca = abaca → |σβ| = 1 + 5 = 6
🔸 Importante:
· A concatenação é associativa, ou seja: (αβ)γ = α(βγ)
· Mas não é comutativa: αβ ≠ βα, exceto se α = β ou uma das duas for a cadeia vazia.
🔹 Cadeia vazia (ɛ)
· Representada por ɛ
· Não contém símbolos
· Comprimento: |ɛ| = 0
· Propriedade:
· αɛ = ɛα = α
· A cadeia vazia é o elemento neutro da concatenação
🔹 Prefixo e Sufixo
· Prefixo: Uma cadeia α é prefixo de β se β = αγ (γ pode ser a cadeia vazia)
· Exemplo:
Se β = 123xyz, então α = 123 é prefixo de β
· Prefixos próprios (diferentes da cadeia completa):
· Se w = 0111, prefixos próprios:
ɛ, 0, 01, 011
· Sufixo: Uma cadeia α é sufixo de β se β = γα
· Exemplo:
Se β = 123xyz, então α = xyz é sufixo de β
· Sufixos próprios (diferentes da cadeia completa):
· Se w = 0110, sufixos próprios:
ɛ, 0, 10, 110
🔸 A cadeia vazia ɛ é prefixo e sufixo de qualquer cadeia
🔹 Subcadeia
· Dadas quatro cadeias α, β, γ e δ, uma cadeia α é uma subcadeia de β se:
β = γ α δ (α aparece no meio, começo ou fim da β)
· Observações:
· Prefixos e sufixos são casos especiais de subcadeias.
· Se γ ou δ forem vazios, continua sendo válido.
🔹 5. Reverso de uma cadeia
· O reverso de uma cadeia β, denotado por βᴿ, é a mesma cadeia com símbolos invertidos.
· Exemplos:
· Se α = 012cba, então αᴿ = abc210
· Se β = d, então βᴿ = d
· ɛᴿ = ɛ (o reverso da cadeia vazia é ela mesma)
🔹 6. Cadeias repetidas (σᵢ)
· Representa a concatenação do símbolo σ consigo mesmo i vezes
· Exemplo com símbolo a:
· a⁰ = ɛ (zero vezes → cadeia vazia)
· a¹ = a
· a² = aa
· a³ = aaa
✅ Resumo Final
· Concatenação: junta duas cadeias, mantendo a ordem
· Prefixo/Sufixo: aparecem no início/fim da cadeia
· Subcadeia: aparece em qualquer posição da cadeia
· Cadeia vazia (ɛ): neutra na concatenação, sempre prefixo/sufixo
· Reverso: inverte os símbolos da cadeia
· Repetição σᵢ: símbolo σ repetido i vezes
Fechamento de Kleene
🔹 Definição de Fechamento de Kleene (Σ*): É o conjunto de todas as cadeias possíveis, formadas por símbolos de um alfabeto Σ, incluindo a cadeia vazia (denotada por λ ou ɛ).
· Símbolo usado: * (asterisco)
· Exemplos:
· Se Σ = {0}, então: Σ* = {λ, 0, 00, 000, 0000, …}
· Se Σ = {0, 1}, então: Σ* = {λ, 0, 1, 00, 01, 10, 11, 100, …}
🔹 Fechamento Positivo (Σ⁺)
· Definição: Igual ao Fechamento de Kleene, mas sem a cadeia vazia.
· Símbolo usado: + (sinal de soma)
· Exemplos:
· Se Σ = {0}, então: Σ⁺ = {0, 00, 000, …}
· Se Σ = {0, 1}, então: Σ⁺ = {0, 1, 00, 01, 10, 11, 100, …}
🔹 Exemplos com expressões
✅ Expressão: 10*1
· Interpretação: Cadeias que começam e terminam com “1”, e podem conter qualquer número de zeros entre os “1” (inclusive nenhum).
· Por quê? O * permite incluir a cadeia vazia (λ), então a parte do meio (0*) pode ter zero ou mais "0".
· Exemplos passo a passo:
· 0 zeros: 1 + λ + 1 → 11
· 1 zero: 1 + 0 + 1 → 101
· 2 zeros: 1 + 00 + 1 → 1001
· 3 zeros: 1 + 000 + 1 → 10001
· Conjunto gerado: {11, 101, 1001, 10001, …}
Podemos sintetizar dizendo que esse é o conjunto de todas as cadeias, começando e terminando com “1” e com qualquer número “0” entre os dois 1s. 
✅ Expressão: a⁺b*
· Interpretação: Cadeias que começam com pelo menos um “a” (a⁺) e podem ser seguidas por zero ou mais “b” (b*).
· Por quê? O + exige pelo menos um “a” e o * permite qualquer número de “b”, incluindo zero.
· Exemplos:
· {a, aa, aaa, ...} . {λ, b, bb, bbb, ...} = ab, aab, aaab, abb, aabb, aaabbb,...
· Conjunto gerado: {a, aa, abb, ab, abb, aab, …}
Em síntese, esse é o conjunto de todas as cadeias de “a” e “b” contendo qualquer número de “a” seguido por qualquer número de “b”. 
✅ Expressão: (ab)*
· Interpretação: Cadeias com repetições da sequência “ab”, podendo ser nenhuma repetição (cadeia vazia está incluída).
· Exemplos passo a passo:
· 0 vezes: λ
· 1 vez: ab
· 2 vezes: abab
· 3 vezes: ababab
· Observação: Sempre haveráo mesmo número de “a” e “b”, e sempre com “a” seguido de “b”.
· Conjunto gerado: {λ, ab, abab, ababab, …}
Nessas cadeias geradas, o número de “a” e “b” precisa ser o mesmo, ou seja, sempre haverá cadeias com repetições de “ab”; logo, ocorrerá um igual número de “a” e “b”.
✅ Expressão: (00)*(11)*1
· Interpretação:
· Começa com zero ou mais pares de zeros → (00)*
· Depois zero ou mais pares de uns → (11)*
· Sempre termina com um único “1”
· Análise:
· (00)*: número par de zeros (inclusive 0)
· (11)*: número par de uns (inclusive 0)
· 1: fixa o final com um único “1”
· Exemplos passo a passo:
· Sem zeros e uns: λ + λ + 1 → 1
· 2 zeros: 00 + λ + 1 → 001
· 2 uns: λ + 11 + 1 → 111
· 2 zeros e 2 uns: 00 + 11 + 1 → 00111
· 4 zeros e nenhum “11”: 0000 + λ + 1 → 00001
· Conjunto gerado:
Cadeias com número par de zeros, seguido de número par de uns, terminando com 1.
Exemplos: {1, 001, 111, 00111, 00001, …}
✅ Resumo Final
· Σ*: todas as cadeias possíveis com símbolos de Σ, incluindo a cadeia vazia.
· Σ⁺: como Σ*, mas sem a cadeia vazia.
· Expressões com *: permitem zero ou mais repetições.
· Expressões com +: exigem uma ou mais repetições.
· Concatenação de partes cria padrões que podemos prever e construir passo a passo.
Questão 1. Palíndromos são cadeias que, lidas da esquerda para a direita ou da direita para a esquerda, têm a mesma sequência de símbolos e podem ser definidas pela seguinte expressão: wcwR, em que w é uma cadeia e c, uma constante ou separador. Nesse contexto, assinale a alternativa na qual todas as cadeias são palíndromos com separador.
A. ANA, 1190911, 0010, ABA.
B. 010, 1190911, 00100, ANA.
C. 00, 119911, 00100, AA.
D. 001, 1199911, 0010, AABB.
E. 000, 219912, 00100, CCC.
Questão 2. Os símbolos são utilizados para construir __________, que são formadas pela __________ de símbolos. Um _________ é um conjunto finito e não vazio de símbolos a partir dos quais são formadas as cadeias. Cadeias possuem prefixos e sufixos, que são considerados __________ da cadeia principal.
Marque a opção que permite o correto preenchimento das lacunas:
A. Alfabetos, cadeias, sufixo, subcadeias.
B. Alfabetos, sufixo, subcadeias, cadeias.
C. Cadeias, concatenação, alfabeto, subcadeias.
D. Subcadeias, concatenação, sufixo, alfabeto.
E. Alfabetos, subcadeias, sufixo, prefixo.
Módulo 3. Linguagens, gramáticas e conjuntos
Linguagens
🔹 Três conceitos fundamentais
· Conjuntos: Conjunto finito e não vazio de símbolos, como um alfabeto.
· Linguagens: Conjunto de cadeias formadas pela concatenação de símbolos de um alfabeto.
· Gramáticas: Regras que definem como as cadeias (ou palavras) de uma linguagem podem ser formadas.
🔹 Alfabeto
· Definição: Conjunto de símbolos individuais. Exemplo: {0, 1, λ}
· Onde λ é o símbolo nulo (cadeia vazia).
· Exemplo: Se o alfabeto é binário {0, 1}, ele contém os símbolos 0 e 1.
🔹 Cadeias
· Definição: Sequência finita (ou infinita) de símbolos concatenados do alfabeto.
· Exemplo: Para o alfabeto binário {0, 1}, as cadeias podem ser: 01, 11, 110, 1010, etc.
· Importante: O tamanho das cadeias pode crescer indefinidamente.
· Notação:
· Alfabeto: ∑ é usado para designar um alfabeto
· Cadeias: u, v, w é usado para designar cadeias 
· Exemplo: w = 0100 indica a cadeia w = 0100.
🔹 Concatenação de Cadeias
· Definição: Operação de unir duas cadeias, colocando uma cadeia como sufixo da outra.
· Exemplo: Se v = 110 e w = 0100, então a concatenação de w e v resulta em wv = 0100110.
· Com a cadeia vazia (λ):
· λw = wλ = w (a concatenação com λ não altera a cadeia).
🔹 Origem das Linguagens Formais
· Noam Chomsky foi um dos primeiros estudiosos e formuladores da teoria das linguagens formais. 
· Ele é autor de trabalhos fundamentais sobre as propriedades matemáticas dessas linguagens, tendo seu nome associado à chamada hierarquia de Chomsky.
🔹 Linguagem Formal
· Definição: Um conjunto finito ou infinito de cadeias de comprimento finito formadas pela concatenação de símbolos de um alfabeto finito e não vazio.
· Exemplo: O alfabeto binário {0, 1} pode gerar palavras de qualquer comprimento (por isso, a linguagem gerada por ∑* é infinita).
· Comentário: Mesmo um alfabeto simples, como {0, 1, λ}, pode gerar uma linguagem infinita (porque as cadeias podem ter tamanho indefinido).
🔹 Limitação do Tamanho das Cadeias
· Possibilidade de Limitação: É possível limitar o tamanho das cadeias em uma linguagem, tornando-a finita.
· Exemplo: Se a linguagem for limitada, como no caso de um conjunto específico de palavras, ela pode ser finita, ou seja, ter apenas um número limitado de cadeias.
🔹 Sentença de uma Linguagem
· Definição: Uma cadeia em uma linguagem (L ou ∑*) é chamada de sentença da linguagem.
· Exemplo: Se L = {λ, 01, 0011, 000111}, então essas são sentenças da linguagem L.
🔹 Operações em Linguagens Formais
· Além das operações previamente definidas para conjuntos, como união, diferença e intersecção, outras operações, como a concatenação, também são fundamentais para a definição e o estudo das linguagens formais.
· Exemplo: Seja a linguagem definida pela sentença a seguir: L = {0ⁿ1ⁿ : n ≥ 0}
Regras: Seja a linguagem definida pela sentença a seguir:
· “0” à esquerda: Zero ou mais símbolos “0” à esquerda, ou como prefixo. 
· “1” à direita: Zero ou mais símbolos “1” à direita, ou como sufixo.
· O número de zeros e uns: O número de zeros e uns é o mesmo.
· Exemplos de palavras nessa linguagem: λ, 01, 0011, 000111....
· Palavras que não pertencem a esta linguagem: 0, 1, 011, 001 (pois o número de zeros e uns não é o mesmo).
🔹 Síntese Conceitual - Grafo
· O grafo abaixo pode ser usado para representar visualmente a concatenação de palavras e as relações entre diferentes sentenças e linguagens.
✅ Resumo Final
· Alfabeto: conjunto finito de símbolos (como {0, 1, λ}).
· Cadeias: sequências de símbolos do alfabeto.
· Concatenação: operação que une duas cadeias.
· Linguagem Formal: conjunto de cadeias formadas a partir de um alfabeto.
· Sentenças: cada cadeia de uma linguagem.
· Operações usadas em Linguagens Formais: união, diferença, interseção e concatenação.
Gramática
🔹 O que é uma Gramática?
· Definição: A gramática é um conjunto de regras que define como formar frases ou cadeias válidas em uma linguagem.
· Função: A gramática determina se uma frase está bem formada em um idioma ou linguagem formal.
· Exemplo: Na língua portuguesa: 
"Uma frase pode consistir em um sintagma nominal seguido por um predicado" 
〈Frase〉 → 〈Sintagma Nominal〉 〈Predicado〉
🔹 Funções das Gramáticas
· Definir linguagens: Gramáticas definem linguagens como um conjunto finito de regras de geração de cadeias.
· Gerar cadeias: Uma gramática deve ser capaz de gerar todas as cadeias válidas da linguagem que ela define.
· Constituir sistemas formais: As gramáticas formam sistemas baseados em regras de substituição para gerar as cadeias de uma linguagem de maneira recursiva.
🔹 Estrutura de uma Gramática Formal
· Definição: Uma gramática é definida por uma quádrupla: G = (V, T, P, S), onde:
· V: Conjunto finito de variáveis ou símbolos não terminais.
· T: Conjunto finito de símbolos terminais (disjunto de V).
· P: Conjunto finito de produções ou regras de substituição. Ex: P= A → b
· S: Símbolo inicial ou Start Symbol (um dos símbolos não terminais).
🔹 Terminais e Não Terminais:
· Símbolos não terminais (V): São símbolos que podem ser substituídos por outros símbolos, tanto terminais quanto não terminais.
· Símbolos terminais (T): São os símbolos finais da cadeia, não podem ser mais substituídos.
🔹 Regras de Produção
· Estrutura de uma regra: As regras de produção seguem o formato a → b, onde:
· a: Contém pelo menos um símbolo não terminal.
· b: Pode ser qualquer combinação de terminais e não terminais (incluindo o nulo).
· Lado esquerdo (LE): Contém os símbolos não terminais que serão substituídos.
· Lado direito (LD): Pode conter terminais, não terminais ou uma combinação deles.
🔹 Agrupamento de Regras
· Quando várias regras têm o mesmo lado esquerdo (LE), elas podem ser agrupadas em uma única regra, com os lados direitos(LD) separados por '/'.
· Exemplo: Considere a gramática:
· Regras:
A → aA,
A → bCa,
A → ab
· As regras de produção podem ser agrupadas como: A → aA / bCa / ab 
· Assumimos que os conjuntos V e T são não vazios e disjuntos.
Vejamos um caso prático em que G seja uma gramática assim definida: G = (V, T, P, S). Assim, os elementos são:
G = (V, T, P, S)
Onde:
· V = {S} (símbolo não terminal)
· T = {0, 1} (símbolos terminais)
· P = {S → 0S, S → 1} (regras de produção)
· S = símbolo inicial
Note que, nessa gramática, o único símbolo não terminal é o próprio símbolo inicial.
· Derivação: É a cadeia gerada a partir da aplicação das regras de produção.
Como prática, geraremos a cadeia “00001” a partir da aplicação das regras de produção. 
Usamos as seguintes regras:
1. S → 0S
Substituímos "S" por "0S" → Temos a cadeia: 0S
2. S → 0S
Substituímos o "S" por "0S" → Temos a cadeia: 00S
3. S → 0S
Substituímos o "S" por "0S" → Temos a cadeia: 000S
4. S → 0S
Substituímos o "S" por "0S" → Temos a cadeia: 0000S
5. S → 1
Substituímos "S" por 1 → Temos a cadeia: 00001
A sequência gerada foi: S → 0S → 00S → 000S → 0000S → 00001
🔹 Linguagem Gerada pela Gramática
· Linguagem gerada (L(G)): A linguagem gerada pela gramática G é composta por todas as cadeias da forma L(G)=0ⁿ1, onde n > 0.
· Observação: Essa linguagem é infinita, pois o número de zeros pode crescer indefinidamente.
🔹 Distinção entre Linguagem e Gramática
· Linguagem(L(G)): É escrita como L(G) e lida como a linguagem gerada pela gramática G. É o conjunto de todas as cadeias válidas geradas pela gramática.
· Gramática (G(L)): É chamada G(L) e lida como a gramática para a linguagem L. É o conjunto de regras que gera as cadeias de uma linguagem.
✅ Resumo Final
· Gramática: Conjunto de regras que define como formar frases válidas em uma linguagem formal.
· Símbolos terminais (T): Elementos finais que compõem as cadeias.
· Símbolos não terminais (V): Elementos que podem ser substituídos por outras cadeias.
· Regras de Produção (P): Definem como substituir os símbolos não terminais.
· Símbolo inicial (S): O ponto de partida da derivação.
Aplicações práticas
🔹 Aplicações de Linguagens e Gramáticas Formais
· Uso em Compiladores: Linguagens e gramáticas formais são amplamente utilizadas para descrever linguagens de programação e são essenciais no desenvolvimento de compiladores (como os usados para Java, C, C++).
· Importância das Gramáticas: Uma gramática descreve de maneira precisa a estrutura de uma linguagem de programação. Ela é usada para validar o código e gerar as instruções do compilador.
🔹 Exemplo de Gramática para Identificadores em Linguagem C
· Regras para Identificadores: Em C, os identificadores (nomes de variáveis) têm regras específicas:
1. Um identificador pode conter letras, dígitos e sublinhados (_).
2. Um identificador deve começar com uma letra ou sublinhado.
3. Um identificador permite o uso de letras maiúsculas e minúsculas.
· Gramática Formal para Identificadores: 
· Nesta gramática o “|” representa “ou” e “λ”, a cadeia vazia. 
· Nessa gramática, as variáveis são , , , e . 
· As letras, os dígitos e os sublinhados são terminais.
· → | 
· → | | | λ
· → a | b | ... | z | A | B | ... | Z
· → 0 | 1 | ... | 9
· → _
· Derivação do Identificador "a0":
. ⇒ 
. a 
. a 
. a 0 
. a0
🔹 Árvores de Derivação
· Definição de Árvore de Derivação: Uma árvore de derivação é uma representação gráfica que mostra como uma cadeia é gerada a partir de uma gramática.
Exemplo 1: Considere a seguinte gramática: {S → aS, S → λ}:
· A produção S → aS gera uma cadeia que pode ser substituída repetidamente, enquanto S → λ termina a produção (a cadeia vazia).
· Processo de Derivação passo a passo:
· S → aS → aaS → aaaS → aaaaS → ...
· A linguagem gerada é formada por aⁿ, onde n ≥ 0.
· Forma Geral da Linguagem: L(G) = aⁿ, n ≥ 0 (incluindo a cadeia vazia λ).
· Exemplo Gráfico de Árvore: A árvore de derivação ao lado ilustra o processo de derivação passo a passo.
Exemplo 2: Considere a seguinte gramática: {S → aSb, S → λ}
· Produção: S → aSb ou S → λ
· O símbolo S pode ser substituído por aSb ou λ.
· Geração das Cadeias:
· A partir de S → aSb, a substituição de S pode gerar as cadeias: 
· S → aSb
· → aaSbb
· → aaaSbbb
· ...
· Finaliza com: S → λ
📌 Etapas para gerar “aabb”:
1. S → aSb
2. → aaSbb
3. → aaλbb = aabb ✅
📌 Cadeias válidas:
· λ (n = 0)
· ab (n = 1)
· aabb (n = 2)
· aaabbb (n = 3)
· ... 
· O número de a's será igual ao número de b's.
· Forma Geral da Linguagem: L(G) = aⁿbⁿ, n ≥ 0 (incluindo a cadeia vazia λ).
· Árvore de Derivação: A árvore de derivação acima, ilustra como aSb é substituído por λ e gera as cadeias desejadas.
🔹 Resumo Final das Linguagens Geradas
· Linguagens Geradas pelas Gramáticas: As gramáticas podem gerar linguagens infinita ou limitada dependendo das regras e do processo de derivação.
· Linguagem Gerada por {S → aS, S → λ}:
· Linguagem: aⁿ, onde n ≥ 0.
· Exemplo de cadeias: λ, a, aa, aaa, ...
· Linguagem Gerada por {S → aSb, S → λ}:
· Linguagem: aⁿbⁿ, onde n ≥ 0.
· Exemplo de cadeias: λ, ab, aabb, aaabbb, ...
✅ Resumo Prático
· Compiladores usam gramáticas formais para interpretar linguagens de programação.
· Gramáticas são compostas de símbolos terminais e não terminais, com regras que definem como as cadeias podem ser formadas. 
· Derivação: Processo de transformar símbolos não terminais em terminais.
· Árvores de derivação é uma representação gráfica das etapas de derivação
Questão 1. Os símbolos são utilizados para construir __________, que são formadas pela __________ de símbolos. Um _________ é um conjunto finito e não vazio de símbolos a partir dos quais são formadas as cadeias. Um conjunto de cadeias formadas a partir das ___________ de uma __________ bem definida compõe uma ___________.
Indique a opção que permite o correto preenchimento das lacunas:
A. Alfabetos, cadeias, alfabeto, derivações, linguagem, gramática.
B. Alfabetos, gramática, alfabeto, linguagens, concatenação, cadeia.
C. Cadeias, concatenação, alfabeto, derivações, gramática, linguagem.
D. Subcadeias, concatenação, sufixo, gramáticas, linguagem, cadeia.
E. Cadeias, subcadeias, gramáticas, alfabeto, linguagem, prefixo.
Questão 2. Considere a seguinte L(G) = (V, T, P, S), em que V = {0, 1, S}, T = {0, 1, λ} e P: S → 0S1 e S → λ
Assinale a alternativa que contém somente cadeias geradas a partir dessa gramática:
A. 010, 101, 01, 1100.
B. 01, 0011, 001, 011.
C. 10, 1100, 100, 110.
D. 01, 0011, 000111, λ.
E. 010, λ, 0011, 1100, 101.
Módulo 4. Hierarquia de Chomsky
Classes de linguagens
Origem e importância do estudo linguagens formais
· O estudo das linguagens formais ganhou força no final da década de 1950, com as publicações do linguista Noam Chomsky.
· Antes disso, não existia uma teoria estruturada sobre linguagens formais.
· A partir dos anos 1960, essa teoria passou a ser fundamental na Engenharia e na Ciência da Computação.
Aplicações práticas
· As linguagens formais são essenciais para a criação de linguagens de programação.
· Ela se tornou muito útil para o estudo das linguagens de programação, principalmente na construção de compiladores e interpretadores, dependem de uma descrição precisa da linguagem.
· As gramáticas formais são a forma mais usada para definir essas linguagens de forma rigorosa.
 A contribuição de Noam Chomsky
· Chomsky criou uma classificação hierárquica das linguagens, conhecida como Hierarquia de Chomsky.
· Ele propôs uma classificação hierárquica das linguagens formais em quatro níveis de complexidade (do mais simples ao mais complexo).
· Ela se tornou muito útil para o estudo das linguagens de programação, principalmente na construção de compiladores e interpretadores. 
· Essa hierarquia é baseada nas restrições das regras de produção das gramáticas (α → β)
🔹 As 4 classes Hierarquia de Chomsky 
	Tipo
	NomeCaracterísticas principais
	Aplicação comum
	Tipo 0
	Linguagens Irrestritas
(Gramáticas com estrutura de frase) 
	Gramáticas mais gerais, sem restrições sobre as regras de produção (forma α → β).
	Teoria computacional, autômatos universais
	Tipo 1
	Linguagens Sensíveis ao Contexto
	As regras de produção dependem do contexto em que os símbolos aparecem.
	Modelos mais complexos de linguagem
	Tipo 2
	Linguagens Livre de Contexto
	As regras têm sempre a forma: um não terminal → sequência de terminais e não terminais.
	Análise sintática em compiladores
	Tipo 3
	Linguagens Regulares
	As regras têm formato simples (como A → aB ou A → a).
	Análise léxica em compiladores
Isso mostra que, à medida que subimos na hierarquia, a complexidade e o poder das gramáticas aumentam.
🔹 Aplicações práticas dos Tipos 2 e 3
· Tipo 2 (Livre de Contexto):
Utilizado na análise sintática (montagem de árvores sintáticas) para verificar se uma sequência de símbolos (como um comando de código) está corretamente estruturada.
· Tipo 3 (Regulares):
Utilizado na análise léxica, responsável por identificar palavras válidas (como variáveis, números ou palavras-chave) em uma linguagem de programação.
✅ Resumo Final
· A Hierarquia de Chomsky classifica linguagens formais em 4 tipos, do mais simples (Tipo 3) ao mais complexo (Tipo 0).
· É uma base fundamental para linguagens de programação, pois permite descrever, processar e validar instruções de forma sistemática.
· Os níveis 2 e 3 são os mais aplicados na construção de compiladores e interpretadores, facilitando o entendimento e processamento automático de código.
Classes de linguagens tipos 0 e 1
🔷 Tipo 0 – Gramáticas Irrestritas (ou com estrutura de frase)
✅ Definição:
· São as mais gerais entre todas as gramáticas.
· Não possuem restrições na forma das regras de produção.
· Capazes de gerar qualquer linguagem que seja recursivamente enumerável (linguagens naturais humanas são exemplos disso).
📌 Estrutura da gramática:
G = (V, T, P, S), onde:
· V = Conjunto de símbolos não terminais;
· T = Conjunto de símbolos terminais;
· P = Produções no formato α → β, com α ≠ λ;
· S = Símbolo inicial.
Obs.: Em gramáticas irrestritas, V e T podem ter símbolos em comum. A distinção entre terminais e não terminais serve apenas para sabermos quando a derivação pode parar.
🧪 Exemplo de gramática irrestrita: G = ({S, A, B, C, D, E}, {0}, P, S)
📌 Objetivo: Mostrar como uma gramática sem restrições consegue gerar palavras com número par de zeros, como por exemplo: 00, 0000, 000000, etc.
🎯 Definição da gramática: G = (V, T, P, S)
· V (símbolos não terminais): {S, A, B, C, D, E}
· T (símbolo terminal): {0}
· P (conjunto de regras de produção):
1. S → AC0B
2. C0 → 00C
3. CB → DB
4. CB → E
5. 0D → D0
6. AD → AC
7. 0E → E0
8. AE → λ (a cadeia vazia)
🧩 Vamos gerar a menor palavra da linguagem, passo a passo: A menor palavra que essa gramática pode gerar é “00”. Vamos entender como isso é feito.
🔁 Etapa 1 – Começamos com o símbolo inicial: S
🔁 Etapa 2 – Aplicamos a regra 1:
S → AC0B
Agora temos: AC0B
🔁 Etapa 3 – Aplicamos a regra 2:
C0 → 00C
Temos AC0B → A00CB
🔁 Etapa 4 – Aplicamos a regra 4:
CB → E
Temos A00CB → A00E
🔁 Etapa 5 – Aplicamos a regra 7:
0E → E0
A00E → A0E0
🔁 Etapa 6 – Aplicamos a regra 7 novamente:
0E → E0
A0E0 → AE00
🔁 Etapa 7 – Aplicamos a regra 8:
AE → λ
AE00 → 00
✅ Resultado final: A cadeia gerada é: “00” (com dois zeros → número par)
📌 Expressão geral da linguagem: L(G) = {0²ⁿ | n é inteiro positivo} → palavras com números pares de zeros
🔷 Tipo 1 – Gramáticas Sensíveis ao Contexto
✅ Definição:
· Sentenças válidas dependem do contexto em que os símbolos aparecem.
· São mais restritas que as do Tipo 0, porém mais poderosas que as livres de contexto.
· Exemplos ocorrem em linguagens de programação, onde símbolos devem aparecer em combinação válida com outros.
📌 Estrutura da gramática:
· Produções: αAβ → αγβ, onde
· A é não terminal
· α, γ, β são cadeias
· O comprimento da direita é maior ou igual ao da esquerda
· É permitida a regra S → λ, desde que S não apareça no lado direito de nenhuma outra produção.
🧪 Exemplo de dependência de contexto: Considere o seguinte exemplo prático em linguagem Java:
public class LG1 {
    public static void main(String[] args) {
        int i = 5;
        System.out.printf("%d", i);
    }
}
· 📌 Por que isso é sensível ao contexto? Porque o uso de “i” depende do contexto anterior onde ela foi declarada.
· 💥 Se você tentar usar “i” sem ter declarado antes, o compilador dá erro.
· Portanto: ✅ O uso correto de “i” depende de ela existir no contexto atual do programa (escopo, tipo, nome).
 Comparando com gramáticas
· Em gramáticas livres de contexto (tipo 2), cada substituição é feita sem se preocupar com o que está antes ou depois.
· Já em gramáticas sensíveis ao contexto (tipo 1), as substituições só são válidas se respeitarem o contexto.
· No código Java: O compilador precisa verificar o contexto inteiro para saber se i:
· Foi declarada.
· Está no escopo correto.
· Está sendo usada com o tipo compatível.
Conclusão:
· Esse código é sensível ao contexto porque:
· O compilador não pode analisar cada linha isoladamente.
· Ele precisa entender o contexto global, principalmente:
· Declarações anteriores
· Escopo da variável
· Tipagem correta
· 🎓 Isso mostra que linguagens de programação modernas exigem verificações contextuais — por isso são classificadas dentro das linguagens sensíveis ao contexto na hierarquia de Chomsky (tipo 1).
🧪 Exemplo de gramática sensível ao contexto: G = (V, T, P, S)
· V (símbolos não terminais): {A, B, C, H, S}
· T (terminais): {0, 1, 2}
· P (regras de produção):
1. S → 0SBC
2. S → 0BC
3. CB → HB
4. HB → HC
5. HC → BC
6. 0B → 01
7. 1B → 11
8. 1C → 12
9. 2C → 22
🧩 Passo a passo para gerar a cadeia “012”: Queremos transformar S em 012.
🔁 Etapa 1 – Aplicamos a regra 2:
S → 0BC
Agora temos: 0BC
🔁 Etapa 2 – Aplicamos a regra 6:
0B → 01
Temos 0BC → 01C
🔁 Etapa 3 – Aplicamos a regra 8:
1C → 12
Temos 01C → 012
✅ Resultado final: “012”
💡 O que essa gramática está fazendo?
Ela garante que para cada 0, temos um 1 e um 2 correspondentes:
· O símbolo B se transforma em 1 com base no símbolo anterior.
· O símbolo C se transforma em 2 com base no símbolo anterior.
Essa dependência entre os símbolos é o que caracteriza uma sensibilidade ao contexto.
📌 Expressão geral da linguagem: L(G) = {aⁿ bⁿ cⁿ | n ≥ 1} → Exige mesmo número de a, b e c, algo impossível de validar com gramáticas livres de contexto.
Resumo Final
	Tipo
	Nome
	Restrições nas Produções?
	Exemplo de Linguagem
	0
	Gramáticas irrestritas
	Nenhuma restrição (exceto α ≠ λ)
	Linguagem com 0²ⁿ
	1
	Gramáticas sensíveis ao contexto
	Regra: αAβ → αγβ,
	γβ
Classes de linguagens tipos 2 e 3
🔵 Tipo 2 – Linguagens Livres de Contexto
📌 Definição:
· Produções com formato A → β, onde:
· A é um símbolo não terminal.
· β é uma sequência de símbolos terminais e/ou não terminais.
· As regras não dependem do contexto em que aparecem.
🧠 Aplicações: Muito usadas para definir a estrutura de linguagens de programação, como Java, C, C++ e Pascal.
🧪 Exemplo: G = (V, T, P, S), em que V = {+, *, (, ), id, E, T, F}. Verifique se a expressão id * (id + id) pode ser gerada pela gramatica G.
Gramática G:
· Não terminais (V): {E, T, F}
· Terminais (T): {+, *, (, ), id}
· Regras (P):
1. E → E + T
2. E → T
3. T → T * F
4. T → F
5. F → (E)
6. F → id
🎯 Objetivo: Queremos saber se a expressão id * (id + id) pode ser gerada pela gramática G. Vamos derivar passo a passo. 
🔁 Etapas da derivação
Objetivo final: chegar na expressão id * (id + id) usando as regras acima, partindo do símbolo inicial E.
1. Começamos com: E(símbolo inicial)
2. Aplicamos a regra 2: 
E → T
Agora temos: T
3. Aplicamos a regra 3: 
T → T * F
Agora temos: T * F
4. Aplicamos a regra 4 no primeiro T: 
T → F
Agora temos: F * F
5. Aplicamos a regra 6 no primeiro F: 
F → id
Agora temos: id * F
6. Aplicamos a regra 5 no segundo F: 
F → (E)
Agora temos: id * (E)
7. Dentro dos parênteses temos E, aplicamos a regra 1:E → E + T
Agora temos: id * (E + T)
8. Aplicamos a regra 2 para E: 
E → T
Agora temos: id * (T + T)
9. Aplicamos a regra 4 para cada T: 
T → F
Agora temos: id * (F + F)
10. Aplicamos a regra 6 para cada F: 
F → id
✅Resultado final: id * (id + id) → Conseguimos gerar a expressão!
🌳 Árvores de Derivação:
· Representam a estrutura hierárquica da derivação.
· Facilitam a análise sintática em compiladores.
Propriedades:
· Raiz: símbolo inicial (S)
· Nós internos: símbolos não terminais (V)
· Folhas: símbolos terminais ou λ (vazio)
· Cada regra de produção se reflete como um "ramo" da árvore.
🧠 Conclusão
· Esta gramática é do tipo 2 (livre de contexto).
· Ela define expressões aritméticas com identificadores, soma, multiplicação e parênteses.
· A estrutura da expressão é garantida pelas regras de produção, que formam sentenças bem formadas como id + id, id * (id + id) etc.
· Isso é essencial para analisadores sintáticos em compiladores.
🟢 Tipo 3 – Linguagens Regulares
📌 Definição:
· Produções com formato restrito, como:
· A → aB (terminal seguido de não terminal)
· A → a (apenas terminal)
· São as mais simples e rápidas de reconhecer.
🧠 Aplicações:
· Utilizadas em análise léxica de compiladores.
· Geram expressões regulares (como em buscas com regex).
Observação: Formalmente, essas regras podem ser descritas por uma gramática, em que “|” representa “ou”.
🧪 Exemplo: G = (V, T, P, S), em que V= {int, dígito}, T = {0, 1...., 9}, S = int e P:
· → + | - ;
· → 0 | 1 | 2 |...| 9;
· → 0 | 1 | ... | 9.
Gramática G:
· V = {int, dígito}
· T = {0,1,2,...,9}
· S = int
· Regras (P):
· → + | - 
· → 0 | 1 | ... | 9 
· → 0 | 1 | ... | 9
Atenção: 
 - Nessa gramática, as variáveis são e .
- Os algarismos são os terminais.
🎯 Por exemplo derivar: +21
Passo a passo:
1. → + 
2. → 2 
3. → 1
Resultado: +21
📊 Resumo da Hierarquia de Chomsky (Tipos 0 a 3)
	Tipo
	Nome
	Exemplo de Uso
	Complexidade
	0
	Gramáticas irrestritas
	Linguagens naturais
	Alta
	1
	Gramáticas sensíveis ao contexto
	Regras com dependência (ex: escopo de variável)
	Alta
	2
	Gramáticas livres de contexto
	Linguagens de programação (estrutura)
	Média
	3
	Gramáticas regulares
	Expressões regulares (análise léxica)
	Baixa
✅ Conclusão:
· Tipo 2 (livres de contexto): essenciais na análise sintática de linguagens de programação. Permitem uso de parênteses aninhados, operadores etc.
· Tipo 3 (regulares): aplicadas na análise léxica, como reconhecer números, palavras-chave, identificadores.
· Todas essas classes ajudam a estruturar e processar linguagens, seja em linguagens naturais ou de programação.
📊 Resumo da Hierarquia de Chomsky 
🧩 Tipo 0 – Linguagens Recursivamente Enumeráveis
📌 Características:
· Mais genérica e poderosa de todas.
· Sem restrição nas regras de produção.
· Regras podem ter qualquer número de símbolos antes e depois da seta, desde que o lado esquerdo não seja vazio.
🧠 Singularidade:
· Pode simular qualquer algoritmo computável (Máquina de Turing).
· Nem sempre é possível saber se uma palavra pertence à linguagem (problema da parada).
📏 Tipo 1 – Linguagens Sensíveis ao Contexto
📌 Características:
· Permite substituições que dependem do contexto.
· Regras seguem o formato αAβ → αγβ, onde:
· A: não terminal.
· α, β, γ: cadeias de símbolos.
· γ não pode ser menor que A (crescimento ou mesmo tamanho).
🧠 Singularidade:
· Útil para linguagens onde certas partes dependem de outras (como declaração e uso de variáveis).
· Reconhecida por um autômato linearmente limitado (memória proporcional à entrada).
🧮 Tipo 2 – Linguagens Livres de Contexto
📌 Características:
· Regras têm um único não terminal à esquerda.
· Forma: A → β
· Muito usada para definir sintaxe de linguagens de programação.
🧠 Singularidade:
· Pode representar aninhamento (ex: parênteses), mas não consegue verificar igualdade entre blocos paralelos (como aⁿbⁿcⁿ).
🧮 Tipo 3 – Linguagens Regulares
📌 Características:
· Mais simples de todas.
· Regras têm formato fixo:
· A → a ou
· A → aB
· Pode ser escrita como expressão regular.
🧠 Singularidade:
· Usada em análise léxica de compiladores.
· Reconhecida por autômatos finitos (sem memória além do estado atual).
· Não suporta aninhamentos ou contagens balanceadas.
🧠 Dica Prática para Identificação
1. Possui regras com qualquer forma? → Tipo 0
2. Regras aumentam ou mantêm o tamanho da cadeia? → Tipo 1
3. Regras têm sempre 1 não terminal à esquerda? → Tipo 2
4. Regras seguem A → a ou A → aB? → Tipo 3
📊 Resumo Visual
Tipo 0 (mais poderoso)
└── Tipo 1 (⊂ Tipo 0)
 └── Tipo 2 (⊂ Tipo 1)
 └── Tipo 3 (⊂ Tipo 2)
Cada tipo contém os anteriores, ou seja:
· Toda linguagem regular é livre de contexto.
· Toda livre de contexto é sensível ao contexto.
· Toda sensível ao contexto é recursivamente enumerável.
Questão 1. Assinale a única alternativa que contém a disposição correta da esquerda para a direita, em ordem crescente, dos tipos de gramática que, segundo a hierarquia de Chomsky, geram as linguagens.
A. Gramáticas regulares → Gramáticas livres de contexto → Gramáticas sensíveis ao contexto → Gramáticas com estrutura de frase.
B. Gramáticas com estrutura de frase → Gramáticas sensíveis ao contexto → Gramáticas livres de contexto → Gramáticas regulares.
C. Gramáticas livres de contexto → Gramáticas com estrutura de frase → Gramáticas sensíveis ao contexto → Gramáticas regulares.
D. Gramáticas livres de contexto → Gramáticas regulares → Gramáticas com estrutura de frase → Gramáticas sensíveis ao contexto.
E. Gramáticas regulares → Gramáticas com estrutura de frase→ Gramáticas sensíveis ao contexto → Gramáticas livres de contexto.
TEMA 3 - LINGUAGENS REGULARES
Módulo 1. Gramáticas regulares
Conjuntos
🔹 Definição de Conjunto
· Um conjunto é uma coleção bem definida de elementos (ou objetos).
· Notação:
· Se o elemento x pertence ao conjunto S, escrevemos: x ∈ S.
· Se x não pertence, escrevemos: x ∉ S.
🔹 Forma de Escrever Conjuntos
1. Por propriedade:
· Exemplo: S = {x : x é número natural}
Lê-se: “S é o conjunto de todos os x tais que x é um número natural”.
2. Por listagem (elementos entre chaves):
· Exemplo: S = {0, 1, 2}
Esse é um conjunto com três elementos: 0, 1 e 2.
3. Com reticências (...):
· Exemplo: {a, b, ..., z} → todas as letras minúsculas.
· Exemplo: {1, 3, 5, ...} → todos os números ímpares positivos.
4. Quando necessário deve-se usar a notação mais explícita:
· Exemplo: S = {i : i > 0, i é ímpar}
Lê-se: “S é o conjunto de todos os i tal que i é maior que 0 e i é ímpar”. 
🔹 Tipos de Conjuntos
· Finito: Tem quantidade limitada de elementos.
Ex: S = {0, 1, 2, ..., 7} → tem 8 elementos → |S| = 8.
· Infinito: Tem infinitos elementos.
Ex: S = {..., -2, -1, 0, 1, 2, ...} → conjunto dos inteiros.
· Unitário: Contém apenas um elemento.
Exemplos:
· {0} → contém o número 0.
· {f} → contém a letra f.
· {∅} → contém o conjunto vazio como elemento.
🔹 Igualdade de Conjuntos
· Dois conjuntos são iguais se têm os mesmos elementos, independentemente da ordem.
🔹 Operações com Conjuntos
1. União ( ∪ )
A ∪ B = {x : x ∈ A ou x ∈ B}
→ junta os elementos de A e B (sem repetir).
2. Interseção ( ∩ )
A ∩ B = {x : x ∈ A e x ∈ B}
→ elementos que estão em ambos os conjuntos.
3. Diferença ( − )
A − B = {x : x ∈ A e x ∉ B}
→ elementos que estão em A, mas não em B.
4. Complemento ( ¯ ou C)
Se U é o conjunto universal, então:
Y̅ = {x : x ∈ U e x ∉ Y}
→ tudo o que está fora de Y, mas dentro de U. 
5. Conjuntos Disjuntos:
· Dois conjuntos são disjuntos quando não têm elementos em comum.
· Notação: A ∩ B = ∅
🔹 Conjunto Vazio (∅)
· ∅ = conjunto sem elementos.
· Propriedades:
· S ∪ ∅ = S
· S − ∅ = S
· S ∩ ∅ = ∅
· ∅c = U (complemento do vazio é o conjunto universal)
🔹 Produto Cartesiano ( A × B )
· Combina todos os pares possíveis entre dois conjuntos.
Exemplo:
· A = {2, 3}, B = {4, 5}
· A × B = {(2,4), (2,5), (3,4), (3,5)}
🔹Concatenação (AB)
· Forma todas as combinações possíveis entre os elementos de A e B, como "letras coladas".
Exemplo:
· A = {a, b}, B = {c, d}
· AB = {ac, ad, bc, bd}
🔹 Subconjunto
· Dizemos que A ⊂ B (A é subconjunto de B) se todo elemento de A está em B.
🔹 Conjunto das Partes (ou Conjunto Potência)
· Conjunto com todos os subconjuntos possíveis de um conjunto S.
· Se S tem n elementos, então o conjunto das partes tem 2ⁿ subconjuntos.
Exemplo:
· Se S = {1, 2}, então 2² = 4 subconjuntos:
→ {}, {1}, {2}, {1, 2}
Relações e funções
🔹 1. Produto Cartesiano
· O produto cartesiano de dois conjuntos A e B é o conjunto de todos os pares ordenados (a, b), onde:
· a ∈ A e b ∈ B.
Notação:
A × B = {(a, b) | a ∈ A e b ∈ B}
Importante:
· A ordem dos elementos importa:
(a, b) ≠ (b, a), se a ≠ b.
🧠 Exemplo:
· A = {a, b, c}, B = {0, 1}
· A × B = {(a, 0), (a, 1), (b, 0), (b, 1), (c, 0), (c, 1)}
🧠 Exemplo:
🔹 2. Relações entre Conjuntos
· Uma relação R entre A e B é um subconjunto de A × B.
· Nesse contexto:
· A = domínio
· B = contradomínio
· Os pares (a, b) são chamados de pares ordenados da relação.
🔹 3. Relação de Equivalência
· É uma relação especial que generaliza a ideia de igualdade.
· Notação: 
Para ser uma relação de equivalência, deve seguir 3 propriedades:
	Propriedade
	Significado
	Reflexiva
	Todo elemento se relaciona consigo mesmo: 
	Simétrica
	Se , então também 
	Transitiva
	Se e , então 
🧠 Exemplo: No conjunto de inteiros não negativos, podemos definir uma relação x≡y se, e apenas se, x mod3=ymod3, em que mod é o resto da divisão inteira de x por y. Então, 2≡5,9≡0 e 12 ≡0. Claramente, essa é uma relação de equivalência, pois satisfaz a reflexividade, a simetria e a transitividade.
· Defina a relação: x ≡ y se x mod 3 = y mod 3
(ou seja, se o resto da divisão por 3 for o mesmo)
· Verificações:
· 2 mod 3 = 2, e 5 mod 3 = 2 → então 2 ≡ 5
· 9 mod 3 = 0, e 12 mod 3 = 0 → então 9 ≡ 12
✅ A relação é de equivalência: satisfaz as 3 propriedades!
🔹 4. Função – Definição
· Uma função é uma regra que associa a cada elemento do domínio (A) a um único elemento do contradomínio (B).
Notação geral:
f: A → B
· f(x) indica o valor correspondente a x no conjunto B.
· Também representada como:
y = f(x)
🔹 5. Termos Importantes em Funções
	Termo
	Significado
	f
	Nome da função
	A
	Domínio (de onde saem os valores x)
	B
	Contradomínio (onde estão os possíveis valores de saída)
	y=f(x)
	expressão da lei de correspondência (relação) dos elementos x em A com os elementos y em B.
🔹 6. Condição para ser uma Função
· Uma relação f: A → B é função se, para cada x ∈ A, existe no máximo um y ∈ B tal que:
f(x) = y
Em outras palavras:
· Não pode haver um mesmo x associado a dois valores diferentes de y.
🧠 Exemplo prático:
A = {1, 2, 3}, B = {a, b}
· Relação R = {(1, a), (2, a), (3, b)} ✅ → é função
· Cada elemento de A está relacionado com apenas um valor de B.
Relação R = {(1, a), (1, b), (2, a)} ❌ → não é função
· O elemento 1 está ligado a dois valores diferentes: a e b.
🔹 O que são Diagramas de Venn?
· São representações gráficas usadas na Matemática para:
· Mostrar conjuntos
· Visualizar relações entre conjuntos
· Resolver problemas de teoria dos conjuntos
🔹 Diagramas de Venn em Funções
· Também podem ser usados para representar funções que ligam elementos de um domínio (A) a um contradomínio (B).
🧠 Exemplo:
· Suponha a função:
f: A → B
f(x) = 2x
· Se x = 2, então f(2) = 4
· Isso significa que 2 (do domínio A) está relacionado a 4 (no contradomínio B)
· O conjunto imagem é o conjunto de todos os valores do contradomínio que foram realmente usados pela função.
🟢 Visualmente:
No diagrama de Venn, desenhamos:
· Um círculo para o domínio A
· Um círculo para o contradomínio B
· E setas ligando cada valor de A ao seu correspondente em B
Outro exemplo de um diagrama de Venn:
🔹 O que é o Gráfico de uma Função?
· É a representação no plano cartesiano (eixos x e y) da função f(x).
Notação:
Gráfico de f: D → I é o conjunto de pontos (x, f(x)), com x ∈ D
Ou seja: Gráfico = {(x, y) ∈ D × I : y = f(x)}
🔹 Exemplo: Gráfico da função y = 2x + 1
Vamos montar a tabela com alguns valores de x e calcular f(x): 
	x
	y = 2x + 1
	-1
	-1
	0
	1
	1
	3
	2
	5
Agora, o gráfico será composto pelos pontos:
 (-1,-1), (0,1), (1,3), (2,5)
No plano cartesiano:
· Eixo x → valores de entrada (domínio)
· Eixo y → valores de saída (imagem)
Você liga os pontos com uma reta, pois é uma função do 1º grau (linear).
✅ Resumo Visual dos Conceitos
	Conceito
	Representação
	Diagrama de Venn
	Círculos que mostram relações entre conjuntos ou pares ligados
	Gráfico de função
	Pontos (x, f(x)) no plano cartesiano
	Imagem da função
	Todos os y que têm um x correspondente no domínio
Noções básicas sobre linguagens
🔹 1. Símbolo
· É a unidade mais básica (como uma letra ou número).
· Exemplo de símbolos: 0, 1, a, b
🔹 2. Alfabeto (Σ)
· É um conjunto finito de símbolos.
· Representado por: Σ
Exemplos:
· Σ = {0, 1} → alfabeto binário
· Σ = {A, B, ..., Z, a, b, ..., z} → alfabeto da língua portuguesa
🔹 3. Cadeia (ou Palavra)
· É uma sequência finita de símbolos do alfabeto.
· Representada por: w
· O tamanho da cadeia é escrito como |w|.
Exemplo:
· w = 000111
· |w| = 6 (pois tem 6 símbolos)
🔹 4. Cadeia Vazia (λ)
· Cadeia sem nenhum símbolo.
· Notação: λ
· Exemplo: |λ| = 0
🔹 5. Prefixo de uma Cadeia
· É qualquer sequência do início da cadeia.
Exemplo:
· w = 0111
· Prefixos: λ, 0, 01, 011, 0111
· Total: 5 prefixos → n + 1 (n = 4)
🔹 6. Prefixo Próprio 
· Todo prefixo que não é igual à cadeia completa.
Exemplo:
· w = 0111
· Prefixos próprios: λ, 0, 01, 011
🔹 7. Sufixo de uma Cadeia
· É qualquer sequência do final da cadeia.
Exemplo:
· w = 0110
· Sufixos: λ, 0, 10, 110, 0110
· Total: 5 sufixos → n + 1 (n = 4)
🔹 8. Sufixo Próprio
· Todo sufixo que não é a cadeia completa.
Exemplo:
· w = 0110
· Sufixos próprios: λ, 0, 10, 110
🔹 9. Subcadeia (ou Fator)
· É qualquer sequência contínua de símbolos da cadeia (início, meio ou fim).
Exemplo:
· w = 012 (n = 3)
· Subcadeias: λ, 0, 1, 2, 01, 02, 12, 012
· Total: 2n = 2³ = 8 subcadeias
🔹 10. Concatenação de Cadeias
· É a junção de duas cadeias em uma só.
Exemplo:
· w₁ = 01, w₂ = 10
· w₁ · w₂ = 0110
✅ Linguagem Formal e Gramática
🔹 11. Linguagem Formal
· É um conjunto de cadeias formadas a partir de um alfabeto, seguindo regras específicas (gramática).
· Muito usada para modelar linguagens de programação.
🔹 12. Gramática
· Define as regras de formação das cadeias válidas de uma linguagem.
· Representada por uma quádrupla:
G = (V, T, P, S)
Significados:
	Símbolo
	Significado
	V
	Conjunto de símbolos não terminais (variáveis que podem ser substituídas)
	T
	Conjunto de símbolos terminais (letras ou símbolos finais da cadeia)
	P
	Conjunto de regras de produção (substituições permitidas)
	S
	Símbolo inicial da gramática (de onde começam as derivações)
🔹 13. Regras de Produção 
· Cada produção tem dois lados:
· Lado Esquerdo (LE):
· Deve conter pelo menos um símbolo não terminal
· Exemplo: S → aA
· Lado Direito (LD):
· Pode conter terminais, não terminais ou até ser vazio (λ)
Exemplo: 
🔹 14. Terminais vs. Não Terminais
	Tipo
	Significado
	Terminais (T)
	Símbolos definitivos, que não mudam mais nas regras
	Não Terminais (V)
	Símbolos intermediários, que ainda podem ser substituídos
🧠 Resumo com Exemplo da Gramática
Seja G = (V, T, P, S) com:
· V = {S, A}
· T = {a, b}
· P = {S → aA, A → b}
· S = S
Cadeia gerada:
· Começa em S
· S → aA
· A → b
· Resultado final: ab
Gramáticas lineares e classes de linguagens
🔹 1. Hierarquia de Chomsky
A Hierarquia de Chomsky classifica as linguagens formais em 4 tipos, da mais geral para a mais restrita:
	Tipo
	Nome
	Características principais
	0
	Gramática irrestrita
	Sem restrições; qualquer forma de produção
	1
	Sensível ao contexto
	O tamanho da saída depende do contexto
	2
	Livre de contexto
	Produções da forma A → α
	3
	Regular
	Produções mais restritas, muito simples
· As gramáticas da hierarquia de Chomsky são diferenciadasa partir de restrições aplicadas às produções da forma α→β.
· Linguagens regulares (tipo 3) são as mais simples e podem ser descritas por expressões regulares (ER). 
· Uma expressão regular é aceita pela máquina chamada de autômatos finitos (AF).
🔹 Relembrando a Gramática Regular (Tipo 3)
São aquelas com produções do tipo:
A → α ou A → αB
Onde:
· A, B são não terminais
· α é um símbolo terminal
🔹 3. Gramáticas Lineares
Gramáticas lineares são gramáticas do tipo 3 e podem ser:
✅ Linear à direita
· Produções da forma: As variáveis estão à direita dos terminais: A → aB ou A → a
· Exemplo: 
G1 = ({S, A}, {0, 1, 2}, {S → 0S, S → 1S, S → A, A → 2}, S)
✅ Linear à esquerda
· Produções da forma: As variáveis estão à esquerda dos terminais: A → Ba ou A → a
· Exemplo: 
G2 = ({S, A}, {0, 1, 2}, {S → S2, S → A, A → 1, A → 0}, S)
➡️ Ambas geram linguagens regulares.
➡️ Têm a mesma capacidade de representação.
✅ Expressões Regulares (ER)
🔹 4. Definições Recursivas de ER
· Quaisquer terminais, ou seja, os símbolos que pertencem a Σ, são expressões regulares. 
· A cadeia nula (λ) e o conjunto nulo (Ø) também são expressões regulares. 
· Se P e Q são duas ER, então a união das duas ER denotadas por P + Q também é uma ER;
· Se P e Q são duas ER, então sua concatenação denotada por PQ também é uma ER;
· Se P for uma ER, então a iteração (repetição ou fechamento) denotada por P* também é uma ER;
· Se P é uma ER, então (P) é uma ER;
· As expressões obtidas pela aplicação repetida das regras de anteriores em ∑ também são ER.
· ER podem ser combinadas usando:
	Operação
	Exemplo
	Significado
	União
	a + b
	a ou b
	Concatenação
	ab
	a seguido de b
	Fechamento
	a*
	zero ou mais repetições de a
	Agrupamento
	(a + b)*
	qualquer sequência de a's e b's
🔹 5. Operações Básicas sobre ER
✅ União (R₁ + R₂)
· Combina linguagens:
L(R₁ + R₂) = L(R₁) ∪ L(R₂)
✅ Concatenação (R₁R₂)
· Junta elementos de R₁ com R₂:
L(R₁R₂) = {xy | x ∈ L(R₁) e y ∈ L(R₂)}
L(R₁R₂) = L(R₁ ∩ R₂) 
✅ Fechamento de Kleene (R*)
· L(R∗) = É uma cadeia obtida pela concatenação de n elementos para n ≥ 0.
· Inclui todas as repetições, inclusive a cadeia vazia (λ).
🔹 6. Fechamento de Kleene (Σ) e Fechamento Positivo (Σ⁺)
	Tipo
	Definição
	Σ*
	Todas as cadeias possíveis (inclusive λ) com símbolos de Σ
	Σ⁺
	Todas as cadeias possíveis exceto a vazia
Exemplos:
· Se Σ = {0}, então:
· Σ* = {λ, 0, 00, 000, ...}
· Σ⁺ = {0, 00, 000, ...}
· Se Σ = {0,1}, então:
· Σ* = {λ, 0, 1, 00, 01, 10, 11, 000, ...}
· Σ⁺ = {0, 1, 00, 01, ...}
🔹 7. Exemplos de ER: Vejamos um exemplo de uma ER. Sejam as seguintes regras:
1. Uma ER consiste em qualquer combinação de a e b, começando e terminando com b.
2. Uma linguagem de qualquer combinação de a e b contendo bb como subcadeia.
3. ER de a e b contendo pelo menos 2 'b's e qualquer número de a e b entre eles.
4. ER para a linguagem L = {anbm | onde m ≥ 2 e n ≥ 0}.
Regra 1: Cadeias que começam e terminam com b, com qualquer coisa no meio
ER: *L = b(a + b)b
✅ Começa com b
✅ Termina com b
✅ Entre elas, qualquer combinação de a e b
Regra 2: Cadeias contendo a subcadeia "bb"
ER: (a + b)bb(a + b)
Regra 3: Linguagem L = {aⁿbᵐ | n ≥ 0, m ≥ 2}
ER: L = a*(bb+)
Explicação passo a passo:
· a* → qualquer quantidade de a’s (inclusive nenhum)
· bb+ → pelo menos dois b’s (um b fixo + um ou mais)
Conjunto regular formado (Ɲ): Números naturais decimais (algarismos arábicos)
ER: {0,1,2,3,4,5,6,7,8,9}{0,1,2,3,4,5,6,7,8,9}*
Ou simplesmente: D D*
Onde D = {0,1,2,3,4,5,6,7,8,9}
· Em que o * representa todas as combinações de números naturais, incluído nenhum algarismo. 
· O primeiro conjunto indica que os números devem começar por um algarismo entre 0 e 9 e podem ser seguidos de zero ou mais algarismos concatenados. Se D = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, então, Ɲ = DD*.
Questão 1. O conjunto de todas as cadeias de {0, 1} com exatamente dois zeros é:
A. 1*01*01*
B. (0 + 1)*11
C. {11 + 0}*
D. {00 + 11}*
E. (001)*
🔍 Análise da alternativa A: 1*01*01*
A expressão 1*01*01* significa:
1. 1* → qualquer quantidade de 1s (inclusive nenhum)
2. 0 → um zero
3. 1* → novamente, qualquer quantidade de 1s
4. 0 → outro zero
5. 1* → qualquer quantidade de 1s depois
Mas atenção: 1*01*01* garante exatamente dois zeros, porque:
· Só aparecem dois 0s fixos
· Não há * depois dos 0s (ou seja, não repete mais 0)
Questão 2. Analise a seguinte ER:
1. ER consiste em qualquer combinação de a e b, começando com a e terminando com b.
2. Linguagem de qualquer combinação de a e b, contendo ab como subcadeia.
3. ER de a e b contendo pelo menos um a e um b e qualquer número de a e b entre eles.
Assinale a alternativa que gera a expressão em notação do fechamento de Kleene para essa ER:
A. L = b (a + b) * b
B. L = a (a + b) * b
C. L = (a + b)*ab(a + b)*
D. a*b*
E. (ab)*
Regra 1: “Qualquer combinação de a e b, começando com a e terminando com b.”
Isso significa:
· A cadeia deve começar com 'a'
· Deve terminar com 'b'
· Pode ter qualquer número de 'a' ou 'b' no meio
Expressão: a(a + b)*b
Regra 2: Linguagem de qualquer combinação de a e b, contendo ‘ab’ como subcadeia.
· A cadeia pode ter qualquer coisa antes e depois
· Mas deve conter obrigatoriamente ‘ab’ em algum lugar
Expressão: (a+b)*ab(a+b)*
Regra 3: “Cadeias de a e b contendo pelo menos um a e um b, e qualquer número de a e b entre eles.”
· Deve conter pelo menos um ‘a’ e um ‘b’
· Pode conter qualquer outro número de a's e b's
Expressão final: a(a + b)*b que garante que há pelo menos um ‘a’ seguido de um ‘b’ → atende à condição.
Módulo 2. Autômatos finitos
Teoria dos autômatos
✅ 1. O que é Teoria dos Autômatos?
· Estudo de máquinas abstratas chamadas autômatos.
· Relaciona-se com problemas computacionais e como resolvê-los com essas máquinas.
· O termo “autômato” sugere algo que age automaticamente e independentemente.
✅ 2. Origem da teoria
· Criada por Noam Chomsky (década de 1950).
· Organizou uma hierarquia de linguagens formais com base nas gramáticas necessárias para gerá-las.
✅ 3. Aplicações dos Autômatos Finitos (AF)
· Utilizados em várias áreas da Computação e Engenharia:
· Corretores ortográficos
· Dicionários multilíngues
· Compactação de texto
· Construção de compiladores (analisadores léxicos)
· Softwares de Processamento de Linguagem Natural (PLN)
· Contagem de padrões em textos
✅ 4. Funcionamento da CPU (ligação com autômatos)
· O computador processa entradas e saídas em forma binária (‘0’ e ‘1’).
· Autômatos ajudam a modelar esse comportamento interno das máquinas.
Exemplo:
· Entrada: tecla pressionada → convertida para 0s e 1s.
· Saída: esses dados binários são processados e retornam como algo compreensível (texto, imagem, som).
✅ 5. Linguagem de Programação e Compilador
· Usuário usa linguagens como C, C++, Java, que lembram o inglês.
· O computador entende apenas código binário.
· Compilador converte essas instruções em binário.
· Para criar compiladores, é necessária uma gramática formal, que é modelada por autômatos.
✅ 6. Aplicações específicas na Computação
1. Projeto de Compiladores: Autômatos finitos detectam erros de sintaxe com gramáticas livres de contexto.
2. Funcionamento de circuitos digitais: Verifica o comportamento lógico dos circuitos com base em estados.
3. Sistemas de PLN (Processamento de Linguagem Natural): Usam autômatos para entender estruturas linguísticas.
4. Contagem de padrões: Autômatos contam quantas vezes palavras ou símbolos específicos aparecem em um texto.
✅ 7. O que é um Autômato Finito (AF)?
· Também chamado de Máquina de Estados Finitos (MEF). 
· Um AF é um modelo matemático usado para representar programas de computador ou circuitos lógicos. 
· Ele funciona como uma máquina abstrata que:
· Tem um número finito de estados.
· Está sempre em apenas um estado por vez, chamado de estado atual.
· Esse estado atual cumpre três papéis importantes:
· 🔄 Espera por uma condição para mudar para outro estado (como se estivesse aguardando um sinal).
· 🧠 Guarda informações do passado, mostrando o que já aconteceu desde que entrou nesse estado.
· ➡️ Realiza uma mudança de estado,