## 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 | |

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)