Search code examples
regular-language

Proving a Language to be regular

Pumping Lemma is used to prove a language to be not regular. But How a language can be
proved to be regular ? In particular, 

Let L be a language. Define half(L) to be  
{ x | for some y such that |x| = |y|, xy is in L}.  
Prove for each regular L that half(L) is regular.

Is there any trick or general procedure to tackle such kind of questions ?

Solution

  • If you can correctly describe your language L by an NFA or DFA, then it will be regular.

    There is a well known equality of NFAs, DFAs, regular grammars and regular expressions, so a representation of L in any of these formalisms should do.