1
$\begingroup$

Suppose I have two LR(1) languages $L_1$, $L_2$. Is $L_1 \cup L_2$ also LR(1)? References to proofs would be very helpful.

$\endgroup$
1

1 Answer 1

4
$\begingroup$

A simple example is $$L_1 = \{a^i b^i c^j \mid i,j\ge 0\}$$ $$L_2 = \{a^i b^j c^j \mid i,j\ge 0\}$$

Clearly, both languages are $LR(1)$. (Indeed, they are $LL(1)$.) But their union is inherently ambiguous, so not $LR(k)$ for any $k$.

This is also the usual example for non-closure of context-free languages over intersection. $L_1 \cap L_2$ is $\{a^i b^i c^i \mid i\ge 0\}$, the classic non-context-free language.

$\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.