0
$\begingroup$

In order to prove that the following language is regular, would I use a pumping lemma?

The set $A$ of all strings that are substrings of some string in $L$, where $L \subseteq\Sigma^*$. $L$ Must be regular.

$\endgroup$
  • 3
    $\begingroup$ Good. Now do a similar modification to the title, otherwise one of our moderators will likely suggest that it be sharpened. Consider, for example, "If $L$ is regular, is the language of all substrings of $L$ regular?" $\endgroup$ – Rick Decker Dec 1 '16 at 2:19
  • $\begingroup$ @NoahSM1993 is it some string, or any string? $\endgroup$ – André Souza Lemos Dec 1 '16 at 2:21
  • 2
    $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Dec 1 '16 at 5:47
  • 1
    $\begingroup$ The pumping lemma is only a necessary condition for regularity, thus it can only be used to show that some language is not regular. $\endgroup$ – Jan Johannsen Dec 1 '16 at 14:12
2
$\begingroup$

Here's a hint. Since $L$ is regular, there is a finite automaton $M$ that accepts all and only those strings in $L$. Suppose you only wanted those substrings that start with the same character as a string in $L$. Could you somehow modify $M$ (perhaps by making some states final) so that it would accept all substrings starting with the same character as a string accepted by $L$?

Having done that, could extend this (perhaps with $\epsilon$-moves) so that you could jump from the start state of $M$ to a string along an accepting path in $M$?

$\endgroup$

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