Abstract:
GF(2)-grammars are a relatively recently introduced family of formal grammars. They have many interesting algebraic properties, and results about them often provide insights into the classical family of unambiguous grammars. In this work, we prove strong necessary conditions for a GF(2)-grammar to define subsets of $w_1^* w_2^* \ldots w_k^*$, where $w_1$, $w_2$, $\ldots$, $w_k$ are arbitrary fixed strings. In the proof, we apply algebraic techniques related to formal power series. Further application of these results allows us to prove the inherent ambiguity of the language $\{a^n b^m c^\ell\mid n \neq m \text{ or } m \neq \ell\}$, which has long been an open question, and to give a new, completely algebraic, proof of the inherent ambiguity of the language $\{a^n b^m c^\ell\mid n = m \text{ or } m = \ell\}$.
Key words and phrases:formal grammars, finite fields, bounded languages, unambiguous grammars, inherent ambiguity.
Fulltext:
PDF file (404 kB)