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

(c) 2012 Leonel Figueiredo de Alencar

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},

S

), 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. 

Exercícios sobre o capítulo 1 de Alencar e Othero (2012) by Leonel F. de Alencar is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.
Based on a work at http://teoria-da-gramatica.blogspot.com.br/2012/08/exercicio-complementar-i-do-capitulo-1.html.

Programa em Prolog jumps.pl

/* Capítulo 1, p. 61.
Programa jumps.pl, adaptado do programa recognize1.pl,
de autoria de Patrick Blackburn e Kristina Striegnitz,
disponível na seguinte URL:
http://cs.union.edu/~striegnk/courses/nlp-with-prolog/html/recognize1.pl 
*/

:- multifile network/1.
:- multifile arc/4.
:- multifile arc/3.
:- multifile final/2.
:- multifile initial/2.
:- discontiguous network/1.
:- discontiguous arc/4.
:- discontiguous arc/3.
:- discontiguous final/2.
:- discontiguous initial/2.


recognize1(Network,Node,[]) :-
    final(Network,Node).
recognize1(Network,Node1,String) :-
    arc(Network,Node1,Node2,Label1),
   atom_codes(Label2,Label1),
    traverse1(Network,Label2,String,NewString),
    recognize1(Network,Node2,NewString).

recognize1(Network,Node1,String) :-
    arc(Network,Node1,Node2),
    traverse1(Network,String,NewString),
    recognize1(Network,Node2,NewString).

traverse1(Network, String, String):-
network(Network).

traverse1(Network,Label,[Label|Symbols],Symbols):- 
network(Network).

test1(Network,Symbols) :-
    initial(Network,Node),
    recognize1(Network,Node,Symbols).

generate1(Network,X) :-
   test1(Network,X).

testa(Rede,Palavra):- atom_chars(Palavra,Lista),test1(Rede,Lista).

gera(Rede,Palavra) :- generate1(Rede,Lista),atom_chars(Palavra,Lista).

gera2(N):- gera(N,Palavra),write(Palavra),nl,fail.

Programa recognize2.pl

O programa em Prolog recognize2.pl, de Blackburn e Striegnitz, está disponível no seguinte endereço:

http://cs.union.edu/~striegnk/courses/nlp-with-prolog/html/recognize2.pl

Programa em Prolog fsm03.pl

/* Capítulo 1, exemplo (35), pp. 48-49.
Programa fsm03.pl, adaptado do programa recognize1.pl,
de autoria de Patrick Blackburn e Kristina Striegnitz,
disponível na seguinte URL:
http://cs.union.edu/~striegnk/courses/nlp-with-prolog/html/recognize1.pl 
*/

:- multifile network/1.
:- multifile arc/4.
:- multifile final/2.
:- multifile initial/1.
:- discontiguous network/1.
:- discontiguous arc/4.
:- discontiguous final/2.
:- discontiguous initial/1.


initial(0).

recognize1(Network,Node,[]) :-
    final(Network,Node).
recognize1(Network,Node1,String) :-
    arc(Network,Node1,Node2,Label1),
   atom_codes(Label2,Label1),
    traverse1(Network,Label2,String,NewString),
    recognize1(Network,Node2,NewString).

traverse1(Network,Label,[Label|Symbols],Symbols):-
network(Network).

test1(Network,Symbols) :-
    initial(Node),
    recognize1(Network,Node,Symbols).

generate1(Network,X) :-
   test1(Network,X).

testa(Rede,Palavra):- atom_chars(Palavra,Lista),test1(Rede,Lista).

gera(Rede,Palavra) :- generate1(Rede,Lista),atom_chars(Palavra,Lista).

gera2(N):- gera(N,Palavra),write(Palavra),nl,fail.

Programa em Prolog fsm05.pl

/* Capítulo 1, pp. 57 e 58.
Programa fsm05.pl, adaptado do programa recognize1.pl,
de autoria de Patrick Blackburn e Kristina Striegnitz,
disponível na seguinte URL:
http://cs.union.edu/~striegnk/courses/nlp-with-prolog/html/recognize1.pl 
*/


:- multifile network/1.
:- multifile arc/4.
:- multifile final/2.
:- multifile initial/2.
:- discontiguous network/1.
:- discontiguous arc/4.
:- discontiguous final/2.
:- discontiguous initial/2.


recognize1(Network,Node,[]) :-
    final(Network,Node).
recognize1(Network,Node1,String) :-
    arc(Network,Node1,Node2,Label1),
   atom_codes(Label2,Label1),
    traverse1(Network,Label2,String,NewString),
    recognize1(Network,Node2,NewString).

traverse1(Network,Label,[Label|Symbols],Symbols):- 
network(Network).

test1(Network,Symbols) :-
    initial(Network,Node),
    recognize1(Network,Node,Symbols).

generate1(Network,X) :-
   test1(Network,X).

testa(Rede,Palavra):- atom_chars(Palavra,Lista),test1(Rede,Lista).

gera(Rede,Palavra) :- generate1(Rede,Lista),atom_chars(Palavra,Lista).

gera2(N):- gera(N,Palavra),write(Palavra),nl,fail.

Errata do capítulo 1

ALENCAR, Leonel F. de; OTHERO, Gabriel de Ávila (Orgs.). Abordagens computacionais da teoria da gramática. Campinas: Mercado de Letras, 2012. 304 p.

Errata do capítulo 1 ”Línguas formais, gramáticas e autômatos no processamento automático das palavras”, de Leonel Figueiredo de Alencar

p. 20 e p. 24: a definição correta de L₂ é aⁿ b^m, com n ≥ 0 e m ≥ 0 (agradeço a Davis Macedo Vasconcelos a correção deste erro)

p. 34: em vez de “A expressões regulares” leia-se “As expressões regulares”

p. 50: Como a Figura 6 não está muito nítida no livro, apresentamos abaixo duas versões produzidas por meio das FSA Utilities.

p. 54, ex. 5a): incluir a cláusula

final(3).

Com isso, a diretiva

?- generate2(X).

passa a gerar também as formas do singular.

p. 69: Abaixo, reprodução mais nítida da Figura 8.

Lançamento em Porto Alegre e Fortaleza

Depois do lançamento do livro no Instituto de Letras da UFRGS, no dia 14 de junho, ele será lançado em Fortaleza, também com a participação dos dois organizadores, no dia 20 de setembro. Mais informações aqui:

http://www.gramaticaufc.blogspot.com.br/p/lancamento-de-livros.html