سلام
این زبان چه جوری مستقله ؟ آیا منظم هم هست؟
[tex]\left \{ xy | n(x)! = n(y) \right \}[/tex]
(۲۶ دى ۱۳۹۲ ۰۳:۱۷ ب.ظ)masoud67 نوشته شده توسط: سلام
این زبان چه جوری مستقله ؟ آیا منظم هم هست؟
[tex]\left \{ xy | n(x)! = n(y) \right \}[/tex]
اون فکتوریله؟
کلا اگر عبارتی نیاز به برابری تعداد عناصر داشته باشه معمولا مستقل از متنه چون باید به همون اندازه که یه x خونده میشه به همون اندازه هم y خونده بشه که چون ماشین متناهی حافظش بسیار ضعیفه نمیتونه اینو یادش بمونه و مجبوریم از ماشین قوی تری که قدرت یاد اوری بهتری ذاره استفاده کنیم که مثلا با یه پشته میتونیم اینو پیاده سازی کنیم.
ولی اگه اون فاکتوریل هستش،نمیدونم دقیقا
Sent from my GT-N5100 using Tapatalk HD
(۲۶ دى ۱۳۹۲ ۰۸:۲۸ ب.ظ)jahanmanesh نوشته شده توسط: اون فکتوریله؟به احتمال زیاد فاکتوریل هست
کلا اگر عبارتی نیاز به برابری تعداد عناصر داشته باشه معمولا مستقل از متنه چون باید به همون اندازه که یه x خونده میشه به همون اندازه هم y خونده بشه که چون ماشین متناهی حافظش بسیار ضعیفه نمیتونه اینو یادش بمونه و مجبوریم از ماشین قوی تری که قدرت یاد اوری بهتری ذاره استفاده کنیم که مثلا با یه پشته میتونیم اینو پیاده سازی کنیم.
ولی اگه اون فاکتوریل هستش،نمیدونم دقیقا
الان اگه فاکتوریل باشه میشه با پشته پیاده اش کرد ؟ میشه پیاده سازیشو توضیح بدید. من هر چی فکر کردم نتونستم چیزی واسش پیدا کنم
(۲۶ دى ۱۳۹۲ ۰۸:۳۹ ب.ظ)masoud67 نوشته شده توسط: به احتمال زیاد فاکتوریل هستسلام
الان اگه فاکتوریل باشه میشه با پشته پیاده اش کرد ؟ میشه پیاده سازیشو توضیح بدید. من هر چی فکر کردم نتونستم چیزی واسش پیدا کنم
دوست عزیز ما اگر حتی یه زبان داشته باشیم با یه الفبا یعنی [tex]\sum= \{a\}[/tex]
و زبانمون باشه [tex]L = \{a^{m}|m=factoriel\}[/tex]
این زبان نه منظمه نه مستقل از متن
از همین به نظرم بتونیم برداشت کنیم که این زبان هم مستقل از متن نیست
(۲۶ دى ۱۳۹۲ ۰۸:۳۹ ب.ظ)masoud67 نوشته شده توسط:(26 دى ۱۳۹۲ ۰۸:۲۸ ب.ظ)jahanmanesh نوشته شده توسط: اون فکتوریله؟به احتمال زیاد فاکتوریل هست
کلا اگر عبارتی نیاز به برابری تعداد عناصر داشته باشه معمولا مستقل از متنه چون باید به همون اندازه که یه x خونده میشه به همون اندازه هم y خونده بشه که چون ماشین متناهی حافظش بسیار ضعیفه نمیتونه اینو یادش بمونه و مجبوریم از ماشین قوی تری که قدرت یاد اوری بهتری ذاره استفاده کنیم که مثلا با یه پشته میتونیم اینو پیاده سازی کنیم.
ولی اگه اون فاکتوریل هستش،نمیدونم دقیقا
الان اگه فاکتوریل باشه میشه با پشته پیاده اش کرد ؟ میشه پیاده سازیشو توضیح بدید. من هر چی فکر کردم نتونستم چیزی واسش پیدا کنم
نمیدونم چجور حلش کرده مدرسان ولی به هر حال
میگه به ازای هر تعداد x، تعدادy هامون برابر فاکتوریل تعداد xها باشه
اگه فرض کنیم که این زبان مستقل از متنه،پس باید بتونیم براش یه ماشین پشته ای بدست بیاریم، خب برای هر x که میخونیم،باید x! توی پشته پوش کنیم،
از نظر من این زبان نباید مستقل از متن باشه به دو دلیل
۱/اینکه حافظه پشته محدوده و n! ، برای n = 7 ، باید بیشتر از ۵۰۰۰ حرف پوش کنه توی پشته در نتیجه ما به همچین پشته ای دسترسی نداریم
۲/من که نتونستم واسش یه پوش دان بکشم.
راستی بزار یه طور دیگه هم بررسیش کنیم. اگر از لم تزریق استفاده کنیم،m رو انتخاب کنیم و یه رشته ای که این زبان تولید میکنه رو بررسی کنیم بطوریکه طول رشته از m بیشتر باشه،واسه همین مثلا رشته
aaabbbbbb
۳!=۶
خب اگر رشته وسط رو برابر aabbbانتخاب کنیم و aa, bb رو افزایش بدیم،
W¹=aaaaabbbbbbbbb
طبق ادعای لم تزریقpumping رشته ی تولیدی باید عضو رشتهای تولید شده ی این زبان باشهاگر نبود یعنی مستقل از متن نیست
که ۵! برابر ۱۲۰ میشه یعنی برای ۵تا a باید۱۲۰تا b داشته باشیم،که میبینیم طبق مثال نقضی که اوردیم میتونیم بگیم این زبان مستقل از متن نیست
یادت باشه لم تزریق فقط میتونه ثابت کنه که یه زبان مستقل از متن نباشه،ولی نمیتونه ثابت کنه یه زبان مستقل از متنه (لم تزریق در زبان های مستقل از متن)
Sent from my GT-N5100 using Tapatalk HD
(۲۶ دى ۱۳۹۲ ۱۱:۴۳ ب.ظ)jahanmanesh نوشته شده توسط: راستی بزار یه طور دیگه هم بررسیش کنیم. اگر از لم تزریق استفاده کنیم،m رو انتخاب کنیم و یه رشته ای که این زبان تولید میکنه رو بررسی کنیم بطوریکه طول رشته از m بیشتر باشه،واسه همین مثلا رشته
aaabbbbbb
۳!=۶
خب اگر رشته وسط رو برابر aabbbانتخاب کنیم و aa, bb رو افزایش بدیم،
W¹=aaaaabbbbbbbbb
طبق ادعای لم تزریقpumping رشته ی تولیدی باید عضو رشتهای تولید شده ی این زبان باشهاگر نبود یعنی مستقل از متن نیست
Sent from my GT-N5100 using Tapatalk HD
سلام. اینی که مستقل از متن نیست شکی نیست. لم تزریق شما اشتباهه. طول رشته نباید محدود باشه.
احتمالاً منظور سوال از != نامساویه نه فاکتوریل. اگه کسی این رابطه رو ببینه و جواب آخر رو ندونه فاکتوریل درنظر میگیره.
(۲۷ دى ۱۳۹۲ ۰۱:۵۴ ق.ظ)Jooybari نوشته شده توسط:(26 دى ۱۳۹۲ ۱۱:۴۳ ب.ظ)jahanmanesh نوشته شده توسط: راستی بزار یه طور دیگه هم بررسیش کنیم. اگر از لم تزریق استفاده کنیم،m رو انتخاب کنیم و یه رشته ای که این زبان تولید میکنه رو بررسی کنیم بطوریکه طول رشته از m بیشتر باشه،واسه همین مثلا رشته
aaabbbbbb
۳!=۶
خب اگر رشته وسط رو برابر aabbbانتخاب کنیم و aa, bb رو افزایش بدیم،
W¹=aaaaabbbbbbbbb
طبق ادعای لم تزریقpumping رشته ی تولیدی باید عضو رشتهای تولید شده ی این زبان باشهاگر نبود یعنی مستقل از متن نیست
Sent from my GT-N5100 using Tapatalk HD
سلام. اینی که مستقل از متن نیست شکی نیست. لم تزریق شما اشتباهه. طول رشته نباید محدود باشه.
احتمالاً منظور سوال از != نامساویه نه فاکتوریل. اگه کسی این رابطه رو ببینه و جواب آخر رو ندونه فاکتوریل درنظر میگیره.
طول رشته رو باید بیشتر از m بگیریم .نگفتم محدود.هر چی m بود، بزرگترش میشه طول رشته دیگه.بین علما اختلاف افتاد :-D
اگر اونو نا مساوی بگیریم که زبان مسقل از متنه برادر من.
Sent from my GT-N5100 using Tapatalk HD
دست همگی درد نکنه. پس اینم یه اشتباه دیگه از مدرسان
مگر اینکه اون علامت فاکتوریل علامت نامساوی باشه که خیلی عجیبه
(۲۷ دى ۱۳۹۲ ۱۲:۲۹ ب.ظ)jahanmanesh نوشته شده توسط: طول رشته رو باید بیشتر از m بگیریم .نگفتم محدود.هر چی m بود، بزرگترش میشه طول رشته دیگه.بین علما اختلاف افتاد :-D
اگر اونو نا مساوی بگیریم که زبان مسقل از متنه برادر من.
Sent from my GT-N5100 using Tapatalk HD
آخه دیدم طول رشتتون محدود بود.
توی جوابیه نوشته بود مستقل از متنه.
(۲۷ دى ۱۳۹۲ ۰۳:۴۳ ب.ظ)Jooybari نوشته شده توسط:(27 دى ۱۳۹۲ ۱۲:۲۹ ب.ظ)jahanmanesh نوشته شده توسط: طول رشته رو باید بیشتر از m بگیریم .نگفتم محدود.هر چی m بود، بزرگترش میشه طول رشته دیگه.بین علما اختلاف افتاد :-D
اگر اونو نا مساوی بگیریم که زبان مسقل از متنه برادر من.
Sent from my GT-N5100 using Tapatalk HD
آخه دیدم طول رشتتون محدود بود.
توی جوابیه نوشته بود مستقل از متنه.
اره داشتم از برهان خلف استفاده میکردم.گفتم اگر فرض کنیم که مستقل از متن باشه ;-)
Sent from my GT-N5100 using Tapatalk HD