Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 4 down vote accepted

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.

share|cite|improve this answer
@Yuvla: What would happen if it was the same question but instead of intersection there was union? – Jozef Aug 9 '12 at 10:58
Then it becomes undecidable. – Yuval Filmus Aug 9 '12 at 16:14

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.