Lista 1 - Alfabetos linguagens e Gramáticas

Prévia do material em texto

UFRPE 
Introdução a Linguagens de Programação 
Fonte: UCPEL/ESIN/BCC/BSI (Prof. Luiz A M Palazzo) 
 
Lista de Exercícios Número 1 
 
 
Modelagem e Representação 
1. Qual o papel das linguagens formais na ciência em geral e na 
computação em particular? Qual a importância de seu estudo? Pesquise 
e descreva aplicações da Teoria das Linguagens. 
 
Alfabetos Palavras e Linguagens 
 
2. Sejam X={a, b} e Y={0, 1} alfabetos. Represente as 5 palavras mais 
curtas das seguintes linguagens: (a) X*, (b) Y+, (c) (X∪Y)* 
3. Dada a palavra abaab, represente (a) seus prefixos, (b) seus sufixos, (c) 
suas subpalavras. 
4. Represente por extensão a linguagem L={w | w ∈ {a, b}* e |w| ≤ 2} . 
5. Sejam v=aa, w=b e t=ab palavras sobre o alfabeto Σ={a, b}. 
Representar os resultados das seguintes expressões: (a) v(wt), (b) 
(vw)t, (c) vw3t2, (d) (vw)2ε6t0. Qual o tamanho da palavra resultante 
em cada caso? 
 
Gramáticas 
 
6. Desenvolver gramáticas para gerar as seguintes linguagens sobre o 
alfabeto Σ={a,b}: 
 
a) A linguagem das palavras que começam por a e terminam por b. 
 
b) A linguagem das palavras que tem bb como sufixo. 
 
c) A linguagem das palavras de tamanho maior ou igual a 3 que 
terminam em ba. 
 
d) A linguagem das palavras w tal que o tamanho de |w| é par. 
 
7. Desenvolver uma gramática que gere expressões aritméticas com 
parênteses balanceados, dois operadores (+ e -) e dois operandos x e y. 
 
8. Desenvolver uma gramática que gere os identificadores da linguagem 
Pascal, começando sempre com uma letra, com no máximo 6 caracteres, 
entre letras e dígitos. 
 
9. Desenvolver uma gramática que gere a seguinte linguagem sobre o 
alfabeto Σ = {a, b, c}: L = {w | w = anbncn, n ≥ 0}.