context free language

Question

Σ ={a,b}
L={W| n_a(W)*n_b(W) ≥ 5}
Is the above language is REGULAR ??

Comments

seems regular.

---

can u draw a DFA for it or hint me to how to draw a DFA for it??
I think there are infinite many possibilities for defining states of DFA so we are not able 2 give a DFA for it bcoz DFA always contains finite no of states .m i right???

---

Till length 5 take all combination
with aaabb = combination 5! / 3! *2!
 aabbb,  = combination 5! / 3! *2!
abbbbb = combination 6! / 5! *1!
 aaaaab=  = combination 6! / 5! *1!
aaaaa is not accepted  bbbbb also.
if m not miss then all strings after this will be in langugage.

---

ok thnx
can u plzz explain me how to distinguish between aaaaa.........a (100 times ) and aaaaa.........a (100 times ) b
here 1st one is not accepted while 2nd ll b accepted ??

Answer 1

Let us think of the complementary language which will be :

L = { n_a(W) * n_b(W) <= 5 } 

Possible ordered pairs for number of a's and b's are = (1,1) , (1,2) ,..(1,5) , 

                                                                              (2,1) , (2,2)

                                                                              (3,1)  , (4,1) and (5,1)

For each of these ordered pairs we can find no of strings as , for example :

If we have (2,2) as ordered pair  , so no of ways we can permute a's and b's  =   4! / 2! 2! [Since this is the case of permutation with limited repetition]   =    6

Similarly , for (5,1) , we have  no of strings   :   6! / 5!   = 6

In this way we can enumerate for each of the cases characterised by the ordered pairs.

Hence we are able to count no of strings which come under this language successfully since we will get a finite value.In other words the language is finite.

And we know that if a language is finite , then it is regular as well.

Hence the complementary language is regular as well ( say it is L^C ) .

So  the original language L  =   (L^c)^c

                                        =    Σ^* - L^c    where Σ^*  stands for Kleene's Closure which is regular in fact.

Now we have L^c as regular as shown above and Kleene's closure is also regular and we know regular language is closed under difference operation.

Hence it is proved that the given language is regular.

Comments

thnx @habibkhan nice explanation as  ever...
i think concept of reducibility involve here :P)