Autómatos finitos determinísticos

1. Considere o alfabeto Σ = {0,1}. Para cada um dos pontos seguintes, represente a linguagem dada usando:
1. uma expressão regular;
2. um autómato finito não determinístico;
3. um autómato finito determinístico;
4. uma gramática regular (linear à direita ou à esquerda).
 
1. L(A) = {u ∈ Σ^*: u é um número binário múltiplo de 4}
2. L(A) = {u ∈ Σ^*: 10 é prefixo de u}
3. L(A) = {u ∈ Σ^*: 111 não é factor de u}
4. L(A) = {u ∈ Σ^*: u é um número binário que ou não é par ou é múltiplo de 8}
5. L(A) = {u ∈ Σ^*: u tem um número par de 1's}
6. L(A) = {u ∈ Σ^*: u é vazia ou tem dígitos todos iguais, sendo de comprimento par as sequências de 0's, e ímpar as sequências de 1's}
7. L(A) = {u ∈ Σ^*: u é múltiplo de 4 mas não de 8}
8. L(A) = {u ∈ Σ^*: u é múltiplo de 8 mas não de 4}
9. L(A) = {u ∈ Σ^*: u tem comprimento 3}
10. L(A) = {u ∈ Σ^*: u tem no máximo comprimento 3 e é uma capicua}
 
2. Mostre para o alfabeto Σ = {A, B, C, ..., Z, a, b, c, ..., z}, que as seguintes linguagens são regulares:
1. L(A) = {u ∈ Σ^*: u não tem sempre pelo menos dois a's juntos}
2. L(A) = {u ∈ Σ^*: u começa por um carácter minúsculo e tem no máximo duas maiúsculas}
3. L(A) = {u ∈ Σ^*: u tem comprimento inferior a 4}
4. L(A) = {u ∈ Σ^*: u começa por uma maiúscula}
5. L(A) = {u ∈ Σ^*: u tem um número par de maiúsculas, um número ímpar de minúsculas e tem comprimento múltiplo de 4}
 
3. Mostre para o alfabeto Σ = {0,1,2,3,4,5,6,7,8,9}, que as seguintes linguagens são regulares:
1. L(A) = {u ∈ Σ^*: u é uma sequência numérica crescente}
2. L(A) = {u ∈ Σ^*: u começa e termina no mesmo dígito}
3. L(A) = {u ∈ Σ^*: u é múltiplo de 5}
4. L(A) = {u ∈ Σ^*: u é um número ímpar}
5. L(A) = {u ∈ Σ^*: u é um inteiro maior ou igual a 1000}

Implementação de analisadores léxicos

1. Implemente em lex/flex um analisador léxico que separe a entrada em tokens, escrevendo no ecrã os nomes dos mesmos. Os tokens possíveis são:
   inteiros: qualquer sequência de um ou mais dígitos, podendo ser antecedidos do sinal '+' ou '-';
   reais: qualquer sequência composta pela parte inteira, com um ou mais dígitos , seguido do carácter '.', podendo ter opcionalmente uma parte fraccionária e uma parte exponencial; a parte fraccionária é composta por um ou mais caracteres; a parte exponencial é composta pelo carácter 'E' seguido por um sinal opcional '+' ou '-' e de uma sequência de um ou mais dígitos;
   identificadores: uma letra seguida de zero ou mais letras ou dígitos;
   operadores relacionais: <,<=,>=,>,= =, !=.
   Os espaços em branco são ignorados. Todos os outros caracteres originam uma mensagem de erro.

Implementação de analisadores sintácticos

1. Implemente o analisador sintáctico para reconhecimento duma expressão lógica, utilizando um parser descendente predictivo. A gramática é a seguinte:
   E → E or E | E xor E | E and E | not E | ( E ) | ID | INT | REAL
   
   onde ID é um identificador, INT um número inteiro e REAL um número real.
2. Implemente o analisador sintáctico anterior usando a ferramenta yacc(ou bison).

Geração de código

1. Considere a seguinte gramática que descreve as expressões aritméticas habituais:
   E → E + E | E - E | E * E | E / E | - E | + E | ( E ) | INT | ID
   Considerando as precedências habituais entre operadores, implemente um compilador que traduza estas expressões para a notação posfixa.