Gateforum test id 70 question no 37

[TEJAS JOSHI]

How can the langauge

L1= { a^n b^m | n>=1 , m>=1 ,nm >= 3 } can be regular

[Varun Shinde]

It is not regular...answer given in the answer key is definitely
wrong..many of them post a msg on the wrong answer key...
this grammar is CFL...as it require 1 memory element ....

[shripad sarade]

In attachment I have drawn NFA for this language.
I think this is correct NFA.
This language is regular.

[TEJAS JOSHI]

hey thanks shripad .Thats is an right NFA I tried for almost all
possible strings.

On Feb 9, 12:46 am, shripad sarade <shripad.sar...@gmail.com> wrote:
> In attachment I have drawn NFA for this language.
> I think this is correct NFA.
> This language is regular.
>

> On Tue, Feb 9, 2010 at 12:33 AM, Varun Shinde <varunshinde...@gmail.com>wrote:
>
> > It is not regular...answer given in the answer key is definitely
> > wrong..many of them post a msg on the wrong answer key...
> > this grammar is CFL...as it require 1 memory element ....
>
> > On Feb 8, 10:50 pm, TEJAS JOSHI <tejasjoshi2...@gmail.com> wrote:
> > > How can the langauge
>
> > >  L1= { a^n b^m |  n>=1 , m>=1 ,nm >= 3 } can be regular
>
>
>

>  nm_more_than_3.jpg
> 32KViewDownload

[harshjpathak]

using a regular language we can compare the OCCURRENCE of two or more elements but we cannot compare the elements directly. In the given grammar we are comparing the OCCURRENCE  of the two elements we are not comparing the two elements directly Hence it is regular.  A palindrome language is not regular because we compare the two elements with each other. 

Source : Hopcraft , motwani , ullman book