Binary context-free grammars

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

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Article number1209
JournalSymmetry
Volume12
Issue number8
DOIs
Publication statusPublished - 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)

Fingerprint

Dive into the research topics of 'Binary context-free grammars'. Together they form a unique fingerprint.

Cite this