- Set of strings over $\{0,1\}$ having at least two occurrence of the substring 00.
- $\{a^n b^m : n ≥ 4, m ≥ 3\}$.
- Set of strings over the alphabet $\{a,b,c\}$ containing at least one $a$ and one $b$.
$\begingroup$
$\endgroup$
3
-
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 FilmusCommented Mar 23, 2019 at 18:30
-
$\begingroup$ The usual rule is one question per post. $\endgroup$– Yuval FilmusCommented Mar 23, 2019 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. ♦Commented Mar 23, 2019 at 18:40
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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^*)$.
-
$\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$– ajax007Commented Mar 23, 2019 at 18:37