2
$\begingroup$

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.

  • 0
    This happens iff each grammar produces finitely many strings and the sum of those numbers is prime. Each property can be decided independently.2012-08-05
  • 0
    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.2012-08-05
  • 3
    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$".2012-08-06
  • 0
    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.2012-08-06

1 Answers 1

4

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.

  • 0
    @Yuvla: What would happen if it was the same question but instead of intersection there was union?2012-08-09
  • 0
    Then it becomes undecidable.2012-08-09