1. Set of strings over $\{0,1\}$ having at least two occurrence of the substring 00.
  2. $\{a^n b^m : n ≥ 4, m ≥ 3\}$.
  3. Set of strings over the alphabet $\{a,b,c\}$ containing at least one $a$ and one $b$.
  • 1
    $\begingroup$ This is a rather routine exercise. I suggest spending some more time on it. Surely you can solve at least some of these. $\endgroup$ – Yuval Filmus Mar 23 '19 at 18:30
  • $\begingroup$ The usual rule is one question per post. $\endgroup$ – Yuval Filmus Mar 23 '19 at 18:31
  • $\begingroup$ We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in asking questions here that relate to exercises or self-learning. $\endgroup$ – D.W. Mar 23 '19 at 18:40

Well, think about what's necessary in each case.

In the first case, you need two instances of $00$, and you don't care what else is there. If those instances can't overlap, this would be $(\cdot^*) 00 (\cdot^*) 00 (\cdot^*)$, since $(\cdot^*)$ means "anything at all, including nothing". If the instances can overlap, you should union in $(\cdot^*)000(\cdot^*)$, to catch cases like $000$.

In the second case, you need at least four $n$s, then at least three $m$s. So just specify that: $nnnn(n^*) mmm(m^*)$.

| cite | improve this answer | |
  • $\begingroup$ thanks @Draconis it really gives me an idea to solve the problems, and you explains the whole thing in simple words... thanks again.. $\endgroup$ – ajax007 Mar 23 '19 at 18:37

Not the answer you're looking for? Browse other questions tagged or ask your own question.