0

I am little bit confuse here about below language is it regular language $$ L= \{a^m b^n \mid mn \ge 10 \}. $$

martini
  • 84,101
Nishant
  • 105

1 Answers1

3

As the language $$ L_1 = \{ a^ib^j \mid 1 \le i, 1\le j, \;ij < 10\} $$ is finite, it is regular. Moreover $$ L_2 = \{a^ib^j \mid i,j \ge 1 \} $$ is regular (in has $aa^*bb^*$ as regular expression). But so $L = L_2 \setminus L_1 = L_2 \cap \complement L_1$ as the set of regular languages is closed under taking complements and finite intersections.

Edit: Regarding Nishant's questions. We have by the definition of complement and intersection \begin{align*} L &= \{a^n b^m \mid nm \ge 10\}\\ &= \{a^n b^m \mid \neg(nm < 10)\}\\ &= \{w \in \Sigma^* \mid \exists n,m\ge 1 : w = a^nb^m \wedge \neg(nm < 10)\}\\ &= \{w \in \Sigma^* \mid \exists n,m \ge 1 : w = a^nb^m\} \cap \{w \in \Sigma^* \mid \neg\exists n,m \ge 1: w=a^nb^m, nm < 10\}\\ &= L_2 \cap \complement L_1 \end{align*}

martini
  • 84,101
  • martini you are correct according to above example you have given even But in question mn which is product >= 10...As I think this will not going to be regular..if mn <= 10 then it will dfenitely going to be regular correct me if i am wrong – Nishant Nov 15 '12 at 14:25
  • But, as I wrote, your $L$ (product $\ge 10$) is the complement of my $L_1$ (product $<10$) intersected with $aa^bb^$, and hence, regular. – martini Nov 15 '12 at 14:28
  • Ok acording to you {a^nb^nc^n where n<= 10 } is regular then it's complement L={ a^nb^nc^n n>10 will be regular} is it fine as we know { a^nb^nc^n n>10 will be regular} is not regular.... – Nishant Nov 15 '12 at 14:35
  • No, as this is not the complement. The complement in $a^+b^+c^+$ is $L = {a^nb^kc^l \mid n\ne k \vee n \ne l \vee k \ne l \vee n > 10}$ – martini Nov 15 '12 at 14:40
  • martini: Is {aibj∣1≤i,1≤j,ij<10} it complement of my problem I don't think so Might be we are interpreting it wrong martini can you check again my above problem is it regular or not In my point of view not looking regular.. – Nishant Nov 15 '12 at 14:54
  • It is. I'll try to work out this point more ... – martini Nov 15 '12 at 14:55
  • martini just can you draw DFA OR NFA For my problem...Dear I will appreciate your help :) – Nishant Nov 15 '12 at 14:55
  • let us continue this discussion in chat – Nishant Nov 15 '12 at 15:02