1. (10 points) Recall the following definitions (from page 44) on languages (set
ID: 3875680 • Letter: 1
Question
1. (10 points) Recall the following definitions (from page 44) on languages (sets of strings) A, B: Union AU B = {x | x A or x B} Concatenation Ao -{zy 1 TE A and y E B} Star Afrir2...lk kE Z and k 20 and each ri E A) For each of the following languages (sets of strings) over the alphabet (a,b), answer the following questions: (a) Is e (the empty string) in the set? (b) Classify each string over [a, b of length 2 as in the set or not in the set. Briefly justify each classification 2. fa) o fa, b, ab 3. w E ab, ba bb is not a substring of w 4. The language described by the regular expression a b*Explanation / Answer
1)
a) yes, every set contains empty string epsilon
b)
length 2, strings over {a,b} = {aa,ab,ba,bb}
1.{a,b} U {ab} produce {a,b,ab}
aa does not belongs to set, because it can't be generated.
ab belongs to set...
ba does not belongs to set
bb does not belongs to set
2. {a} concatenate {a,b,ab} produce {aa,ab,aab}
aa belongs to set,
ab belongs to set...
ba does not belongs to set, because it can't be generated.
bb does not belongs to set
3.{ab,ba}* produce {ab,ba,abab,baba,....}
aa does not belongs to set, because it can't be generated.
ab belongs to set
ba belongs to set
bb does not belongs to set... because it can't be generated.
4.a*b* produce {epsilon, a,b,ab,aa,bb,ba........}
aa belongs to set
bb belongs to set
ab belongs to set
ba belongs to set
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.