Questão 0

A diferença entre problemas decidíveis e problemas indecidíveis

Os problemas indedicíveis não possuem um algoritmo, logo, não tem parada garantida pois pode existir um número infinito de estados dado uma entrada.. Já os problemas decidíveis possuem algoritmo.

De que forma problemas computacionais em geral, podem ser vistos como problemas de Linguagem

A relação entre problemas decidíveis e problemas indecidíveis com a teoria das linguagens formais

Os problemas decidíveis possuem uma linguagem recursiva e, desta forma, possuem algoritmo. Já os problemas indecivéis possuem uma linguagem recursivamente enuméravel e são representados por procedure.

Diferenças entre aspectos léxicos, sintáticos e semânticos de linguagens de programação.

Na análise léxica, o programa é lido caractere por caractere para produzir uma sequência de tokens conhecidos. Com uma analogia ao português seria verificar se todas as palavras estão escritas de forma correta e também identificando se é um objeto, verbo ou sujeito.
Na análise sintática, o parser irá ler a sequência de tokens gerados na fase léxica para verificar se estão agrupados da maneira correta. Com uma analogia ao português, seria ver se, por exemplo, dois verbos não estão um ao lodo do outro (estrutura incorreta)
A análise semântica é responsável por verificar o sentido das instruções.

Diferenças, vantagens e desvantagens das diferentes formas de processamento de linguagens de programação.

A estrutura geral de um compilador e as funções básicas de cada fase.

Análise Léxica (verificar as corretude das palavras e agrupar em tokens)
Análise Sintática (verificar se os tokens estão na sequência correta)
Análise Semântica (verificar se as sequências de tokens possuem sentido)
Geração de código intermediário (transformar o código original em código intermediário para permitir otimizações)
Sintése. Otimização de código (aplicar otimizações ao código intermediário)
Sintése. Geração de código (transformar o código intermediário em código objeto)

As formas de implementação de um compilador, e os critérios usados na escolha de uma delas para uma determinada implementação.

Forma de implementação de 1 passo: Nessa forma, todas as funcionalidades são executadas em apenas um passo. Sua principal vantagem é a velocidade de compilação e tamanho de código. Sua principal desvantagem é não conseguir gerar código otimizado visto que para isso precisaria realizar loop (passar mais de uma vez) entre as estruturas.
Forma de imlpementação de muitos passos: Processa o código origem várias vezes. Cada passo possui sua entrada a saída da fase anterior. Sua principal vantagem é possibilitar um código menor e mais otimizado. Sua principal desvantagem é o tempo de compilação e o uso excessivo de memória.

A importância do uso de Código Intermediário na implementação de um compilador.

Torna mais simples a tradução da linguagem de alto nível para linguagem de máquina
Permite otimização do código
Uniformiza o código

Técnicas mais comuns de otimização de código

Eliminação de desvios para a próxima instrução
Retirada de comandos invariantes ao loop
Eliminação de código inalcançaveis
Alocação ótima de registradores

Definir formalmente: sentença, forma sentencial, gramática, linguagem, derivação e redução

Sentença: É uma sequência de símbolos não-terminais gerados a partir do símbolo inicial da gramática. G(Vn, Vt, P, S) ^ S+ => x, então x é uma setença da linguagem
Forma sentencial: É Uma sequência de símbolos terminais e não terminais produzidos a partir do símbolo inicial da gramática. G(Vn, Vt, P, S) ^ S -> Y -> X -> Z então Y, X, Z são formas sentenciais
Linguagem: É o conjunto de setenças que podem ser derivadas a partir do símbolo inicial.
Derivação: É o processo de construir/substituir strings (ou parte) por outro no sentido de forma sentencial -> sentença, ou seja, simbolo inicial -> sentença
Redução: É o processo inverso a derivação. Sentido Sentença -> Símbolo inicial

Questão 1: Diferencie e exemplifique linguagem vazia, finita e infinita

Linguagem vazia: É uma linguagem que não possui sentença, somente a sentença vazia.
Linguagem finita: É uma linguagem em que as sentenças podem ser enumerados.
Linguagem infinita: É uma linguagem com conjunto de sentenças infinitos.

Questão 2: Construa uma gramática G

a) G não seja recursiva mas possua uma GR equivalente G1 | L(G1) seja Regular, infinita e não contenha a sentença vazia

b) G seja recursiva, L(G) não seja Livre de Contexto e L(G) seja finita e contenha a sentença vazia

Questão 3:

a) União e a Concatenação de duas Linguagens (L1 e L2) de um mesmo tipo, resultam sempre em Linguagens desse mesmo tipo.

Existe casos em que a concatenação de linguagens podem resultar em uma linguagem de tipo maior mas certamente será pelo menos do mesmo tipo, nunca inferior. Veja o exemplo abaixo em que a concatenação de duas linguagens sensíveis ao contexto formam uma Regular.

L1 = { x / x E (a,b)* /\ #a's = #b's } e L2 = { x / x E (a,b)* /\ #a's != #b's }

b) Toda linguagem finita é uma L.L.C. ? é uma L. Regular ? Justifique sua resposta

Toda linguagem finita é uma linguagem regular visto que podemos criar um número finito de estados/produções a fim de antender todas as sentenças geradas a partir da gramática.

c) Proponha um algoritmo para verificar se a Linguagem gerada por uma dada GLC é vazia, finita ou infinita.

Questão 4:

Questão 5:

a) L(G) = { an bm cn | n,m ≥ 0 ∧ m ≠ n }

S -> X | B | J
X -> aXc | ac # somente ac
B -> bB | b # somente b
J -> aJKc | aKc
cK -> Kc
aK -> aL | a | aabc
bK -> bb | b
L -> bL | bb

Linguagem sensível ao contexto

b) L(G) = { x | x ∈ (a, b)* ∧ x não seja um palíndromo }

S -> aSb | aYa | bSa | bYb | ab | ba
Y -> aY | bY | a | b

Linguagem livre de contexto

c) L(G) = { x | x ∈ (a, b)* ∧ #“ab” = #“ba” }

S -> aB | bC | a | b
B -> aB | bC | b
C -> bC | aB | a

Gramática regular

d) L(G) = { an bm cp dq | n,m,p,q ≥ 0 ∧ n < p ∧ m > q }

S -> abbccd

senhorinha/lista_1.md