×

zbMATH — the first resource for mathematics

On formal properties of simple phrase structure grammars. (English) Zbl 0106.34501
Die Arbeit behandelt mathematische Probleme im Zusammenhang mit einfachen, d. h. kontextfreien Konstituentenstrukturgrammatiken (simple phrase structure grammar: PSG), die im Rahmen der theoretischen Linguistik von verschiedenen Autoren entwickelt wurden (vgl. N. Chomsky [Inf. Control 2, 137–167 (1959; Zbl 0088.10801)]; Y. Bar-Hillel, C. Gaifman and E. Shamir [Bull. Res. Council. Israel, Sect. F 9, 1–16 (1960; Zbl 0091.15601)]; St. Scheinberg, Zbl 96, 347). Es sind dies: Darstellungen der PSGs, Relationen zu anderen formalen Systemen, speziell zu endlichen Automaten, Charakterisierung von sprachlichen Ausdrucksmengen, die durch PSGs ableitbar sind, Abschluß unter Booleschen Mengenoperationen und Beweis der rekursiven Unterscheidbarkeit einiger Eigenschaften von PSGs. Letzterer gelingt durch Anwendung des Postschen Theorems der rekursiven Unentscheidbarkeit des Korrespondenzproblems [vgl. Bull. Am. Math. Soc. 52, 264-268 (1946)] auf PSGs.
Die Arbeit ist ein wesentlicher Beitrag zur mathematischen Linguistik, und insbesondere die ersten Abschnitte geben einen kurzen, systematischen und klaren Überblick über die verwendeten Grundbegriffe dieser Disziplin.
Reviewer: H. Schnelle

MSC:
68T50 Natural language processing
91F20 Linguistics
68Q42 Grammars and rewriting systems
PDF BibTeX XML Cite