Linguagens Formais e Compiladores Avaliação Processual 01

Prévia do material em texto

Linguagens Formais e Compiladores 
Prof. Matheus Brunoro Dilem 
 
Atividade Processual 1º Bimestre – 2025/2 
 
Questão 01) Considerando a Gramática abaixo capaz de gerar o conjunto dos números naturais: 
 
G = (Vn, Vt, P, S), onde: 
 Vn = { S, D } 
 Vt = { 0, 1, 2, ..., 9 } 
 P = { S→D, S → DS, D → 0 | 1 | 2 | ... | 9 } 
Modifique a gramática de tal forma a não permitir a geração de sentenças com zeros à esquerda. 
 
 
Questão 02) Desenvolva uma gramática G = (Vn, Vt, P, S) que gere a seguinte linguagem: 
 
L = { anbncn | n ≥ 0 } 
 
 
Questão 03) Desenvolva gramáticas regulares que gerem as linguagens sobre Σ = {a, b} 
 
a) { w | w não possui aba como subpalavra } Ex: ε, a, b, aa, bbb, ... 
b) { w | qualquer par de a antecede qualquer par de b } Ex: ε, a, aabb, baaabb, ... 
c) { w | w tem no máximo um par de a como subpalavra e no máximo um par de b como 
subpalavra } Ex: ε, a, b, aa, bb, abaa, bababb, ... 
 
 
Questão 04) Desenvolva autômatos finitos determinísticos que reconheçam as seguintes 
linguagens sobre o alfabeto Σ = {a, b} 
 
a) { w | o sufixo de w é aa } Ex: aa, baa, abbaaa, ... 
b) { w | w possui aa como subpalavra } Ex: aa, aab, aaa, baab, ... 
c) { w | w possui número ímpar de a e número ímpar de b } Ex: ab, ba, aabbab, babaab, .. 
d) { w | w possui número par de a e número ímpar de b ou w possui número ímpar de a e 
número par de b } Ex: abb, bab, baa, aabbb, ... 
 
 
Questão 05) Desenvolva autômatos finitos não determinísticos que reconheçam as seguintes 
linguagens sobre o alfabeto Σ = {a, b} 
 
a) Qualquer ocorrência de a é imediatamente sucedida por b. Ex: bbbabab, abab, ... 
b) Qualquer ocorrência de a é imediatamente antecedida e imediatamente sucedida por b. 
Ex: bab, bbbbabab, ... 
 
 
 
 
 
 
 
 
Questão 06) Quais das seguintes palavras são aceitas pelo autômato finito não determinístico 
abaixo, considerando o alfabeto Σ = {a, b} e F = {q2}. Demonstre. 
 
a) ε? 
b) aa? 
c) bb? 
d) aba? 
e) bbaaba? 
 
 
Questão 07) Quais das seguintes palavras são aceitas pelo autômato finito não determinístico 
abaixo, considerando o alfabeto Σ = {a, b} e F = {q0, q2, q3}. Demonstre. 
 
a) ε? 
b) bb? 
c) bab? 
d) bbbaaa? 
e) bbbbbbababababa? 
 
 
Questão 08) Transforme os A.F.N.D. das questões 6 e 7 em A.F.D. 
 
 
Questão 09) Descreva em palavras as linguagens geradas pelas seguintes expressões regulares: 
 
a) (a | b | c)*(a | b | c) 
b) (aa | b)*(a | bb) 
c) (b | ab)*( ε | a) 
d) c*(a | b)(a | b | c)* 
e) ((b | c)* | a(b | c)*a)* 
 
 
Questão 10) Desenvolva expressões regulares que gerem as linguagens sobre Σ = {a, b} 
 
a) { w | w não possui aba como subpalavra } 
b) { w | qualquer par de a antecede qualquer par de b } 
c) { w | w tem no máximo um par de a como subpalavra e no máximo um par de b como 
subpalavra }