{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:03:40Z","timestamp":1760238220801,"version":"build-2065373602"},"reference-count":48,"publisher":"MDPI AG","issue":"8","license":[{"start":{"date-parts":[[2020,7,24]],"date-time":"2020-07-24T00:00:00Z","timestamp":1595548800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100006013","name":"United Arab Emirates University","doi-asserted-by":"publisher","award":["G00003321"],"award-info":[{"award-number":["G00003321"]}],"id":[{"id":"10.13039\/501100006013","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>A binary grammar is a relational grammar with two nonterminal alphabets, two terminal alphabets, a set of pairs of productions and the pair of the initial nonterminals that generates the binary relation, i.e., the set of pairs of strings over the terminal alphabets. This paper investigates the binary context-free grammars as mutually controlled grammars: two context-free grammars generate strings imposing restrictions on selecting production rules to be applied in derivations. The paper shows that binary context-free grammars can generate matrix languages whereas binary regular and linear grammars have the same power as Chomskyan regular and linear grammars.<\/jats:p>","DOI":"10.3390\/sym12081209","type":"journal-article","created":{"date-parts":[[2020,7,24]],"date-time":"2020-07-24T09:06:09Z","timestamp":1595581569000},"page":"1209","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Binary Context-Free Grammars"],"prefix":"10.3390","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6661-8469","authenticated-orcid":false,"given":"Sherzod","family":"Turaev","sequence":"first","affiliation":[{"name":"Department of Computer Science &amp; Software Engineering, College of Information Technology, United Arab Emirates University, Al Ain 15551, UAE"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0266-1027","authenticated-orcid":false,"given":"Rawad","family":"Abdulghafor","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Faculty of Information and Communication Technology, International Islamic University Malaysia, Gombak, Selangor 53100, Malaysia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3279-9366","authenticated-orcid":false,"given":"Ali","family":"Amer Alwan","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Faculty of Information and Communication Technology, International Islamic University Malaysia, Gombak, Selangor 53100, Malaysia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7581-5747","authenticated-orcid":false,"given":"Ali","family":"Abd Almisreb","sequence":"additional","affiliation":[{"name":"Faculty of Engineering and Natural Sciences, International University of Sarajevo, 71210 Sarajevo, Bosnia and Herzegovina"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6515-1569","authenticated-orcid":false,"given":"Yonis","family":"Gulzar","sequence":"additional","affiliation":[{"name":"Department of Management Information Systems, King Faisal University, Al-Ahsa 31982, Saudi Arabia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,7,24]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1109\/TIT.1956.1056813","article-title":"Three models for the description of languages","volume":"2","author":"Chomsky","year":"1956","journal-title":"IRE Trans. Inf. Theory"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Chomsky, N. (1957). Syntactic Structure, Mouton.","DOI":"10.1515\/9783112316009"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/S0019-9958(59)90362-6","article-title":"On certain formal properties of grammars","volume":"2","author":"Chomsky","year":"1959","journal-title":"Inf. Control"},{"key":"ref_4","unstructured":"Hopcroft, J., Motwani, R., and Ullman, J. (2007). Introduction to Automata Theory, Languages, and Computation, Pearson."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Rozenberg, G., and Salomaa, A. (1997). Handbook of Formal Languages, Springer.","DOI":"10.1007\/978-3-642-59126-6"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Dassow, J., and P\u0103un, G. (1989). Regulated Rewriting in Formal Language Theory, Springer.","DOI":"10.1007\/978-3-642-74932-2"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"P\u01ceun, G., Rozenberg, G., and Salomaa, A. (1998). DNA Computing. New Computing Paradigms, Springer.","DOI":"10.1007\/978-3-662-03563-4"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Meduna, A., and Soukup, O. (2017). Modern Language Models and Computation. Theory with Applications, Springer.","DOI":"10.1007\/978-3-319-63100-4"},{"key":"ref_9","unstructured":"Sipser, M. (2013). Introduction to the Theory of Computation, Cengage Learning."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Meduna, A., and Zemek, P. (2014). Regulated Grammars and Automata, Springer.","DOI":"10.1007\/978-1-4939-0369-6"},{"key":"ref_11","first-page":"287","article-title":"Simple-Semi-Conditional Versions of Matrix Grammars with a Reduced Regulated Mechanism","volume":"23","author":"Meduna","year":"2004","journal-title":"Comput. Inform."},{"key":"ref_12","first-page":"61","article-title":"Some questions of phrase-structure grammars","volume":"4","author":"Abraham","year":"1965","journal-title":"Comput. Linguist."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1016\/S0022-0000(74)80053-X","article-title":"On vector languages","volume":"8","author":"Cremers","year":"1974","journal-title":"J. Comp. Syst. Sci."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1007\/BF01692513","article-title":"Control sets on grammars","volume":"2","author":"Ginsburg","year":"1968","journal-title":"Math. Syst. Theory"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1145\/321495.321504","article-title":"Programmed grammars and classes of formal languages","volume":"16","author":"Rozenkrantz","year":"1969","journal-title":"J. ACM"},{"key":"ref_16","first-page":"911","article-title":"A new generative device: Valence grammars","volume":"25","year":"1980","journal-title":"Rev. Roum. Math. Pures Appl."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/0020-0190(73)90008-2","article-title":"A note on leftmost restricted random context grammars","volume":"2","author":"Cremers","year":"1973","journal-title":"Inform. Proc. Lett."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1016\/S0019-9958(68)90439-7","article-title":"Grammars with partial ordering of the rules","volume":"12","author":"Fris","year":"1968","journal-title":"Inform. Control"},{"key":"ref_19","unstructured":"Peak, I., and Szep, J. (1984). Conditional grammars: Motivations, definitions and some properties. Proc. Conf. Automata, Languages and Mathematical Sciences."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"647","DOI":"10.1145\/321479.321488","article-title":"Indexed grammars. An extension of context-free grammars","volume":"15","author":"Aho","year":"1968","journal-title":"J. ACM"},{"key":"ref_21","first-page":"145","article-title":"Bicolored Digraph Grammar Systems","volume":"1","author":"Wood","year":"1973","journal-title":"RAIRO Inform. Th\u00e9rique et Appl.\/Theor. Inform. Appl."},{"key":"ref_22","first-page":"301","article-title":"A Note on Bicolored Digraph Grammar Systems","volume":"3","author":"Wood","year":"1973","journal-title":"IJCM"},{"key":"ref_23","first-page":"191","article-title":"Petri net controlled grammars: The power of labeling and final markings","volume":"12","author":"Dassow","year":"2009","journal-title":"Rom. J. Inf. Sci. Technol."},{"key":"ref_24","first-page":"2808","article-title":"Petri net controlled grammars: The case of special Petri nets","volume":"15","author":"Dassow","year":"2009","journal-title":"J. Univers. Comput. Sci."},{"key":"ref_25","unstructured":"Prusinkiewicz, P., and Hanan, J. (1980). Lindenmayer Systems, Fractals, and Plants, Springer. Lecture Notes in Biomathematics."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1016\/S0022-0000(72)80025-4","article-title":"Absolutely parallel grammars and two-way deterministic finite state transducers","volume":"6","author":"Rajlich","year":"1972","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/S0019-9958(74)80054-9","article-title":"Parallel context-free languages","volume":"24","author":"Siromoney","year":"1974","journal-title":"Inform. Control"},{"key":"ref_28","first-page":"32","article-title":"On some grammars with global productions","volume":"2","author":"Levitina","year":"1972","journal-title":"NTI Ser."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1016\/S0022-0000(69)80015-2","article-title":"Scattered context grammars","volume":"3","author":"Greibach","year":"1969","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_30","first-page":"748","article-title":"Concurrently Controlled Grammars","volume":"54","author":"Mavlankulov","year":"2018","journal-title":"Kybernetika"},{"key":"ref_31","first-page":"55","article-title":"Parallel communicating grammar systems: The regular case","volume":"37","author":"Santean","year":"1989","journal-title":"Ann. Univ. Buc. Ser. Mat.-Inform."},{"key":"ref_32","unstructured":"Csuhaj-Varj\u00fa, E., Dassow, J., Kelemen, J., and P\u0103un, G. (1994). Grammar Systems: A Grammatical Approach to Distribution and Cooperation, Gordon and Beach Science Publishers."},{"key":"ref_33","first-page":"60","article-title":"On Multiple Grammars","volume":"5","year":"1969","journal-title":"Kybernetika"},{"key":"ref_34","first-page":"99","article-title":"n-ary Grammars and the Description of Mapping of Languages","volume":"6","year":"1970","journal-title":"Kybernetika"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1016\/S0019-9958(65)90392-X","article-title":"Relational Phrase Structure Grammar and Its Tentative Applications","volume":"8","author":"Bellert","year":"1965","journal-title":"Inf. Control"},{"key":"ref_36","first-page":"264","article-title":"Relational Phrase Structure Grammar Applied to Mohawk Constructions","volume":"3","author":"Bellert","year":"1966","journal-title":"Kybernetika"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1016\/S1045-926X(05)80003-5","article-title":"Relation Grammars and their Application to Multidimensional Languages","volume":"4","author":"Crimi","year":"1991","journal-title":"J. Vis. Lang. Comput."},{"key":"ref_38","unstructured":"Wittenburg, K. (1992, January 15\u201318). Earley-Style Parsing for Relational Grammars. Proceedings of the IEEE Workshop on Visual Languages, Seattle, WA, USA."},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Marriott, K., and Meyer, B. (1998). Relational Grammars: Theory and Practice in a Visual Language Interface for Process Modeling. Visual Language Theory, Springer Science & Business Media.","DOI":"10.1007\/978-1-4612-1676-6"},{"key":"ref_40","unstructured":"Cole, P., and Sadock, J. (2020). On Relational Constraints on Grammars. Grammatical Relations, BRILL."},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Mart\u00edn-Vide, C., Mitrana, V., and P\u0103un, G. (2004). Formal Languages and Applications, Springer.","DOI":"10.1007\/978-3-540-39886-8"},{"key":"ref_42","unstructured":"Baumgarten, B. (1990). Petri-Netze. Grundlagen und Anwendungen, Wissensschaftverlag."},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Reisig, W., and Rozenberg, G. (1997). Lectures on Petri Nets I: Basic Models, Springer.","DOI":"10.1007\/3-540-65306-6"},{"key":"ref_44","first-page":"609","article-title":"Petri net controlled grammars with a bounded number of additional places","volume":"19","author":"Dassow","year":"2009","journal-title":"Acta Cybernetica"},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"283","DOI":"10.21136\/MB.1992.126278","article-title":"Binary and Ternary Relations","volume":"117","year":"1992","journal-title":"Math. Bohem."},{"key":"ref_46","first-page":"541","article-title":"Pseudodimension of Relational Structures","volume":"49","year":"1999","journal-title":"Czechoslov. Math. J."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"780","DOI":"10.1016\/j.ejc.2009.07.005","article-title":"Hypergroups and n-ary Relations","volume":"31","author":"Cristea","year":"2010","journal-title":"Eur. J. Comb."},{"key":"ref_48","first-page":"191","article-title":"Some Properties on the Powers of n-ary Relational Systems","volume":"43","author":"Chaisansuk","year":"2013","journal-title":"Novi Sad J. Math."}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/12\/8\/1209\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T09:51:17Z","timestamp":1760176277000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/12\/8\/1209"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,24]]},"references-count":48,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2020,8]]}},"alternative-id":["sym12081209"],"URL":"https:\/\/doi.org\/10.3390\/sym12081209","relation":{},"ISSN":["2073-8994"],"issn-type":[{"type":"electronic","value":"2073-8994"}],"subject":[],"published":{"date-parts":[[2020,7,24]]}}}