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
    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
    Then it becomes undecidable.2012-08-09