Advertisement
Published in:
2021 | OriginalPaper | Chapter
Bounded Languages Described by GF(2)-grammars
Author : Vladislav Makarov
Published in: Developments in Language Theory
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
GF(2)-grammars are a recently introduced grammar family that has some unusual algebraic properties and is closely connected to the family of unambiguous grammars. By using the method of formal power series, we establish strong conditions that are necessary for subsets of \(a_1^* a_2^* \cdots a_k^*\) to be described by some GF(2)-grammar. By further applying the established results, we settle the long-standing open question of proving the inherent ambiguity of the language \(\{ \, a^n b^m c^\ell \mid n \ne m \text { or } m \ne \ell \, \}\), as well as give a new, purely algebraic, proof of the inherent ambiguity of the language \(\{ \, a^n b^m c^\ell \mid n = m \text { or } m = \ell \, \}\).