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