Binary context-free grammars

Sherzod Turaev; Rawad Abdulghafor; Ali Amer Alwan; Ali Abd Almisreb; Yonis Gulzar

doi:10.3390/SYM12081209

Binary context-free grammars

Sherzod Turaev, Rawad Abdulghafor, Ali Amer Alwan, Ali Abd Almisreb, Yonis Gulzar

Department of Computer Science and Software Engineering

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

Abstract

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.

Original language	English
Article number	1209
Journal	Symmetry
Volume	12
Issue number	8
DOIs	https://doi.org/10.3390/SYM12081209
Publication status	Published - Aug 2020

Keywords

Binary grammar
Chomsky hierarchy
Computation power
Context-free grammar
Formal language
Matrix grammar
Relational grammar

ASJC Scopus subject areas

Computer Science (miscellaneous)
Chemistry (miscellaneous)
General Mathematics
Physics and Astronomy (miscellaneous)

Access to Document

10.3390/SYM12081209

Cite this

@article{47aeef6981884cd8ba6b1e5259be1b7c,

title = "Binary context-free grammars",

abstract = "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.",

keywords = "Binary grammar, Chomsky hierarchy, Computation power, Context-free grammar, Formal language, Matrix grammar, Relational grammar",

author = "Sherzod Turaev and Rawad Abdulghafor and Alwan, {Ali Amer} and {Abd Almisreb}, Ali and Yonis Gulzar",

note = "Publisher Copyright: {\textcopyright} 2020 by the authors.",

year = "2020",

month = aug,

doi = "10.3390/SYM12081209",

language = "English",

volume = "12",

journal = "Symmetry",

issn = "2073-8994",

publisher = "Multidisciplinary Digital Publishing Institute (MDPI)",

number = "8",

}

TY - JOUR

T1 - Binary context-free grammars

AU - Turaev, Sherzod

AU - Abdulghafor, Rawad

AU - Alwan, Ali Amer

AU - Abd Almisreb, Ali

AU - Gulzar, Yonis

PY - 2020/8

Y1 - 2020/8

N2 - 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.

AB - 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.

KW - Binary grammar

KW - Chomsky hierarchy

KW - Computation power

KW - Context-free grammar

KW - Formal language

KW - Matrix grammar

KW - Relational grammar

UR - http://www.scopus.com/inward/record.url?scp=85089696414&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85089696414&partnerID=8YFLogxK

U2 - 10.3390/SYM12081209

DO - 10.3390/SYM12081209

M3 - Article

AN - SCOPUS:85089696414

SN - 2073-8994

VL - 12

JO - Symmetry

JF - Symmetry

IS - 8

M1 - 1209

ER -

Binary context-free grammars

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this