Exercício complementar II 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 II

(c) 2012 Leonel Figueiredo de Alencar

Questão 1: Defina os seguintes conjuntos por meio de um critério de pertinência satisfeito por todos e apenas os membros de cada conjunto:

a. A={Piauí, Rio Grande do Norte, Paraíba, Pernambuco}

b. B={azul, vermelho, branco}

Questão 2: Define enumerativamente o conjunto C={x | x é uma forma simples do artigo em português contemporâneo} (consultar, por exemplo, a Nova Gramática do Português Contemporâneo, de C. Cunha e L. Cintra).

A Questão 3 se refere ao conhecido poema “Quadrilha” de Carlos Drummond de Andrade:¹

João amava Teresa que amava Raimundo

que amava Maria que amava Joaquim que amava Lili

que não amava ninguém.

João foi para os Estados Unidos, Teresa para o convento,

Raimundo morreu de desastre, Maria ficou para tia,

Joaquim suicidou-se e Lili casou com J. Pinto Fernandes

que não tinha entrado na história.

Questão 3: Construa, a partir da gramática GD1 de (4), uma gramática GD2 tal que um parser baseado nessa gramática reconheça estruturas como a de (1) ou quaisquer outras construídas nos moldes de (2) e (3). Teste a a sua proposta de gramática no NLTK por meio do Donatus.

(1) João amava Teresa que amava Raimundo
(2) João amava Teresa que amava Raimundo que amava Maria que amava Joaquim
(3) João amava Teresa que amava Raimundo que amava Maria que amava Joaquim que amava Lili que amava Francisco que amava Joana

(4) Gramática GD1
S → NP VP
VP → V NP

NP → N

CP → C S

V → {amava}

N → {João, Teresa, Raimundo, Maria, Joaquim, Lili, Francisco, Joana}

C → {que}

Nas seguintes questões, marque verdadeiro (V) ou falso (F) para as alternativas.

Questão 4: Seja LD a língua gerada pela gramática GD2, proposta como resolução da Questão 3. Sobre LD é correto afirmar:

a. Trata-se de língua infinita.

b. LD é do tipo 0.

c. LD é do tipo 1.

d. LD é do tipo 2.

Questão 5: Sobre a Hierarquia de Chomsky, é correto afirmar:

a. Uma gramática do tipo 0 é capaz de gerar qualquer língua do tipo 1.

b. Uma gramática do tipo 0 é capaz de gerar qualquer língua do tipo 2.

c. Uma gramática do tipo 3 é capaz de gerar qualquer língua do tipo 2.

d. Uma gramática do tipo 1 é capaz de gerar qualquer língua do tipo 3.

Questão 6: Qual o tipo mais alto de gramática de Chomsky em que se enquadra a gramática GD1 do exemplo (4) da Questão 3?

a. Tipo 0.

b. Tipo 1.

c. Tipo 2.

d. Tipo 3.

Questão 7: Construa uma versão GD3 de GD2 capaz de analisar os versos abaixo do poema “Tinha uma pedra” de Drummond.² Teste a gramática no NLTK por meio do Donatus.

(5) no meio do caminho tinha uma pedra

(6) tinha uma pedra no meio do caminho

(7) tinha uma pedra

1 ANDRADE, Carlos Drummond de. Nova Reunião: 19 Livros de Poesia. Volume 1. Rio de Janeiro: José Olympio, 1983, p. 25.

2 ANDRADE, Carlos Drummond de. Nova Reunião: 19 Livros de Poesia. Volume 1. Rio de Janeiro: José Olympio, 1983, p. 15.

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/alencar-l.html.

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

Capa

Organizadores e autores do livro

Os Organizadores

Leonel Figueiredo de Alencar: é Professor Adjunto do Departamento de Letras Estrangeiras e do Programa de Pós-Graduação em Linguística da Universidade Federal do Ceará. Como bolsista da CAPES, doutorou-se em Linguística em 2003 pela Universidade de Constança, Alemanha. Antes disso, havia feito cursos em Freiburg e Göttingen, com bolsas do DAAD e do Instituto Goethe. No ensino e na pesquisa, tem se concentrado nos últimos anos, no plano teórico, em modelos não transformacionais da gramática gerativa e, no âmbito aplicado, na Lingüística Computacional e na Linguística de Corpus, com ênfase na utilização da linguagem de programação Python e de ferramentas de estados finitos. É autor de várias publicações, não só no Brasil, mas também no exterior, principalmente na Europa. É coordenador do CompLin – Computação e Linguagem Natural, listado no Diretório dos Grupos de Pesquisa no Brasil como grupo de pesquisa com certificação institucional. Homepage: http://complin.blogspot.com/

Gabriel de Ávila Othero: é formado em Letras Português/Inglês e Letras Português pela Universidade do Vale do Rio dos Sinos – UNISINOS; é especialista em Estruturas a Língua Portuguesa pela Universidade Luterana do Brasil - ULBRA; Mestre em Letras, área de Linguística Aplicada, e Doutor em Linguística Aplicada pela Pontifícia Universidade Católica do Rio Grande do Sul – PUCRS, tendo realizado estágio pós-doutoral na Universidade Federal do Rio Grande do Sul (UFRGS). Atualmente, é Professor Adjunto do Instituto de Letras e do Programa de Pós-Graduação em Linguística da Universidade Federal do Rio Grande do Sul. Ele é um dos criadores do parser Grammar Play. Tem experiência na área de sintaxe do português e é autor dos livros Lingüística Computacional: teoria & prática (São Paulo: Parábola, 2005, em co-autoria com Sérgio Menuzzi) e Teoria X-barra: descrição do português e aplicação computacional (São Paulo: Contexto, 2006). Além disso, é o editor-chefe da Revista Virtual de Estudos da Linguagem – ReVEL desde 2003. Homepage:  http://sites.google.com/site/gabrielothero/home

