Pergunta

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)
Foi útil?

Solução

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.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top