Binary context-free grammars

• Main Authors: Turaev, Sherzod, Abdulghafor, Rawad Abdulkhaleq Abdulmolla, Alwan, Ali Amer, Almisreb, Ali Abd, Gulzar, Yonis
• Format: Article
• Language: English; English
• Published: MDPI 2020
• Subjects: QA Mathematics; QA75 Electronic computers. Computer science
• Online Access: http://irep.iium.edu.my/81846/1/symmetry-12-01209_Published_Version.pdf; http://irep.iium.edu.my/81846/7/Binary%20context-free%20grammar_Scopus.pdf; http://irep.iium.edu.my/81846/; https://www.mdpi.com/2073-8994/12/8/1209; https://doi.org/10.3390/sym12081209
• Institution: Universiti Islam Antarabangsa Malaysia

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.