3
$\begingroup$

The Problem:

Say that a language is prefix-closed if all prefixes of every string in the language are also in the language. Let C be an infinite, prefix-closed, context-free language. Show that C contains an infinite regular subset.

Can we show this by using Myhill-Nerode Theorem?

$\endgroup$
2
$\begingroup$

Given a normal form grammer $G$ for an infinite prefix-closed $L$, examine the (almost) regular grammer $G'$ obtained by transforming rules of the form $A\rightarrow BC$ into $A\rightarrow B$. I leave it to you to show that $L(G')$ satisfies your requirements.

$\endgroup$
0
$\begingroup$

Another easy solutions uses the pumping-lemma for context-free languages. Let $L$ be infinite, prefix closed and context free. Then there is an $l$ such that for all $z\in L$ with length at least $l$ there is a decomposition $uvwxy=z$, s.t. $vx$ has length $>0$, $vwx$ hat length $\leq l$ and $\forall i\geq 0: uv^iwx^iy\in L$ (actually, we don't need $l$ and just one $z$ and since $L$ is infinite, there is one).

Now take such a word $z$ and some decomposition. Then $uv^*$ and $uvwx^*$ are regular expression for subsets of $L$ (since $L$ is prefixed closed) and at least one of them generates an infinite language, because $x$ and $v$ cannot both be empty.

Using the Myhill-Nerode Theorem seems rather difficult: Take the language $L=\{a^nb^m|m\leq n\}$. While $A=\{a\}^*=\{a^n| n\geq 0\}$ is an infinite regular subset of $L$, all the $a^i$ ($i\geq 0$) are pairwise inequivalent w.r.t. the Nerode relation of $L$. So we need an additional ingredient to show why we can collapse equivalence classes by not allowing certain suffixes (that is what taking a subset practically means for the Nerode relation).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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