edited by
419 views
1 votes
1 votes

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

edited by

1 Answer

Best answer
4 votes
4 votes

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

Related questions

3 votes
3 votes
1 answer
2
Prateek Raghuvanshi asked Nov 10, 2017
488 views
$L_1 =\{a^n b^m c^n \mid m,n \geq 0\}$ and $L_2=\{ a^n b^n\mid n\geq 0\}$. If $L=L_2-L_1$ then $L$ isfinite languageregular languageDCFL not DCFL
2 votes
2 votes
2 answers
3