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

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!

share|cite|improve this question
up vote 5 down vote accepted

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.

share|cite|improve this answer
We can't assume anything about the order or size of the strings enumerated by the enumerator of L, since it is RE, right? If the nth work has more than n letters? would we simply generate it as is from the TM of extend? – marcos Jun 21 '12 at 1:55
@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. – Brian M. Scott Jun 21 '12 at 2:11

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.