article

Free access

On Context-Free Languages

Author:

Rohit J. ParikhAuthors Info & Claims

Journal of the ACM (JACM), Volume 13, Issue 4

Pages 570 - 581

https://doi.org/10.1145/321356.321364

Published: 01 October 1966 Publication History

PDF eReader

Abstract

In this report, certain properties of context-free (CF or type 2) grammars are investigated, like that of Chomsky. In particular, questions regarding structure, possible ambiguity and relationship to finite automata are considered. The following results are presented:

The language generated by a context-free grammmar is linear in a sense that is defined precisely.

The requirement of unambiguity—that every sentence has a unique phrase structure—weakens the grammar in the sense that there exists a CF language that cannot be generated unambiguously by a CF grammar.

The result that not every CF language is a finite automaton (FA) language is improved in the following way. There exists a CF language L such that for any L′ ⊆ L, if L′ is FA, an L″ ⊆ L can be found such that L″ is also FA, L′ ⊆ L″ and L″ contains infinitely many sentences not in L′.

A type of grammar is defined that is intermediate between type 1 and type 2 grammars. It is shown that this type of grammar is essentially stronger than type 2 grammars and has the advantage over type 1 grammars that the phrase structure of a grammatical sentence is unique, once the derivation is given.

References

[1]

BAR-HILLEL, Y., PRLES, M., AND SHAMIR, E. On formal properties of simple phrase structure grammars. Z. Phonetik, Sprachwissen. Komm. 15 (I961), 143-172; in Y. Bar-Hillel, Language and Information, Addison-Wesley, Reading, Mass., 1965, pp. 116-150.

Google Scholar

[2]

CHOMSKY, N. Three models for the description of lmguage. IRE trans, IT, 3 (1956), 113-.124.

Google Scholar

[3]

----and MILIEh G. A. Fiaite stae languages, Inform, :nd Contr. 1 (19h3), 9b-.112.

Google Scholar

[4]

---. On certai formal propertiets of grammars, inforem. and Contr.2 (1956) 137-167,

Google Scholar

[5]

SCHEINBERG, S. On Booleal properties of phrase structure grammars Inform. and Contr, S (1960), 72---375.

Google Scholar

[6]

SCHUTZENBERGER, M. P, Some remarks on Chomsky's eontext-free lsguges. MIT Quart, Progr. Rep. 63, Oct. 1961, p, 155ff.

Google Scholar

Cited By

View all

Kuznetsov S(2024)Algorithmic complexity for theories of commutative Kleene algebrasIzvestiya: Mathematics10.4213/im9480e88:2(236-269)Online publication date: 4-Apr-2024
https://doi.org/10.4213/im9480e
Kuznetsov S(2024)Алгоритмическая сложность теорий коммутативных алгебр КлиниAlgorithmic complexity for theories of Commutative Kleene algebrasИзвестия Российской академии наук. Серия математическаяIzvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya10.4213/im948088:2(44-79)Online publication date: 25-Mar-2024
https://doi.org/10.4213/im9480
Mereghetti CPalano BRaucci P(2024)Unary Quantum Finite State Automata with Control LanguageApplied Sciences10.3390/app1404149014:4(1490)Online publication date: 12-Feb-2024
https://doi.org/10.3390/app14041490
Show More Cited By

Index Terms

On Context-Free Languages
1. Theory of computation
  1. Formal languages and automata theory
    1. Grammars and context-free languages

Recommendations

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 ...
Lexicalized context-free grammars
ACL '93: Proceedings of the 31st annual meeting on Association for Computational Linguistics

Lexicalized context-free grammar(LCFG) is an attractive compromise between the parsing efficiency of context-free grammar (CFG) and the elegance and lexical sensitivity of lexicalized tree adjoining grammar (LTAG). LCFG is a restricted form of LTAG that ...
Fuzzy context-free languages: part 1: Generalized fuzzy context-free grammars

Motivated by aspects of robustness in parsing a context-free language, we study generalized fuzzy context-free grammars. These fuzzy context-free K-grammars provide a general framework to describe correctly as well as erroneously derived sentences by a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 13, Issue 4

Oct. 1966

159 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/321356

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 1966

Published in JACM Volume 13, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

594
Total Citations
View Citations
2,951
Total Downloads

Downloads (Last 12 months)622
Downloads (Last 6 weeks)82

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Kuznetsov S(2024)Algorithmic complexity for theories of commutative Kleene algebrasIzvestiya: Mathematics10.4213/im9480e88:2(236-269)Online publication date: 4-Apr-2024
https://doi.org/10.4213/im9480e
Kuznetsov S(2024)Алгоритмическая сложность теорий коммутативных алгебр КлиниAlgorithmic complexity for theories of Commutative Kleene algebrasИзвестия Российской академии наук. Серия математическаяIzvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya10.4213/im948088:2(44-79)Online publication date: 25-Mar-2024
https://doi.org/10.4213/im9480
Mereghetti CPalano BRaucci P(2024)Unary Quantum Finite State Automata with Control LanguageApplied Sciences10.3390/app1404149014:4(1490)Online publication date: 12-Feb-2024
https://doi.org/10.3390/app14041490
Im SMoseley BNgo HPruhs K(2024)Polynomial Time Convergence of the Iterative Evaluation of Datalogo ProgramsProceedings of the ACM on Management of Data10.1145/36958392:5(1-19)Online publication date: 7-Nov-2024
https://dl.acm.org/doi/10.1145/3695839
Pimpalkhare NKincaid Z(2024)Monotone Procedure Summarization via Vector Addition Systems and Inductive PotentialsProceedings of the ACM on Programming Languages10.1145/36897778:OOPSLA2(1873-1899)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689777
Anand ASchmitz SSchütze LZetzsche GSobocinski PLago UEsparza J(2024)Verifying Unboundedness via AmalgamationProceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3661814.3662133(1-15)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3661814.3662133
Stjerna ARümmer P(2024)A Constraint Solving Approach to Parikh Images of Regular LanguagesProceedings of the ACM on Programming Languages10.1145/36498558:OOPSLA1(1235-1263)Online publication date: 29-Apr-2024
https://dl.acm.org/doi/10.1145/3649855
Abo Khamis MNgo HPichler RSuciu DWang Y(2024)Convergence of datalog over (Pre-) SemiringsJournal of the ACM10.1145/364302771:2(1-55)Online publication date: 10-Apr-2024
https://dl.acm.org/doi/10.1145/3643027
Hague MJeż ALin A(2024)Parikh’s Theorem Made SymbolicProceedings of the ACM on Programming Languages10.1145/36329078:POPL(1945-1977)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632907
Jaspars H(2024)The stable conjugation-invariant word norm is rational in free groupsProceedings of the American Mathematical Society10.1090/proc/16786Online publication date: 25-Apr-2024
https://doi.org/10.1090/proc/16786
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Bracketed context-free languages

Lexicalized context-free grammars

Fuzzy context-free languages: part 1: Generalized fuzzy context-free grammars

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations