Proving a Language to be regular

regular-language
Happy Mittal picture Happy Mittal · Dec 26, 2010 · Viewed 7.9k times · Source

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 ?

Answer

miku picture miku · Dec 26, 2010

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.

Related questions

Regular vs Context Free Grammars

I'm studying for my computing languages test, and there's one idea I'm having problems wrapping my head around. I understood that regular grammars are simpler and cannot contain ambiguity, but can't do a lot of tasks that are required for …

Read More
Regular expression for strings with even number of a's and odd no of b's

Im having a problem in solving the problem:- Its an assignment, i solved it, but it seems to be too long and vague, Can anyboby help me please...... Regular expression for the strings with even number of a's and …

Read More
Left-Linear and Right-Linear Grammars

I need help with constructing a left-linear and right-linear grammar for the languages below? a) (0+1)*00(0+1)* b) 0*(1(0+1))* c) (((01+10)*11)*00)* For a) I have the following: Left-linear S --> B00 | S11 B --> B0|B1|011 Right-linear S --> 00B | 11S …

Read More