حل تمرین نظریه محاسبات/فصل اول/حل تمرین1-15
حل تمرین 1-15
تمرین
[ویرایش]برای هرکدام از زبانهای زیر دو رشته مثال بزنید که عضوزبان باشند و دو رشته مثال بزنید که عضوزبان نباشند، پس در کل برای هر زبان چهار رشته مثال بزنید. برای تمام مواردالفبا را {Σ={a,b در نظر بگیرید.
- الف)*a*b
- ب)*a(ba)b
- پ)*a* U b
- ت) *(aaa)
- ث)*Σ*aΣ*bΣ*aΣ
- ج)aba U bab
- چ)b (εUa)
- ح) *a U ba U bb)Σ)
حل
[ویرایش]الف)رشته های عضوزبان هستند:{aab},{aabb}
- رشته هایی که عضو نیستند:{bab},{aba}
ب)رشته های عضوزبان هستند:{abab},{ababb}
- رشته هایی که عضو نیستند:{abaa},{ababa}
پ)رشته های عضوزبان هستند:{aaa},{bb}
- رشته هایی که عضو نیستند:{ab},{bab}
ت)رشته های عضوزبان هستند:{aaa},{aaaaaa}
- رشته هایی که عضو نیستند:{aa},{aaaa}
ث)رشته های عضوزبان هستند:{aaabbab},{baabaaa}
- رشته هایی که عضو نیستند:{ab},{ba}
ج)رشته های عضوزبان هستند:{aba},{ababab}
- رشته هایی که عضو نیستند:{baa},{bba}
چ)رشته های عضوزبان هستند:{ab},{b}
- رشته هایی که عضو نیستند:{a},{aba}
ح)رشته های عضوزبان هستند:{ababba},{ababbb}
- رشته هایی که عضو نیستند:{babb},{abaa}
Marzieh ۱۷ آوریل ۲۰۰۹، ساعت ۱۶:۴۲ (UTC)