3
$\begingroup$

This is my attempt to solve an exercise from a formal languagues class.

Consider the following definition:

extend(L) = { w $\in$ $\Sigma^*$ | $\exists$ x $\in$ L, y$\in$ $\Sigma^*$ . w = xy }

In words: extend(L) is the set of all strings with some prefix in L;

1- Are CFLs (Context Free Languages) closed under 'extend'? ( If L is CFG, then extend(L) is also CFG?). Justify your answer.

Answer: Yes.

Let $G_L$ be the CFG gramar for L . We can construct a new $G_E$ for extend(L) as follows:

S' $\Rightarrow$ SE

E $\Rightarrow$ $a_1$E | $a_2$E | $a_n$E | $\epsilon$

(all other productions from $G_L$

where S' is the starting symbol for $G_E$; S is the starting symbol for $G_L$ > and $a_1$..$a_n$ are all the symbols from $\Sigma$

Is this correct?

2- Recursively Enumerable Languages are closed under 'extend' ?

Answer: False.

I feel like it is not RE because I can't create a TM for extend(L), but I don't know how to prove it. Reducing another well known undecidable problem to it, perhaps.... but how, and which one?

Thanks for any help!

1 Answers 1

5

The first part looks okay. For the second, though, $\mathrm{extend}(L)$ appears to be the concatenation of $L$ and $\Sigma^*$, and the r.e. languages are closed under concatenation. Consider a Turing machine $M$ that lists $L$. Modify it so that after listing the $n$-th word of $L$, it systematically lists all of the extensions of the first $n$ words by a maximum of $n$ letters.

  • 0
    @marcos: You modify $M$ to get $M'$ that works as follows. You feed $M'$ the input $1$, and it simulates $M$ with input $1$ **and** generates $w_1a_1,\dots,w_1a_n$. You feed it $2$, and it simulates $M$ with $1$ but outputs $w_1a_ia_j$ for all $i,j$, then simulates $M$ with $2$ and outputs $w_2$, all $w_2a_i$, and all $w_2a_ia_j$. And so on.2012-06-21