حل تمرین نظریه محاسبات/فصل اول/حل تمرین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)