Os Autores

António Branco: é Professor na Universidade de Lisboa, onde dirige o NLX-Grupo de Fala e Linguagem Natural. É autor de várias dezenas de publicações na área da Ciência Cognitiva, com especial ênfase no processamento computacional da linguagem natural. É responsável pelo desenvolvimento da gramática computacional HPSG do português no projeto internacional DELPHIN, tendo organizado a conferência anual da HPSG em 2005 e participado em diversas comissões científicas de reuniões desta área. Homepage: http://www.di.fc.ul.pt/~ahb/

Christoph Gabriel: é Professor Livre-Docente de Linguística Espanhola e Francesa na Universidade de Hamburgo (Alemanha). Em 2000, ele terminou seu Doutorado em Linguística Francesa e Geral pela Universidade Técnica de Berlim (Alemanha), como bolsista do programa Nafög (bolsa de doutorado do Estado de Berlim). De 2000 a 2006, ele foi Professor Adjunto de Linguística Românica na Universidade de Osnabruck (Alemanha), onde recebeu o título de Livre-Docente. Seus principais interesses de pesquisa são teoria sintática (especialmente Minimalismo e sintaxe em Teoria da Otimidade) e a interface sintaxe-fonologia. Além do mais, suas pesquisas incluem trabalhos em entonação do espanhol, fonologia segmental do francês e estudos sincrônicos e diacrônicos sobre pronomes pessoais de línguas românicas. Ele é autor e co-autor de diversas publicações abordando diversos tópicos no campo da sintaxe e fonologia românicas, incluindo duas monografias e três livros-texto. Homepage: http://www1.uni-hamburg.de/romanistik/personal/w_gabr.html

Francisco Costa: é Investigador na Universidade de Lisboa, onde tem trabalhado activamente no desenvolvimento da gramática HPSG do português do projecto internacional DELPHIN. É especialista na sintaxe e semântica dos sintagmas nominais do Português, aos quais dedicou a sua investigação de doutorado. É autor de vários artigos sobre HPSG. Homepage: http://nlx-server.di.fc.ul.pt/~fcosta/

Karine Alves David: é formada em Letras pela Universidade Estadual do Ceará desde 1998. Especializou-se em Língua Portuguesa pela mesma Universidade em 2000 e, em fevereiro de 2007, recebeu o título de Mestre em Linguística, com louvor, pela Universidade Federal do Ceará. 

Marcello Modesto: é pesquisador e docente do departamento de Linguística da Universidade de São Paulo. Como bolsista do CNPq, ele recebeu o título de Ph.D. em Linguística pela University of Southern California no ano 2000. Atualmente, com apoio da FAPESP, desenvolve um projeto em tradução automática de línguas com poucos recursos computacionais em parceria com o grupo Avenue da Universidade Carnegie Mellon. Sua pesquisa em sintaxe gerativa tem lidado com argumentos nulos e a teoria do controle. Ele é autor de várias publicações, principalmente na Europa. Homepage: http://www.fflch.usp.br/dl/modesto/

Ronaldo Teixeira Martins: possui graduação em Letras pela Universidade Federal de Juiz de Fora (1994), mestrado em Linguística pela Universidade Estadual de Campinas (1997) e doutorado em Linguística pela Universidade Estadual de Campinas (2004). Atualmente é Coordenador do Curso de Letras e Professor Assistente da Universidade Presbiteriana Mackenzie, Professor Titular da Universidade do Vale do Sapucai, Sócio- Fundador da Cybernemics Language Solutions, Pesquisador-Associado da UNDL Foundation e Colaborador do NILC – Núcleo Interinstitucional de Lingüística Computacional da Universidade de São Paulo. Tem experiência na área de Linguística, com ênfase em Linguística Computacional, atuando principalmente nos seguintes temas: Tradução Automática, Revisão Gramatical e de Estilo Automática e Recuperação de Informação. Homepage: http://www.ronaldomartins.pro.br/

Agradecimentos, introdução, resumos dos capítulos etc.

A partir deste link, é possível baixar o material prefacial (sumário, introdução com resumo de cada capítulo etc.):


http://www.mercado-de-letras.com.br/livro-mway.php?codid=278

Como adquirir o livro

O livro pode ser adquirido a partir do site da Mercado de Letras:


http://www.mercado-de-letras.com.br/livro-mway.php?codid=278


ou pelo e-mail vendas@mercado-de-letras.com.br, com 20% de desconto.

Capítulos do livro

SUMÁRIO

 Introdução

Leonel Figueiredo de Alencar e Gabriel de Ávila Othero

1. Línguas formais, gramáticas e autômatos no processamento automático das palavras

Leonel Figueiredo de Alencar

2. Agrupamentos nominais no português brasileiro: uma análise formal e sua aplicação computacional

Karine Alves David e Gabriel de Ávila Othero

3. Parsing do português

Ronaldo Teixeira Martins  e Gabriel de Ávila Othero

4. O Programa Minimalista em sua primeira versão

Marcello Modesto

5. Pesquisas recentes em Minimalismo

Christoph Gabriel

6. HPSG: Arquitectura

Antônio Branco e Francisco Costa

7. Representação Sintáctica em HPSG

Antônio Branco e Francisco Costa

8. Representação do significado em HPSG

Antônio Branco e Francisco Costa