# How do I prove that a language is regular? [duplicate]

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.

## marked as duplicate by David Richerby, Yuval Filmus formal-languages StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Dec 14 '16 at 15:50

• 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?" – Rick Decker Dec 1 '16 at 2:19
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$?