1. (10 points) In this problem, we\'ll use the following definitions (from page

Question

1. (10 points) In this problem, we'll use the following definitions (from page 44) of operations on languages (sets of strings) A, B: Concatenation Ao B = {xy | x A and y B} Star A* = {xJZ2 . . . xk IkEZand k 20 and each xi EA} For each of the following sets of strings over the alphabet {a, answer the following questions (1) Is (the empty string) in the set? (2) What's an example of a string over {a,b} of length at least 2 that is in the set (or why isn't there such an example)? (3) What's an example of a string over this alphabet of length at least 2 that is not in the set (or why isn't there such an example)? (c) (a, b u (aa, bb Created by Paint X

Explanation / Answer

(a)

1)yes (y=epsilon,w=epsilon)

2)aa

3)ab

(b)Concatenation {aaa,abb,baa,bbb}

1)NO {Epsilon is not in both sets so we can't have epsilon in final set}

2)aaa

3)abbb

(c) Union {a,b,aa,bb}

1)NO { Epsilon is not present in any of the sets so we can't have epsilon in final set }

2)bb

3)ab

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

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