Lista de Exercícios no 1



Baixar 40.8 Kb.
Encontro07.10.2019
Tamanho40.8 Kb.

Universidade Federal de Santa Catarina / Centro Tecnológico

Departamento de Informática e de Estatística

INE5421 - Linguagens Formais e Compiladores
Lista de Exercícios no 1

0 – Você deve saber ... (não precisa entregar a resposta desta questão)

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

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

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

d) O que é e qual a importância (teórica e prática) da Teoria das Linguagens Formais;

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

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

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

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

i) As formas de representação formal de Linguagens;

j) A definição formal de sentença, forma sentencial, gramática, linguagem, derivação e redução.

k) Mostrar que GSC são recursivas.
1 - Construa uma gramática G, do maior tipo possível |


  1. L(G) = { ai bj ck | i,j,k  0  j seja par  i + k seja ímpar }

  2. L(G) = { ai bj ck | i,j,k  0  j = i + k ou i ≠ k }

  3. L(G) = { an (b, c)* dm | n,m  0  n > #b’s + #c’s > m}

2 – a) Mostre através de exemplos que a União e a Concatenação de duas Linguagens (L1 e L2) de um mesmo tipo, resultam sempre em Linguagens do mesmo tipo que L1 e L2.

b) Mostre que toda Linguagem finita é uma Linguagem Regular.

c) Mostre, genericamente e através de exemplos, que toda linguagem gerada por uma GLC com produções da forma A  x B | x (onde x  VT+), também pode ser gerada por uma G.R..


3 – Construa, se possível, Gramáticas G1, G2 e G3 | G1 seja GR, G2 seja GLC, G3 seja GSC  L(G3)  L(G2)  L(G1)  L(G3) não seja LC  L(G2) não seja Regular.
4 - Construa, se possível, Gramáticas G1 e G2 |

a) LG1)  L(G2) = VT*

b) LG1) ∩ L(G2) = φ
5 - Construa uma Gramática Regular G |


  1. L(G) = { x | x  ( 0,1)*  x não possua os substrings “000” e “111”}

  2. L(G) = { x | x  ( a, b)*cn  n + #a’s é ímpar  x não possua b’s consecutivos}

  3. L(G) = { x | x  ( a, b)*  | x | seja par  x não possua b’s consecutivos }

  4. L(G) = { x | x  ( a, b, c)*  #a’s + #b’s não seja divisível por 3}

6 - Construa uma Gramática Livre de Contexto (GLC) G |

  1. L(G) = { an bm (c,d)*| 0  n  m  #c’s = 2 * #d’s}

  2. L(G) = { an bm ck dl | n,m,k,p  0, n + k = m + l }

  3. L(G) = { x | x  ( a, b)* (c, d)*  #a’s + #b’s ≠ #c’s + #d’s}

  4. L(G) = { x | x  ( a, b)*  #a’s ≠ #b’s }

7 – Construa uma GLC que especifique:

a) a sintaxe da declaração e da chamada de procedimentos (métodos) de uma linguagem de programação qualquer. OBS. Para simplificar, considere apenas parâmetros de tipos simples pré-definidos e represente qualquer identificados por “id”.

b) a sintaxe de expressões aritméticas envolvendo variáveis (“id”), constantes (“c”), parênteses (“(“ e “)”) e os operadores “+”, “-“ , “/” e “*”.

c) a sintaxe de uma seqüência de estruturas de controle if-then-else e while-do (possivelmente aninhadas).

8 - Construa uma GSC (Gramática Sensível ao Contexto) G |



  1. L(G) = { an bm cp dq | n,m,p,q  0  n = p  q = m }

  2. L(G) = { x | x  an (b,c)* dm  n + m > #b’s  #c’s = #b’s}

  3. L(G) = { an bn cm | n  0, m  0  n  m }

  4. L(G) = { x | x  ( a, b, c)*  #a’s  #b’s  #c’s}

9 - Seja G a seguinte gramática:

S  a S | S C | c S A | b

A C  C A C A  A C

b C  b c b A  b a

a A  a a a C  a c

c A  c a c C  c c

Pede-se:


  1. Verifique se x = acba e y = abca pertencem a L(G), usando o algoritmo apropriado;

  2. Determine L(G);

  3. Construa, se possível, uma GLC G1 | L(G1) = L(G)

  4. Construa G2 | G2 seja do mesmo tipo de G  L(G2) = L(G) {  }

10 - Determine L(G) onde G é dada por:


a ) S  S a S | S b S | c (* L(G) é também uma LR? *)
b ) S  0 S 1 | 1 S 0 | 0 1 | 1 0 | 0 | 1
c ) S  a S | b A | b | a C | b D

A  b S | a A | a | b C | a D

C  d C | c D | c

D  d D | c C | d

d ) S  a A L | b B L (* L(G) é também uma LR? *)

A  L A L | a

B  L B L | b

L  a B | b A | a


e ) S  AD (* L(G) é também uma LLC? *)

A  a A C | a A | a

D  B D d | D d | d

C B  B C

B C  C B

B  b


C  c
f ) S  a A | b A | a | b

A  a B | b B

B  a C | b C

C  a D | b D

D  a E | b E | a | b

E  a S | b S


g ) S  C D (* L(G) é também uma LSC? *)

C  a C A | b C B

A D  a D

B D  b D

A a  a A

A b  b A

B a  a B

B b  b B



C  

D  




©aneste.org 2017
enviar mensagem

    Página principal