Exercícios de Linguagens Formais e Autômatos
Nome: _________________________________________________________________ RA: __________________
Questão 1
Apresente gramáticas que representem as
seguintes linguagens definidas de maneira
informal:
Questão 3
Obtenha gramáticas que representem as
seguintes linguagens definidas de maneira
informal:
a) Conjunto de todas as cadeias sobre o
alfabeto {a,b,c} tais que elas contenham
apenas 3 símbolos “a”, todos eles
consecutivos. Exemplos: bcaaa, caaabbcc,
aaa, caaab, ... a) Conjunto de todas as cadeias sobre o
alfabeto {a,b,c} tais que elas contenham
qualquer número de símbolos b e apenas 2
símbolos a e b.
b) Conjunto de todas as cadeias sobre o
alfabeto {a,b,c} tais que elas contenham
apenas 2 símbolos “c”, não consecutivos.
Exemplos: bcaca, cacab, aca, cabab,
baba, ... Questão 2
Para cada uma das regras de produção da
gramática definida sobre o alfabeto {a,b,c},
vocabulário { S, T, U, a, b, c } e com símbolo
não terminal raiz S apresentadas a seguir,
selecione as cadeias pertencentes às
respectivas linguagens:
I. S → a | b | cT
T → Sc | cU U → c
cac, cbc, ccac, ccc, cccacc, ca,
cac, cacc, cbca, cbcc, ccccc II. S → c | aU | Ub
U → Tc | a T → bS
cc, aa, bccb, ccc, abcc, c, baacb,
bacc, abaac, abaaac, abbccbc b) Conjunto de todas as cadeias sobre o
alfabeto {a,b,c} tais que elas comecem com
o símbolo a e termine com b ou c.
c) Conjunto de todas as cadeias sobre o
alfabeto {a,b,c} tais que elas comecem com
1 ou 2 símbolos a e termine com 1 ou 2
símbolos c.