Lista1 FTC

Prévia do material em texto

uiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiit
h
h
h
h
h
h
h
h
h
h
h
h
h
h
FUNDAMENTOS TEÓRICOS DA
COMPUTAÇÃO
Departamento de Computação e Sistemas - DECSI - UFOP
Engenharia de Computação/ Sistemas de Informação
Prof. Roberto Gomes Ribeiro
h
h
h
h
h
h
h
h
h
h
h
h
h
h
viiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiw
Lista de exercícios 1 - Valor: 2 pontos
Questões extraídas e adaptadas do livro Introdução aos
Fundamentos da Computação (VIEIRA, N. J., 2023)
Questão 1 Seja a gramática ({A,B}, {0, 1}, R,A), em que R tem as três regras:
1. A −→ BB
2. B −→ 0B1|λ
Dê todas as derivações das seguintes palavras:
(a) λ
(b) 01
(c) 0101
(d) 0011
Qual linguagem é gerada?
Questão 2 Considere a gramática G constituída pela variável de partida P e pelas regras:
1. P −→ aAbc
2. A −→ aAbC
3. A −→ λ
4. Cb −→ bC
5. Cc −→ cc
Ainda, considere a gramática G′ constituída pela variável de partida P e pelas regras:
1. P −→ aAbD
2. A −→ aAbC
3. A −→ λ
4. Cb −→ bC
5. CD −→ Dc
6. D −→ c
Verifique se L(G) = L(G′). Justifique sua resposta.
Questão 3 Construa gramáticas para as seguintes linguagens:
(a) {w ∈ {a, b}∗ | o número de as em w é par};
(b) {anbn | n ∈NNN};
(c) {w ∈ {a, b}∗ | w = wR};
(d) {w ∈ {a, b}∗ | w = wR e w não contém símbolos consecutivos idênticos};
(e) {anbncndn | n ∈NNN}.
Questão 4 Para as gramáticas dos itens (b) e (c) do exercício anterior, determine o número de
passos necessários para gerar uma palavra de tamanho n.
Questão 5 Seja a gramática G = ({A,B}, {a, b}, R,A) em que R é constituído pelas quatro regras:
• A −→ aA|B
• B −→ bB|λ
Que linguagem é gerada por G?
Page 2