تالار گفتمان مانشت
زبان های نامتناهی - نسخه‌ی قابل چاپ

زبان های نامتناهی - hsehat - 29 مهر ۱۳۹۵ ۰۲:۱۰ ب.ظ

با سلام

آیا می توان گفت که برای طول رشته های یک زبان نامتناهی محدودیتی وجود ندارد؟
اگه کسی اثبات ریاضی برای درست با غلط بودن این جمله داره، ممنون میشم

RE: زبان های نامتناهی - Pure Liveliness - 29 مهر ۱۳۹۵ ۰۵:۵۲ ب.ظ

سلام.

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

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

RE: زبان های نامتناهی - hsehat - 30 مهر ۱۳۹۵ ۰۲:۳۸ ب.ظ

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

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

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

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

RE: زبان های نامتناهی - Pure Liveliness - 30 مهر ۱۳۹۵ ۰۴:۰۴ ب.ظ

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

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

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

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