7
$\begingroup$

Suppose I have two LL languages $L_1, L_2$, both describable by LL($k$) grammars for the same $k$, and regular language $R$. Which of the following are also LL languages, and can they be described by LL($k$) grammars?

  • $L_1 \cup L_2$ (union)
  • $L_1 \circ L_2$ (concatenation)
  • $L_1^*$ (Kleene star)
  • $L_1 \cap R$ (intersection with a regular language)
$\endgroup$

1 Answer 1

9
$\begingroup$

All of these (except possibly Kleene closure) are answered (in the negative) in Rosenkrantz & Stearns, Properties of Deterministic Top-Down Grammars, 1970.

For an example of a language whose Kleene closure is non-deterministic, see this answer by Hendrik Jan.

$\endgroup$
3
  • $\begingroup$ Ouch... I'll definitely read that for the proofs. $\endgroup$
    – Koz Ross
    Sep 30, 2020 at 21:42
  • $\begingroup$ Actually, I might have misremembered the Kleene star closure. Rechecking. $\endgroup$
    – rici
    Sep 30, 2020 at 21:44
  • $\begingroup$ Just in case, added another reference for Kleene star. $\endgroup$
    – rici
    Sep 30, 2020 at 21:58

Your Answer

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

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