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.