6
$\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$
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 '20 at 21:42
  • $\begingroup$ Actually, I might have misremembered the Kleene star closure. Rechecking. $\endgroup$ – rici Sep 30 '20 at 21:44
  • $\begingroup$ Just in case, added another reference for Kleene star. $\endgroup$ – rici Sep 30 '20 at 21:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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