1. (10 points) Consider the alphabet -ta, b}. Here are several descriptions of s

Question

1. (10 points) Consider the alphabet -ta, b}. Here are several descriptions of sets, along with several regular expressions. Match the ones that describe the languages. In other words: for each mathematical description of a set, list (any and a) regular expressions that describe the set. Remember to justify your answers. Hint: start by coming up with test strings for each set and checking whether or not they are described by the regular expressions. For example, is in the set? is it in the set described by each of the regular expressions? Mathematical descriptions of sets Regular expressions {w {w {w * | w does not start with b} * | ba is a substring of w} * l ab is not a substring of w} 2, (ii) b(aUb)" (iv) b (aUb) (v) (Xba)' (vi) "(ba)L' 3, 4, Note: the notation 220 refers to the set of nonnegative integers. Similarly, we could use the notation Z+ to refer to the set of (strictly) positive integers [This problem was revised to remove the unnecessary mention of DFAs. ]]

Explanation / Answer

1.
b*a* because it generates zero or more number of b's and then followed by zero or more numberes of a's

2
no such regular expression from the list matches the need
apt regular expression of 2 is
(a(a U b)* )| ()
i.e. does not start with b (hence must strat with a) and followed by any combination ocharacters

3
this one is pretty simple
*(ba)*

4
ab does not occur means after a we cannot have any more b, so a's can appear only in the last, and hence first part of the word can be nothing other than b
so the answe is
b*a*

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

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