Is the Language 0^m1^n regular?

[yuren1978]

I know 0^n1^n is not regular, but how about the Language 0^m1^n .

[whisky]

yuss it is a regular language.

[stillarnd]

can u explain.

[sudipta_cht]

0-->0-->0--->... m times and then 1--->1-->1--> n times... it is regular

[whisky]

the above is the language can be represented by 0*1* .... which is regular.

[stillarnd]

so why is 0^n 1^n not regular?

[whisky]

@stillarnd: use the pumping lemma to prove this.

 

could anybody pleas explain the difference between a language and an expression.

[bilash]

an expression is one way of describing a language. You can also say an expression is kind of a "formula" for a language.

[R0jkumar]

I think you also need to mention the constraints on the integers m and n.

If for example it is given that m and n are non-negative integers(i.e m >= 0 and n >= 0) , then the language 0^m 1^n is regular since it is equivalent to 0*1*. But if there are additional constraints like for example m != n or m > n then the above language is not regular.

 

rajkumar

[SenorSaru]

Well, if you're familiar with programming with regular expressions, it gets easier. If you can make a regular expression for the pattern, then it's regular. If a regular expression would be impossible, then it's not regular. Your regular expression shouldn't need any advanced features.

 

Unfortunately, I know of no such trick for determining if a language is context-free or not. Sure, if you can make a context-free grammar for the language, then it's context-free. But, I don't have so much experience making context-free grammars.

[PatheticOne]

On way of thinking about this is in terms of automaton, remember a regalar one is accpeted by a [/b] finite [/b] automaton which remembers anything in terms of states, as the number of states are bounded in any FA hence the amount of information it can remeber is also bounded. Also the only way to remember the number of any symbol appearing in a string is to count that symbol. in case 0^n1^n you/automaton have to first count the number of 0s and remember, since number of 0s is unbounded ( we dont have an upper limit on n ) we will require an unbounded number of states! now this voilates one necessary requirement of FA. so this family strings cannt be accepted by a FA so its not regular. Now in case of 0^m1^n we only have to remember that 1s follow 0s nothing more, specially their numbers! hence it may be possible to build a FA for this. Indeed we can construct one and also a regular expression 0*1* thats it! its a regular one. One thumb rule which i use to quickly assess the regularity of any language is the amount of information (most of the time counting) that will be reuqired to be remembered while processing a string, if its bounded well there is a very good (or rather a perfect) chance we can have a regalr expression otherwise its not regular. similarly for CFG think in terms of no of stacks (1 for cgf).