TITLE: $L=\{\langle G_1,G_2 \rangle|G_{1,2}$ are context free grammars, and the size of $L(G_1) \cup L(G_2) $is a prime$\} \in R$?
QUESTION [2 upvotes]: Why does the following language $L=\{\langle G_1,G_2\rangle|G_1$ and $G_2 $are context free grammars, and the size of $L(G_1) \cup L(G_2)$ is a prime $\} \in R$?
How do I prove it? I didn't come to any smart conclusions.
I know that determining whether $|L(G)|< \infty$ is decidable.

REPLY [4 votes]: The first step is to form a context-free grammar $G$ such that $L(G) = L(G_1) \cup L(G_2)$. I'll let you figure that part yourself. Next, we want to check whether $L(G)$ is infinite. We start by eliminating symbols which only generate the empty string. Now we check the "production graph" for loops - the language is finite iff there are none. Finally, if $L(G)$ is finite then we can recursively list $L(G)$, and check whatever decidable property of $|L(G)|$ we want.
Edit: The OP also asks about the same problem with $\cap$ instead of $\cup$. We reduce the problem of finding whether $L(G_1)$ and $L(G_2)$ are disjoint to $L$, so that $L$ is also undecidable. Let $a,b$ be new symbols, and define for $i=1,2$:
$$ H_i = \{a,aa\} \cup \{b^n w : n \geq 0, w \in G_i\}. $$
If $L(G_1) \cap L(G_2) = \emptyset$ then $L(H_1) \cap L(H_2) = \{a,aa\}$ which is prime. If $w \in L(G_1) \cap L(G_2)$ then $b^nw \in L(H_1) \cap L(H_2)$ for all $n \geq 0$, and in particular the intersection is not finite.
{"set_name": "stack_exchange", "score": 2, "question_id": 179152}