Defining Natural Language Grammars in GPSG
This paper is a formal analysis of whether generalized phrase structure grammar's (GPSG) weak context-free generative power will allow it to achieve three of its central goals: (1) to characterize all and only the natural language grammars, (2) to algorithmically determine membership and...
| Main Author: | |
|---|---|
| Language: | en_US |
| Published: |
2004
|
| Online Access: | http://hdl.handle.net/1721.1/6447 |
| _version_ | 1811084569883967488 |
|---|---|
| author | Ristad, Eric Sven |
| author_facet | Ristad, Eric Sven |
| author_sort | Ristad, Eric Sven |
| collection | MIT |
| description | This paper is a formal analysis of whether generalized phrase structure grammar's (GPSG) weak context-free generative power will allow it to achieve three of its central goals: (1) to characterize all and only the natural language grammars, (2) to algorithmically determine membership and generative power consequences of GPSG's and (3) to embody the universalism of natural language entirely in the formal system. I prove that "=E*?" is undecidable for GPSGs and, on the basis of this result and the unnaturalness of E*, I argue that GPSG's three goals and its weak context-free generative power conflict with each other: there is no algorithmic way of knowing whether any given GPSG generates a natural language or an unnatural one. The paper concludes with a diagnosis of the result and suggests that the problem might be met by abandoning the weak context-free framework and assuming substantive constraints. |
| first_indexed | 2024-09-23T12:53:16Z |
| id | mit-1721.1/6447 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T12:53:16Z |
| publishDate | 2004 |
| record_format | dspace |
| spelling | mit-1721.1/64472019-04-12T08:30:48Z Defining Natural Language Grammars in GPSG Ristad, Eric Sven This paper is a formal analysis of whether generalized phrase structure grammar's (GPSG) weak context-free generative power will allow it to achieve three of its central goals: (1) to characterize all and only the natural language grammars, (2) to algorithmically determine membership and generative power consequences of GPSG's and (3) to embody the universalism of natural language entirely in the formal system. I prove that "=E*?" is undecidable for GPSGs and, on the basis of this result and the unnaturalness of E*, I argue that GPSG's three goals and its weak context-free generative power conflict with each other: there is no algorithmic way of knowing whether any given GPSG generates a natural language or an unnatural one. The paper concludes with a diagnosis of the result and suggests that the problem might be met by abandoning the weak context-free framework and assuming substantive constraints. 2004-10-04T14:56:34Z 2004-10-04T14:56:34Z 1986-04-01 AIM-895 http://hdl.handle.net/1721.1/6447 en_US AIM-895 1619510 bytes 644622 bytes application/postscript application/pdf application/postscript application/pdf |
| spellingShingle | Ristad, Eric Sven Defining Natural Language Grammars in GPSG |
| title | Defining Natural Language Grammars in GPSG |
| title_full | Defining Natural Language Grammars in GPSG |
| title_fullStr | Defining Natural Language Grammars in GPSG |
| title_full_unstemmed | Defining Natural Language Grammars in GPSG |
| title_short | Defining Natural Language Grammars in GPSG |
| title_sort | defining natural language grammars in gpsg |
| url | http://hdl.handle.net/1721.1/6447 |
| work_keys_str_mv | AT ristadericsven definingnaturallanguagegrammarsingpsg |