Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
1  
there's a typo in the definition of your $L'$, please edit to fix. –  Ran G. Apr 18 '12 at 5:46
2  
"Drawing" is no proof; you have to give an NFA and prove it accepts the language. –  Raphael Apr 18 '12 at 6:00
    
I think the language definition still does not make sense... –  missingno Apr 18 '12 at 15:09
1  
anyways, the specific language is irrelevant if the question is "can I draw an NFA to prove it is regular". @corium, can we edit the question to reflect the more general question: "how to prove that a specific $L$ is regular"? –  Ran G. Apr 18 '12 at 16:39
add comment

5 Answers

up vote 18 down vote accepted

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

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

share|improve this answer
1  
It might also be worth noting that proving a language is finite is enough to show it's regular. That can be useful, particularly in non-constructive proofs by cases. –  Patrick87 Apr 18 '12 at 11:18
2  
regexp's as found in programming languages can do much more than regular languages. You'd have to restrict to "classical" constructs. –  David Lewis Apr 18 '12 at 13:00
4  
@DavidLewis: On this site, you may assume that by "regular expression" the classical notion is meant. –  Raphael Apr 18 '12 at 18:38
    
@DavidLewis I agree, one should avoid "regexp" in the context of theory to avoid confusion. –  Raphael Apr 19 '12 at 19:40
    
Note that for any of the first four bullets, you'll need a proof showing that your representation is indeed correct. –  Raphael Feb 19 '13 at 6:03
add comment

Elementary methods

  1. Finite automata (possibly nondeterministic, with empty transitions).
  2. Regular expressions.
  3. Right (or Left, but not both) linear equations, like $X = KX + L$ where $K$ and $L$ are regular.
  4. Regular (Type 3) grammar.
  5. Operations preserving regular languages (Boolean operations, product, star, shuffle, morphisms, inverses of morphisms, reversal, etc.)
  6. Recognized by a finite monoid.

Logical methods (often used in formal verification)

  1. Monadic second order logic (Büchi's theorem).
  2. Linear temporal logic (Kamp's theorem).
  3. Rabin's tree theorem (Monadic second order logic with two successors). Very powerful.

Advanced methods

  1. Sophisticated pumping lemmas. See for instance
    [1] J. Jaffe, A necessary and sufficient pumping lemma for regular languages, Sigact News - SIGACT 10 (1978) 48-49.
    [2] A. Ehrenfeucht, R. Parikh, and G. Rozenberg, Pumping lemmas for regular sets, SIAM J. Comput. 10 (1981), 536-541.
    [3] S. Varricchio, A pumping condition for regular sets, SIAM J. Comput. 26 (1997) 764-771.

  2. Well quasi orders. See
    [4] W. Bucher, A. Ehrenfeucht, D. Haussler, On total regulators generated by derivation relations, Theor. Comput. Sci. 40 (1985) 131–148.
    [5] M. Kunz, Regular Solutions of Language Inequalities and Well Quasi-orders.

  3. Support of $\mathbb{N}$-rational series.

  4. Algebraic methods based on Transductions (see also Operations preserving regular languages).

share|improve this answer
add comment

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, ...)

share|improve this answer
    
That's already mentioned in Ran's answer. –  Raphael Jan 18 '13 at 15:18
add comment

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.

share|improve this answer
    
I am not quite sure what you are getting at. If I have some model for $L'$, I can convert it into any of the other equivalent ones. –  Raphael Apr 3 '13 at 7:13
    
@Raphael Sorry I did make my point. The earlier answers seem to explain we can construct a description of the language (as automaton, operations, etc.). I agree. However, the question seems to be about closure properties, see the example given. That point I am missing in the other answers: to prove a closure property you assume you have a description, and construct a new one. –  Hendrik Jan Apr 4 '13 at 11:04
    
Ah, this $L'$! Now I get it, my bad. I agree, this aspect is missing from Ran's answer. –  Raphael Apr 4 '13 at 12:09
    
I'm not sure why it is missing (or what exactly is missing). Say you have a regular $L'$, and you want to prove $L$ is regular as well, you can start with $L'$'s DFA and use it to construct a DFA for $L$. But this is covered by "construct a DFA for $L$".. there's no restriction to use $L'$ automaton for that task (and naturally, if $L$ is defined via $L'$ you will be forced to use $L'$'s automaton..). The same goes for regexp, closure, grammars, etc. –  Ran G. Apr 9 '13 at 5:28
    
@RanG. Yes I agree. (And I do like your answer.) But someone that has to be explained what it means to show a language regular might need a more explicit explanation how one proves a closure property for regular languages (start with an unknown given representation and transform it). That was/is my point. (The closure property question is not clear from the title or initial paragraph, but is implied by the "for example".) Raphael has added some words on this in your original answer. –  Hendrik Jan Apr 9 '13 at 23:55
show 1 more comment

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.

share|improve this answer
    
O(1) space, you mean? In any case, this is covered by the fact that DFA suffice; it may be worthwhile to explicitly note this equivalence in terms of programming. –  Raphael Apr 5 '13 at 11:37
    
Yes, it is just a different perspective. –  reinierpost Apr 8 '13 at 15:59
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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