Binary context-free grammars
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 bina...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English English |
| Published: |
MDPI
2020
|
| Subjects: | |
| Online Access: | http://irep.iium.edu.my/81846/ 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 |
| _version_ | 1848789192220344320 |
|---|---|
| author | Turaev, Sherzod Abdulghafor, Rawad Abdulkhaleq Abdulmolla Alwan, Ali Amer Almisreb, Ali Abd Gulzar, Yonis |
| author_facet | Turaev, Sherzod Abdulghafor, Rawad Abdulkhaleq Abdulmolla Alwan, Ali Amer Almisreb, Ali Abd Gulzar, Yonis |
| author_sort | Turaev, Sherzod |
| building | IIUM Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-14T17:52:49Z |
| format | Article |
| id | iium-81846 |
| institution | International Islamic University Malaysia |
| institution_category | Local University |
| language | English English |
| last_indexed | 2025-11-14T17:52:49Z |
| publishDate | 2020 |
| publisher | MDPI |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | iium-818462020-12-23T08:06:58Z http://irep.iium.edu.my/81846/ Binary context-free grammars Turaev, Sherzod Abdulghafor, Rawad Abdulkhaleq Abdulmolla Alwan, Ali Amer Almisreb, Ali Abd Gulzar, Yonis QA Mathematics QA75 Electronic computers. Computer science 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. MDPI 2020-07-24 Article PeerReviewed application/pdf en http://irep.iium.edu.my/81846/1/symmetry-12-01209_Published_Version.pdf application/pdf en http://irep.iium.edu.my/81846/7/Binary%20context-free%20grammar_Scopus.pdf Turaev, Sherzod and Abdulghafor, Rawad Abdulkhaleq Abdulmolla and Alwan, Ali Amer and Almisreb, Ali Abd and Gulzar, Yonis (2020) Binary context-free grammars. Symmetry, 12 (8). E-ISSN 2073-8994 https://www.mdpi.com/2073-8994/12/8/1209 https://doi.org/10.3390/sym12081209 |
| spellingShingle | QA Mathematics QA75 Electronic computers. Computer science Turaev, Sherzod Abdulghafor, Rawad Abdulkhaleq Abdulmolla Alwan, Ali Amer Almisreb, Ali Abd Gulzar, Yonis Binary context-free grammars |
| title | Binary context-free grammars |
| title_full | Binary context-free grammars |
| title_fullStr | Binary context-free grammars |
| title_full_unstemmed | Binary context-free grammars |
| title_short | Binary context-free grammars |
| title_sort | binary context-free grammars |
| topic | QA Mathematics QA75 Electronic computers. Computer science |
| url | http://irep.iium.edu.my/81846/ http://irep.iium.edu.my/81846/ http://irep.iium.edu.my/81846/ 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 |