How to prove a language is regular?

Question

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?

Answer 1

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

  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'$.

Answer 2

Another way is to build up the language using operations under which you know they are closed. This is an extension to exhibiting a regular expression, as you have many more operations available (reverse the string, complement, intersection, chop out a piece, just keep a part, homomorphisms and inverse homomorphisms, ...)

Answer 3

The answer by Ran G. give a fairly extensive listing of the equivalent models that can be used to specify regular languages (and the list goes on, two-way automata, MSO logic, but that is covered by the link under 'more equivalent models'). And as Raphael stresses, we need an argument to convince the audience that the chosen representation is indeed correct.

Reconsidering the question, it adds 'For instance $\dots$'. That means we have to give a valid construction that, given any of the above models we assume specify language $L$, turns that model into one for $L'$. This generally will be the same type of model, but need not be: we can e.g. start with an deterministic FSA for $L$ and end with a nondeterminitic one for $L'$.

This includes the possibility to use closure operations: in the explicitly given operation in the example we have $L'= (\Sigma^* \setminus L) \cdot \Sigma^*$.

So, my point is that the answer is great, but we should add the "from $L$ to $L'$ construction", when not building a specific language from scratch.

Answer 4

A language is regular iff you can write a scanner that decides on arbitrary strings whether or not they belong to the language using no more than a fixed amount of memory - i.e. recognition can be done in O(1) space.