Exercícios -Linguagens e Gramáticas Resolvidos

Prévia do material em texto

1) Seja  = {a, b} um alfabeto. Determine o fecho transitivo reflexivo (*) e o 
fecho positivo (+) sobre este alfabeto. 
 
* = {, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb, ...} 
+ = * - {} = {a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb, 
...} 
 
2) Sabendo-se que o alfabeto de uma dada linguagem L é  = {0, 1}, e que 
L = { |   *  ||  3}, determine quais as sentenças desta linguagem. 
L = {, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, 111} 
3) Sabe-se que uma linguagem L possui as sentenças {abaa, aabbaaaa, 
aaabbbaaaaaa, aaaabbbbaaaaaaaa, ...}. Determine formalmente que 
linguagem é esta. 
L = { |   *   = anbna2n  n > 0} 
4) Desenvolva uma gramática que gere a linguagem correspondente aos 
identificadores da linguagem Pascal, isto é, palavras formadas por uma ou 
mais letras ou dígitos, as quais sempre se iniciam por uma letra. 
 
G1 = (VN, VT, P, S), onde: 
VN = {S, A, L, D} 
VT = {a, b, c, ..., z, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9} 
P = { S  LA 
A  LA | DA | 
L  a | b | c | ... | z 
D  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 
} 
Derive as cadeias: a, v6, ovo. 
S  LA  aA  a 
S  LA  vA  vDA  v6A  v6 
S  LA  ao  oLA  ovA  ovLA  ovoA  o
 
 
 
G2 = (VN, VT, P, S), onde: 
VN = {S, L, D} 
VT = {a, b, c, ..., z, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9} 
P = { S  SL | SD | L 
L  a | b | c | ... | z 
D  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 
} 
Derive as cadeias: a, v6, ovo. 
S  L  a 
S  SD  S6  L6  v6 
S  SL  So  SLo  Svo  Lvo  ovo 
 
Observe que L(G1) = L(G2); isto é, G1 e G2 são equivalentes. 
 
5) Considerando a linguagem anterior, construa uma gramática que gere a 
linguagem correspondente aos identificadores da linguagem Pascal, mas que 
possua no máximo tamanho de seis caracteres. 
 
G = (VN, VT, P, S), onde: 
VN = {S, A, B, C, D, E, F, L} 
VT = {a, b, c, ..., z, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9} 
P = { S  LA 
A  LB | DB |  
B  LC | DC |  
C  LE | DE |  
E  LF | DF |  
F  L | D | 
L  a | b | c | ... | z 
D  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 
} 
 
 
6) Desenvolva uma gramática que gere expressões aritméticas com parênteses 
balanceados, os operadores de multiplicação e/ou adição (representados por 
* e +, respectivamente) e um operando, representado por x. Por exemplo, as 
seguintes expressões devem ser válidas: x, x*(x + x), x + x * x, (((x))), etc.. 
 
G = (VN, VT, P, E), onde: 
VN = {E} 
VT = {+, -, *, /, (, ), x} 
P = {E  E + E | E – E | E * E | E / E | (E) | x} 
 
7) Desenvolva gramáticas que gerem as seguintes linguagens: 
 
a) L(G1) = {ancbm | n e m  0} 
Note que L(G1) = {c, ac, cb, acb, aac, aacb, aacbb, cbb, acbb, aacbb, ...} 
G1 = (VN, VT, P, S), onde: 
VN = {S, A, B} 
VT = {a, b, c} 
P = { S  AcB 
A  aA | 
B  bB | 
} 
 
S  AcB  cB  c 
S  AcB  aAcB  acB  ac 
S  AcB  cB  cbB  cb 
S  AcB  aAcB  acB  acbB  acb 
 
G2 = (VN, VT, P, S), onde: 
VN = {S, A} 
VT = {a, b, c} 
P = { S  aS | cA 
A  bA | 
} 
 
 
S  cA  c 
S  aS  acA  ac 
S  cA  cbA  cb 
S  aS  acA  acbA  acb 
 
Note que L(G1) = L(G2); isto é, G1 e G2 são equivalentes. 
b) L(G2) = {10n10n | n > 0} 
G = (VN, VT, P, S), onde: 
VN = {S, A} 
VT = {0, 1} 
P = { S  1A 
A  0A0 | 010 
} 
Gere as cadeias 1010, 100100 e 10001000: 
S  1A  1010 
S  1A  10A0  100100 
S  1A  10A0  100A00  10001000 
 
c) L(G3) = {(ab)ncam | n > 0, m  0} 
 
G1 = (VN, VT, P, S), onde: 
VN = {S, T} 
VT = {a, b, c} 
P = { S  abS | abcT 
T  aT | 
} 
 
Outro exemplo seria: 
 
G2 = (VN, VT, P, S), onde: 
VN = {S, A, B} 
VT = {a, b, c} 
 
 
P = { S  AcB 
A  abA | ab 
B  aB | 
} 
d) L(G4) = {10n110m | n  0, m  2} 
G = (VN, VT, P, S), onde: 
VN = {S, A, B} 
VT = {0, 1} 
P = { S  1A11B 
A  0A | 
B  aB | aa 
} 
 
e) L(G5) = {  * |  = {a, b, c, d, e } e  inicia-se com a e termina com e} 
f) L(G6) = {  * |  = {a, b, c} e  inicia-se com a e tem comprimento 
par ou inicia-se com b e tem comprimento ímpar} 
g) L(G7) = {  * |  = {a, b} e  possui a nas posições pares e b nas 
posições ímpares} 
h) L(G8) = {  * |  = {0, 1, 2, ... , 9} e  inicia-se com 0 e a soma de 
todos os seus dígitos é par ou inicia-se com 1 e a soma de todos os seus 
dígitos é ímpar} 
i) L(G9) = {   {0, 1} |  contém 0101 como subcadeia } 
j) L(G10) = {   {0, 1} |  não possui 110 como subcadeia } 
k) L(G11) = { r |  é uma sentença de {a, b}*} 
l) L(G12) = { aib jck | i = j ou j = k e i, j, k  0 } 
 
8) Sejam as gramáticas definidas a seguir. Determine qual é a linguagem 
gerada por cada uma delas: 
 
a) G1 = (VN, VT, P, S), onde: 
VN = {S} 
VT = {a, b, c} 
P = {S  aSb | c} 
 
 
b) G2 = (VN, VT, P, S), onde: 
VN = {S, A, B} 
VT = {0, 1} 
P = {S  0 | 0A, 
A  1B, 
B  0 | 0A} 
 
c) G3 = (VN, VT, P, S), onde: 
VN = {S} 
VT = {a, b, c} 
P = {S  aSa | bSb | cSc | a | b | c | }