Additional problem 3-19 Find a regular expression to describe: The set of all st

Question

Additional problem 3-19

Find a regular expression to describe:
The set of all strings over the alphabet {a, b, c} that always contain the substring “bc” (at least one or more times)
So, for example, the following strings are in this language:

bc, abc, aaaaaaaaabc, abcba, bc, bcb, aaaabcaaacbc, bbc, bcabc

and the following strings are NOT in this language:

   cb, acb, aaaa, bbbb, c, b, a, bronco, cccccccccccccabac

Additional 3-20:
Find a regular expression to describe:

The set of all strings over the alphabet {a, b, c, d} that contain exactly one a and exactly one b

So, for example, the following strings are in this language:

ab, ba, cccbad, acbd, cabddddd, ddbdddacccc

and the following strings are NOT in this language:

a, ccbc, acbcaaacba, acacac, bcbbbbbca, aca, c, d, b

Additional 3-21:
Find a regular expression to describe L, where L = The set of strings over the alphabet {a, b, c, d} where every “c” is immediately preceded and also followed by a “b” (i.e. every “c” has the symbol “b” right next to it on both sides)   So, for example … These strings are in L:

a, b, d, bcb, abbbbcbddabcb, abd, dbcbcb, bcbcb

and these strings are NOT in L:

abc, abcbabc, asdc, cbbb, acb

Additional 3-22:
Find a regular expression to describe m, where M = the set of strings over the alphabet {a,b,c,d} which start with the letter 'a' or the letter 'b' and also contain exactly one c

For example, the following strings are in M:

ac, bc, abc, abcba, bcbd, bbbbbbc, aaaaaabbbbcdd, bbbbcaaa

and these are NOT in M:

abcbabc, a, b, c, d, ca, dbbbacbba, bcabcd

Explanation / Answer

3-19: (a+b+c)* bc (a+b+c)*

3-20: ( ( (c+d)* a (c+d)* b (c+d)* ) + ( (c+d)* b (c+d)* a (c+d)* ) )

3-21: (a+b+d+ b(cb)*)*

3-22: (a+b) (a+b+d)* c (a+b+d)*

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.