Алгебраические и аналитические методы для доказательства неоднозначности грамматик

GF(2)-grammars, recently introduced by Bakinova et al. [4], and further studied by Makarov and Okhotin [21], are a variant of ordinary context-free grammars, in which the disjunction is replaced by exclusive OR, whereas the classical concatenation is replaced by a new operation called GF(2)-concatenation: K ⊙ L is the set of all strings with an odd number of partitions into a concatenation of a string in K and a string in L.
There are several reasons for studying GF(2)-grammars. Firstly, they are a class of gram- mars with better algebraic properties, compared to ordinary grammars and similar grammar families, because the underlying boolean semiring logic was replaced by a logic of a eld with two elements. As we will see later, that makes GF(2)-grammars lend themselves very well to algebraic manipulations.
Secondly, GF(2)-grammars provide a new way of looking at unambiguous grammars. For example, instead of proving that some language is inherently ambiguous, one can prove that no GF(2)-grammar describes it. While the latter condition is, strictly speaking, stronger, it may turn out to be easier to prove, because GF(2)-grammars have good algebraic properties and are also closed under symmetric di erence, meaning that more tools can be used in the proof.
Finally, GF(2)-grammars generalize the notion of parity nondeterminism to grammars. Re- call that the most common types of nondeterminism that are considered in complexity theory are classical nondeterminism, which corresponds to an existence of an accepting computation, unambiguous nondeterminism, which corresponds to an existence of unique accepting com- putation and parity nondeterminism, which corresponds to number of accepting computations being odd.
Tying to the theme of connections between unambiguous and GF(2)-grammars, classical and parity nondeterminism can be seen as two di erent generalisations of unambiguous non- determinism: if the number of accepting computations is in the set {0, 1}, then it is positive (classical case) if and only if it is odd (parity case); the same is not true for larger numbers, of course.
The main result of the rst part of this thesis is Theorem 6 that establishes a strong neces- sary conditions on subsets of a∗1a∗2 . . . a∗k that are described by GF(2)-grammars. Theorem 5, a special case of Theorem 6, implies that there are no GF(2)-grammars for the languages L1 :={anbmcl |n=morm=l}andL2 :={anbmcl |n̸=morm̸=l}.
As a consequence, both are inherently ambiguous. For L1, all previously known arguments establishing its inherent ambiguity were combinatorial, mainly based on Ogden’s lemma.
Proving the inherent ambiguity of L2 was a long-standing open question due to Autebert et al. [3, p. 375]. There is an interesting detail here: back in 1966, Ginsburg and Ullian fully characterized bounded languages described by unambiguous grammars in terms of semi-linear sets [16, Theorems 5.1 and 6.1]. However, most natural ways to apply this characterization su er from the same limitation: they mainly rely on words that are not in the language and much less on the words that are. Hence, dense languages like L2 leave them with almost nothing to work with. Moreover, L2 has an algebraic generating function, meaning that analytic methods cannot tackle it either. In fact, Flajolet [11], in his seminal work on analytic methods for proving grammar ambiguity, refers to inherent ambiguity of L2 as to a still open question (see page 286).
The close relationship between GF(2)- and unambiguous grammars brings us to the second topic of the thesis: the equivalence problem for unambiguous grammars. It can be stated in the
3
following way: Is there an algorithm that takes two unambiguous grammars and tells whether they generate the same language or not? . It is an important, but di cult open problem in formal language theory. So far, only partial progress has been made. Most famously, it was positively resolved in two special cases: when one of the grammars is regular [24] and when both grammars correspond to a deterministic pushdown automaton [25] (languages recog- nized by DPDA are an important, but small subclass of languages described by unambiguous grammars). Moreover, the proof of the latter result is very long, technical and involved.