The Gateway to Computer Science Excellence
+1 vote

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

in Theory of Computation by
edited by | 136 views
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 ??

1 Answer

+4 votes
Best answer

Let us think of the complementary language which will be :

L = { na(W) * nb(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 LC ) .

So  the original language L  =   (Lc)c

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

Now we have Lc 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.

selected by
thnx @habibkhan nice explanation as  ever...
i think concept of reducibility involve here :P)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,315 questions
60,432 answers
95,245 users