12
$\begingroup$

Greibach famously defined a language $H$, the so-called nondeterministic version of $D_2$, such that any CFL is an inverse morphic image of $H$. Does there exist a similar statement with DCFL, possibly with some restriction on the morphisms allowed?

(See, e.g., M. Autebert, J. Berstel, and L. Boasson. Context-free languages and pushdown automata. In R. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, volume I, chapter 3. Springer Verlag, 1997.)

Improve this question
$\endgroup$

3 Answers 3

Reset to default
8
$\begingroup$

An identical homomorphism characterization of DCFL does not seem to be possible. The following is extracted from Greibach's original paper.

We show that every context-free language can be expressed as $h^{-1}(L_0)$ or $h^{-1}(L_0-\{e\})$ for a homomorphism $h$. The algebraic statement is: the family of context-free languages is a principal AFDL; ... By way of contrast, the family of deterministic context-free languages is not a principal AFDL [7].

The paper 7 is the conference version of the paper. In the conference version, Theorem 4.2 states that "The family of deterministic context-free languages is not a principal AFDL".

However some analogue characterization may still be possible. Okhotin provided homomorphic characterizations of conjunctive and Boolean grammars. For DCFL's the problem seems to be open. The following is the conclusion of Okhotin's paper (from 2013).

Every family of languages closed under inverse homomorphisms can potentially have an analogue of Greibach’s inverse homomorphic characterization. The question is, which families have it? Could it exist for linear, deterministic or unambiguous variants of ordinary (context-free) grammars? Could there be such a characterization for linear conjunctive grammars, unambiguous conjunctive grammars, etc.?

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks! However, I do know that the DCFL are not principal ; this is why I'm allowing the morphisms to be restricted if needed - I can more accurately word my question as: what is the smallest class of functions F for which there is a language H where F(H) is the set of all DCFL - give or take some additional closures. $\endgroup$
    – Michaël Cadilhac
    Feb 21, 2016 at 22:59
  • $\begingroup$ Ok. I edited my answer. It seems that for DCFL this is an open problem. $\endgroup$
    – Mateus de Oliveira Oliveira
    Feb 21, 2016 at 23:28
  • $\begingroup$ Funnily enough, I know very well Okhotin's article, but didn't notice that he was explicitly referring to the problem! Well then, I'm not sure what to do here; sure, it is a valid answer for the moment, but should it be left open until solved? $\endgroup$
    – Michaël Cadilhac
    Feb 23, 2016 at 15:54
  • 2
    $\begingroup$ I don't know what is the police of the site about asking solutions for hard open problems. Personally, if someone pointed to me that a problem I'm interested in is open for many years, then I would accept the answer. My opinion is that in this case it is more appropriate to view the question as a reference request. But there may be divergent points of view with relation to this. I think this discussion in meta.cstheory might be helpful meta.cstheory.stackexchange.com/questions/1058/… $\endgroup$
    – Mateus de Oliveira Oliveira
    Feb 23, 2016 at 23:46
  • 1
    $\begingroup$ Of course I don't mind you accepting your the answer. Indeed it is a very interesting answer. However although the answer kind of fits the title, it is very different from the question itself, since logspace reductions are much more powerful than homomorphisms. $\endgroup$
    – Mateus de Oliveira Oliveira
    Feb 29, 2016 at 20:48
8
$\begingroup$

There actually is a hardest DCFL, which is a deterministic version of Greibach's; it was introduced by Sudborough in 78 in On deterministic context-free languages, multihead automata, and the power of an auxiliary pushdown store—it is however hardest w.r.t log-space reduction. The language $L_0^{(2)}$ referred therein is the set of words over $\{a, \bar{a}, b, \bar{b}, \#, [, ]\}$ where:

$$\gamma_0\;[\bar{a}\gamma_a^{(1)}\#\bar{b}\gamma_b^{(1)}]\;\cdots\; [\bar{a}\gamma_a^{(k)}\#\bar{b}\gamma_b^{(k)}]\enspace,$$

with $\gamma_0, \gamma_a^{(i)}, \gamma_b^{(i)}$ words over $\{a, \bar{a}, b, \bar{b}\}$, such that there exists a word $w_1w_2\cdots w_k \in \{a, b\}^k$ with $\gamma_0 \; \bar{w_1}\gamma_{w_1}^{(1)} \cdots \bar{w_k}\gamma_{w_k}^{(k)}$ a Dyck word.

It then holds that $L_0^{(2)}$ is a DCFL and any DCFL log-space-reduces to $L_0^{(2)}$. In that sense, $L_0^{(2)}$ is the hardest tape DCFL.

As mentioned by contributor Mateus de Oliveira Oliveira, DCFL is not a principal AFL, and it is unknown whether there exists an exact characterization involving the closure of a single language under some operations.

Improve this answer
$\endgroup$
8
$\begingroup$

The paper

J.-M. Autebert, Une note sur le cylindre des langages déterministes, Theoretical Computer Science 8 (1979), 395-399

gives a short proof of the following result (credited to Greibach) which seems to answer your question:

there is no deterministic context-free language $L$ such that, for every deterministic context-free language $C$, there is an homomorphism $h$ and a regular language $R$ such that $C = h^{-1}(L)\cap R$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.