The inherent ambiguity partial algorithm problem for context free languages
Pages 19 - 20
Abstract
It is shown that there is no “partial algorithm” (effective procedure that may fail to terminate) by which, given a context free grammar, one can always find an unambiguous context free grammar generating the same language if such an unambiguous grammar exists. The argument turns on the degree of unsolvability of the inherent ambiguity problem for context free languages.
References
[1]
Davis, M., "Computability and Unsolvability." McGraw-Hill, New York, 1958.
[2]
Ginsburg, S., "The Mathematical Theory of Context-Free Languages." McGraw-Hill, New York, 1966.
[3]
Ginsburg, S., Hibbard, T. N., and Ullian, J. S., Sequences in Context Free Languages. Illinois J. Math. 9(1965), 321-337.
[4]
Ogden, W., A Helpful Result for Proving Inherent Ambiguity. Math. Systems Theory 2(1968), 191-194.
[5]
Rogers, H., "Theory of Recursive Functions and Effective Computability." McGraw-Hill, New York, 1967.
[6]
Ullian, J. S., Partial Algorithm Problems for Context Free Languages. Information and Control 11(1967), 80-101.
Index Terms
- The inherent ambiguity partial algorithm problem for context free languages
Recommendations
Inherent Ambiguity of Languages Generated by Spine Grammars
There have been many arguments that the underlying structure of natural languages is beyond the descriptive capacity of context-free languages. A well-known example is tree adjoining grammars; less common are spine grammars, linear indexed grammars, ...
Bracketed context-free languages
A bracketed grammar is a context-free grammar in which indexed brackets are inserted around the right-hand sides of the rules. The language generated by a bracketed grammar is a bracketed language. An algebraic condition is given for one bracketed ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
May 1969
267 pages
ISBN:9781450374781
DOI:10.1145/800169
Copyright © 1969 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 05 May 1969
Check for updates
Qualifiers
- Article
Acceptance Rates
Overall Acceptance Rate 1,469 of 4,586 submissions, 32%
Upcoming Conference
STOC '25
- Sponsor:
- sigact
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 443Total Downloads
- Downloads (Last 12 months)41
- Downloads (Last 6 weeks)4
Reflects downloads up to 09 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in