(۲۹ مهر ۱۳۹۵ ۰۵:۵۲ ب.ظ)Pure Liveliness نوشته شده توسط:  سلام.

اثبات ریاضی ش رو نمی دونم اما متن صریح کتاب لینز هست که:
خب $\sum$ الفبای یک زبان هست، $\sum^{\ast}$ مجموعه ی تمامی رشته هایی که با این الفبا با هر طولی ساخته میشه. $\sum$ متناهی و غیرتهی هست اما محدودیتی درباره ی طول رشته هایی که از $\sum^{\ast}$ به دست میان نداریم. (این رو توی کتاب دقیقا نوشته)
یک زبان اغلب زیرمجموعه ای از $\sum^{\ast}$ هست. پس میشه نتیجه گرفت که درباره ی زبان های نامتناهی طول رشته محدودیتی نداره.
فک میکنم اینطوری باشه. البته اون اغلب که توی کتاب نوشته جای تامل داره.
از یک نگاه دیگه:
زبانی نامتناهی هست (توی اینجا زبان های منظم مورد بحث هست) باید توی dfa یا nfa اش حداقل یه flash back به یه state دیگه داشته باشه یا روی خودش حلقه داشته باشه. در این صورت بی نهایت بار میتونه این حلقه به طول یک یا هرچیزی (با توجه به این که به کدوم حالت، flash back داریم تکرار بشه پس طول رشته رو نمیتونیم محدود کنیم.

پی نوشت: ببخشید من دقت نکردم که شما دانشجوی ارشد هستید و رشته تون علوم کامپیوتر هست و احتمالاََ اثبات ریاضی خفنی مد نظرتون بوده. فک میکردم واسه کنکور ارشد میخواید...

(۳۰ مهر ۱۳۹۵ ۰۲:۳۸ ب.ظ)hsehat نوشته شده توسط:  

(29 مهر ۱۳۹۵ ۰۵:۵۲ ب.ظ)Pure Liveliness نوشته شده توسط:  سلام.

اثبات ریاضی ش رو نمی دونم اما متن صریح کتاب لینز هست که:
خب $\sum$ الفبای یک زبان هست، $\sum^{\ast}$ مجموعه ی تمامی رشته هایی که با این الفبا با هر طولی ساخته میشه. $\sum$ متناهی و غیرتهی هست اما محدودیتی درباره ی طول رشته هایی که از $\sum^{\ast}$ به دست میان نداریم. (این رو توی کتاب دقیقا نوشته)
یک زبان اغلب زیرمجموعه ای از $\sum^{\ast}$ هست. پس میشه نتیجه گرفت که درباره ی زبان های نامتناهی طول رشته محدودیتی نداره.
فک میکنم اینطوری باشه. البته اون اغلب که توی کتاب نوشته جای تامل داره.
از یک نگاه دیگه:
زبانی نامتناهی هست (توی اینجا زبان های منظم مورد بحث هست) باید توی dfa یا nfa اش حداقل یه flash back به یه state دیگه داشته باشه یا روی خودش حلقه داشته باشه. در این صورت بی نهایت بار میتونه این حلقه به طول یک یا هرچیزی (با توجه به این که به کدوم حالت، flash back داریم تکرار بشه پس طول رشته رو نمیتونیم محدود کنیم.

پی نوشت: ببخشید من دقت نکردم که شما دانشجوی ارشد هستید و رشته تون علوم کامپیوتر هست و احتمالاََ اثبات ریاضی خفنی مد نظرتون بوده. فک میکردم واسه کنکور ارشد میخواید...

خیلی ممنون. در واقع من میخواستم از این قضیه تو یه اثبات استفاده کنم. فقط شک داشتم که آیا واقعا درسته یا نه.
بازم ممنون