The Gateway to Computer Science Excellence

+1 vote

0

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???

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???

+4 votes

Best answer

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.**

52,315 questions

60,432 answers

201,766 comments

95,245 users