HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

What are the closure properties of LL(k) languages?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
thewhatarepropertieslanguagesclosure

Problem

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)

Solution

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.

Context

StackExchange Computer Science Q#130682, answer score: 9

Revisions (0)

No revisions yet.