Binary context-free grammars

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

	PDF (Journal Article) - Published Version Restricted to Registered users only Download (326kB) | Request a copy
	PDF (Scopus) Restricted to Registered users only Download (85kB) | Request a copy

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.

Item Type:	Article (Journal)
Additional Information:	8638/81846
Uncontrolled Keywords:	formal language, binary grammar; context-free grammar; matrix grammar; relational grammar; computation power; chomsky hierarchy
Subjects:	Q Science > QA Mathematics Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Kulliyyahs/Centres/Divisions/Institutes (Can select more than one option. Press CONTROL button):	Kulliyyah of Information and Communication Technology > Department of Computer Science Kulliyyah of Information and Communication Technology > Department of Computer Science
Depositing User:	DR. ALI A. ALWAN AL-JUBOORI
Date Deposited:	29 Jul 2020 10:58
Last Modified:	23 Dec 2020 16:06
URI:	http://irep.iium.edu.my/id/eprint/81846

Actions (login required)

View Item