Departamento de Ciência da Computação ICEx/UFMG Teoria de Linguagens 2o semestre de 2018 Professor: Newton José Vieira Primeira Prova 18/9/2018...

Departamento de Ciência da Computação ICEx/UFMG Teoria de Linguagens 2o semestre de 2018 Professor: Newton José Vieira Primeira Prova 18/9/2018 Valor: 24 pontos 1. Descreva, em português, as seguintes linguagens sobre o alfabeto {0, 1}: a) {0, 1}∗{1}{0, 1}; b) {0}{0, 1}∗ ∪ {0, 1}∗{1}; c) {01, 1}∗; d) {0}∗{1}({0} ∪ {1}{0}∗{1})∗. Solução: a) Conjunto das palavras cujo penúltimo śımbolo é 1. b) Conjunto das palavras que começam com 0 ou terminam com 1. c) Conjunto das palavras em que todo 0 (caso haja algum) é seguido de 1. d) Conjunto das palavras com um número ı́mpar de 1s. 2. Construa gramáticas para as seguintes linguagens: a) {0}{11}∗{0}; b) {w ∈ {a, b}∗ | o número de as em w é par}; c) {anbk |n > k}; d) {xxR |x ∈ {a, b}∗}. Solução: a) P → 0X0 X → 11X |λ b) P → aI | bP |λ I → aP | bI c) X → aX | aXb | a d) X → aXa | bXb |λ 3. Construa AFDs que reconheçam: a) {0, 1}∗ − {0, 01, 10}; b) {w ∈ {0, 1}∗ |w tem número par de 0s e um único 1}. Solução: a) 0 1 1 0 0 0,1 1 0,1 b) 0 1 0 1 00 4. Sejam: • L1 = {0, 1}∗{1}{0, 1}∗; • L2 = {w ∈ {0, 1}∗ |w contém número par de 0s}. Construa AFDs que reconheçam: a) L1. b) L2. c) L1 − L2. Para isto, faça o produto dos autômatos que reconhecem L1 e L2. Solução: (a) A B 1 0 0,1 (b) 1 2 1 0 1 0 1 0 (c) A1 B1 A2 B2 0 1 0 1 1 0 1 0 5. Seja o AFN com o diagrama de estados: 1 2 3 4 5 0 1 0,1 1 0,1 0 0 Obtenha um AFD equivalente utilizando o método de construção de subconjuntos. Solução: 15 24 3 2 34 0 1 1 0 1 0 0 1 0 1 6. Seja o AFNλ: 1 2 3 0 1 1 1 0 4 5 0 1 0 λ Obtenha um AFN equivalente usando a técnica para eliminação de transições λ. Solução: 1 2 3 0 1 1 1 0 4 5 0 1 01 1 1 Para e = 1, 2, 3: δ′(e, 1) = fλ(δ(e, 1)) = fλ({3}) = {3, 4}.
1. Descreva, em português, as seguintes linguagens sobre o alfabeto {0, 1}: a) {0, 1}∗{1}{0, 1}; b) {0}{0, 1}∗ ∪ {0, 1}∗{1}; c) {01, 1}∗; d) {0}∗{1}({0} ∪ {1}{0}∗{1})∗.
2. Construa gramáticas para as seguintes linguagens: a) {0}{11}∗{0}; b) {w ∈ {a, b}∗ | o número de as em w é par}; c) {anbk |n > k}; d) {xxR |x ∈ {a, b}∗}.
3. Construa AFDs que reconheçam: a) {0, 1}∗ − {0, 01, 10}; b) {w ∈ {0, 1}∗ |w tem número par de 0s e um único 1}.
4. Sejam: • L1 = {0, 1}∗{1}{0, 1}∗; • L2 = {w ∈ {0, 1}∗ |w contém número par de 0s}. Construa AFDs que reconheçam: a) L1. b) L2. c) L1 − L2. Para isto, faça o produto dos autômatos que reconhecem L1 e L2.
5. Seja o AFN com o diagrama de estados: 1 2 3 4 5 0 1 0,1 1 0,1 0 0 Obtenha um AFD equivalente utilizando o método de construção de subconjuntos.
6. Seja o AFNλ: 1 2 3 0 1 1 1 0 4 5 0 1 0 λ Obtenha um AFN equivalente usando a técnica para eliminação de transições λ.