How to prove a language is regular?

There are many methods to prove that a language is not regular, but what do I need to do to prove that some language is regular?

For instance, if I am given that $L$ is regular,
how can I prove that the following $L'$ is regular, too?

$\qquad \displaystyle L' := \{w \in L: uv = w \text{ for } u \in \Sigma^* \setminus L \text{ and } v \in \Sigma^+ \}$

Can I draw a nondeterministic finite automaton to prove this?

Yes, if you can come up with any of the following:

• deterministic finite automaton (DFA),

• nondeterministic finite automaton (NFA),

• regular expression (regexp of formal languages) or

• regular grammar

for some language $L$, then $L$ is regular. There are more equivalent models, but the above are the most common.

There are also useful properties outside of the "computational" world. $L$ is also regular if

• it is finite,

-
you can construct it by performing certain operations on regular languages, and those operations are closed for regular languages, such as

• intersection,

• complement,

• homomorphism,

• reversal,

• left- or right-quotient,

• regular transduction

and more, or

• using Myhill–Nerode theorem if the number of equivalence classes for $L$ is finite.

In the given example, we have some (regular) langage $L$ as basis and want to say something about a language $L'$ derived from it. Following the first approach -- construct a suitable model for $L'$ -- we can assume whichever equivalent model for $L$ we so desire; it will remain abstract, of course, since $L$ is unknown. In the second approach, we can use $L$ directly and apply closure properties to it in order to arrive at a description for $L'$.

StackExchange Computer Science Q#1331, answer score: 59