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  


Compartilhe com seus amigos:


©aneste.org 2020
enviar mensagem

    Página principal
Universidade federal
Prefeitura municipal
santa catarina
universidade federal
terapia intensiva
Excelentíssimo senhor
minas gerais
união acórdãos
Universidade estadual
prefeitura municipal
pregão presencial
reunião ordinária
educaçÃo universidade
público federal
outras providências
ensino superior
ensino fundamental
federal rural
Palavras chave
Colégio pedro
ministério público
senhor doutor
Dispõe sobre
Serviço público
Ministério público
língua portuguesa
Relatório técnico
conselho nacional
técnico científico
Concurso público
educaçÃo física
pregão eletrônico
consentimento informado
recursos humanos
ensino médio
concurso público
Curriculum vitae
Atividade física
sujeito passivo
ciências biológicas
científico período
Sociedade brasileira
desenvolvimento rural
catarina centro
física adaptada
Conselho nacional
espírito santo
direitos humanos
Memorial descritivo
conselho municipal
campina grande