# $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$?

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.

-
This happens iff each grammar produces finitely many strings and the sum of those numbers is prime. Each property can be decided independently. – templatetypedef Aug 5 '12 at 15:55
By the sum you mean the amount of strings each machine get? Do we know to compute this number? and we should also check not to count number twice. – Jozef Aug 5 '12 at 16:06
You questions would be more accessible if you use ordinary English, e.g. say that something "is computable" rather than saying it is "$\in R$". – Carl Mummert Aug 6 '12 at 12:24
I don't understand what you don't understand. If you know how to decide if $L(G)$ is finite, then this is obvious, because you work on a finite set, so everything is decidable. – Xoff Aug 6 '12 at 16:49

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.