Abordagens computacionais da teoria da gramática: Exercício complementar I do capítulo 1

ALENCAR, L. F. de . Línguas formais, gramáticas e autômatos no processamento automático das palavras. In: ALENCAR, L. F. de; OTHERO, G. A.. (Org.). Abordagens computacionais da teoria da gramática. 1 ed. Campinas: Mercado de Letras, 2012, p. 13-75.

Exercícios complementares sobre o capítulo 1 de Alencar e Othero (2012)

Exercício I

Nos exercícios de 1 a 3, marque verdadeiro (V) ou falso (F) para as alternativas.

Questão 1: Que tipo de objeto matemático é uma língua formal?

a. Equação.

b. Vetor.

c. Matriz.

d. Conjunto.

e. Árvore.

Questão 2: Sobre a língua formal L₁ (p. 20) é correto afirmar:

a. Trata-se de língua finita.

b. A palavra romã pertence a L₁.

c. A palavra mamão pertence a L₁.

d. O número de elementos de L₁é 7.

e. O número de elementos de L₁é 10.

Questão 3: Sobre a língua formal L3 (p. 20) é correto afirmar:

a. Está definida enumerativamente.

b. Se A={x | x é um sintagma nominal do português}, então L₃=A.

c. Se A={u,m,o,s}, então A é um subconjunto do alfabeto de L₃.

d. A cardinalidade do alfabeto de L₃é 9.

e. Se B={aquele jogador de xadrez}, então B está contido em L₃.

f. Se B={aquela jogadora}, então B pertence a L₃.

Questão 4: Seja a versão corrigida de L₂=aⁿ b^m, com n ≥ 0 e m ≥ 0 (v. errata). Construa uma gramática dessa língua nos moldes do exemplo (5), p. 26.

Questão 5: Nos moldes do exemplo (4), p. 25, utilizando a gramática da Questão 4, faça a derivação da cadeia abb.

Questão 6: Apresente a árvore do exemplo da Questão 5.

Questão 7: Seja L₅=aⁿ bⁿ, com n ≥ 0. Construa uma gramática dessa língua nos moldes do exemplo (5), p. 26. Com base nessa gramática, elabore a árvore da cadeia aabb.

Questão 8: Seja a gramática G=(

{A,C,S},

{a,b,c},

{S -> A S A,

S -> b C,

A -> a,

C -> b C,

C -> c},

), extraída do livro Generative Syntax, de Ursula Klenk (Tübingen: Narr, 2003, p. 38). Pressupondo que a língua L gerada por G é tal que L=a^x b^y c^z a^w, estabeleça os valores que podem ser assumidos por x, y, z e w.