Самые трудные формальные языки

The notion of a complete set for a family of formal languages is among the central concepts of theoretical computer science. Given a reduction mechanism, such as logarithmic-space Turing machines, a language, to which every language from a family is reducible, is called hard for that family. If, furthermore, this language belongs to the family, it is complete for that family.
For this definition to make sense, the reduction mechanism should be computationally weaker than the family itself. Furthermore, the weaker the reduction mechanism, the stronger are the results on the completeness of some language with respect to those reductions. The weakest reduction mechanism are homomorphisms, under which every symbol a from the alphabet of the given language is mapped to a substring h(a) over the alphabet of the hard language. There is a notable result involving such reductions: Greibach’s [8] “hardest context-free language”, that is, a fixed language L0 over an alphabet Σ0 defined by a formal grammar, to which one can reduce every language L defined by a grammar over any alphabet Σ, by a suitable homomorphism h: Σ∗ → Σ∗0, so that a nonempty string w ∈ Σ+ belongs to L if and only if its image h(w) is in L0.
Greibach’s result inspired a line of research on the existence of hardest languages under homomorphic reductions in various families of formal languages. Already Greibach [9] proved the first negative result, that for the family of languages described by LR(1) grammars, or, equivalently, recognized by deterministic pushdown automata, there cannot exist such a hardest language. For another important subfamily of grammars, the linear grammars, non-existence of hardest languages was established by Boasson and Nivat [3]. On the other hand, as proved by Okhotin [24], two generalizations of ordinary (“context-free”) grammars do have hardest languages: these are conjunctive grammars [20, 23], with an explicit conjunction operation in the rules, and Boolean grammars [22], which are further equipped with a negation operation.
Hardest languages under homomorphic reductions have been investigated beyond formal grammars. For the family of regular languages, Cˇul ́ık and Maurer [7] proved that a hardest language under homomorphic reductions cannot exist; a related stronger result was later estab- lished by Harju, Karhum ̈aki and Kleijn [10]. Autebert [1] obtained the same negative result for one-counter automata. On the other hand, Greibach [8] proved a hardest language theorem for a certain restricted type of Turing machines, whereas Cˇul ́ık and Maurer [7] found a hardest language in the complexity class NSPACE(n); their argument extends to NSPACE(f(n)) and DSPACE(f(n)) for every space-constructible function f.
I have already researched the problem of hardest languages as my Bachelor’s thesis. The first topic of research was the family generated by grammars with one-sided context operators [2]—an extension of conjunctive grammars with a special operator that restricts the form of the prefix of the entire string preceding the derived substring. This allows the grammar to succinctly express “declaration before use” and similar conditions. As it turned out, the construction of a hardest language for conjunctive grammars could be augmented to handle this extension as well [17]. The second topic of my research was the family of linear conjunctive grammars—an intermediate step between linear and conjunctive grammars. The key to solving this problem was using an alternative characterization [21] of the generated languages as those recognized by one-way real-time cellular automata (also known as trellis automata): a classical model, first studied by Smith [26], that represents the process of parsing a string as a linear array of cells, each initialized with a single symbol of the string, passing finite information to their neighbours in one direction in discrete steps.
The present work continues this research by constructing a hardest language for a close rel- ative of the latter model—[two-way] linear-time cellular automata, which have been introduced by Smith [26] as well, but have since been found to be much more powerful than trellis automata: forinstance,theycanrecognizethelanguages{a2n |n 0}[5]and{anbin|n,i 1}[4].There is an important theoretical result on linear speed-up for this model: every language recognized by a cellular automaton in time C · n can be recognized in time (1 + ε)n, see Ibarra et al. [12].
3
LL
LR
UnambLin
Unamb
Lin
Ordinary (CF)
Conj+
UnambTAG TAG Multi
Reg LLLin
LRLin
IDPDA
Bool Conj
UnambBool
RT-CA
UnambConj LinConj=TA
Figure 1: Inclusion graph of language families for which the problem has already been solved (circled: hardest language exists; crossed: hardest language does not exist; both: hardest lan- guage exists, but only under a slightly relaxed definition), alongside some intermediate and related families (neither circled nor crossed).
Whether these automata are equivalent to the intermediate model of [two-way] real-time cel- lular automata operating in time exactly n, is a long-standing open problem raised already by Smith [26] and addressed many times in the literature. For more details about cellular automata as language-recognition devices, the reader is directed to a survey by Terrier [28].
Additionally, this work also investigates the existence of hardest languages for the classical language family parsable in linear time, the LL(k) languages, which are recognized by top-down parsers with a k-symbol lookahead. This family is not closed under inverse homomorphisms, see Lehtinen and Okhotin [15]. This does not affect possible existence of hardest languages, but that if they do exist, then their inverse homomorphic images would include languages beyond LL(k). Indeed, in spite of this non-closure, there is a hardest language theorem for LL: the first such result, presented in Section 5, is that LL(1) grammars in the Greibach normal form (these are “simple grammars” of Korenjak and Hopcroft [13]) have a hardest language with respect to reductions by homomorphisms. It is natural to try extending this result to the entire LL(k) hierarchy. An apparent obstacle is presented in Section 6: it is proved that already for the family of LL(1) languages, there is no hardest language under the strict definition of Greibach, that is, with respect to reductions by homomorphisms. This obstacle leads to a small modification of the definition of hardest languages: as shown in Section 7, if a single end-marker is appended to the input, then a hardest LL(k) language does exist. In fact, it can be generated by a single LL(1) grammar in the Greibach normal form uniformly for all k.
With the new contributions of this thesis, the current state of the art in hardest languages for basic language families is presented in Figure 1 (with newly proved results framed). For families represented by black circles, namely for multi-component grammars of several kinds as well as for unambiguous variations of ordinary, conjunctive and Boolean grammars, the existence of hardest languages remains an open problem. The results of this thesis have been accepted for presentation at formal language conferences: at LATA 2021 [18] for the results of Sections 2–3, and at DLT 2021 [19] for the results of Sections 4–7.