با سلام
در مورد زبان های به فرم uww^ru اگر همه رشته ها عضو یه مجموعه الفبا باشند که معمولا از یه رشته و معکوسش و چند رشته دیگه که بهش الحاق شدن تشکیل شده من هر چی سعی کردم نتونستم راهی برای تشخیص نوع زبان این مدل از زبانها پیدا کنم.
لطفا راهنمایی کنید که چطور میشه نوعشون رو تشخیص داد ؟
سلام. برای تشخیص مستقل بودن یک زبان، یک راه ساده این هست که اونایی که به هم وابسته هستند رو با یک خط به هم متصل کنیم، اگه خطوطی که بین وابسته ها همدیگر رو قطع کردن، این زبان مستقل از متن نیست. مثلا تو همین مثالی که نوشتی دوتا u(اولی و آخری) به هم وابسته هستن و w و معکوسw بهم وابسته هستن اما این خطوط یکدیگر رو قطع نمی کنن،
پس مستقل از متن هست. توجه کن که مثلا a^i b^j c^i c^j می تونیم جای دوتا c آخری رو عوض کنیم. در هرصورت قسمت مهمی که باید بهش توجه بشه، شرط وابستگی بین عنصرها هست. و البته میشه با لم تزریق هم نامنظم یا نامستقل بودن زبان ها رو اثبات کرد.
در کتاب سپاهان در سوالی این زبان اومده و زبان مستقل از متن رو خواسته ولی جواب رو گزینه دیگه ای زده! در بعضی کتابها گفته که اگر به نوعی رشته ها به هم وصل شوند که نتوان وابستگی را تشخیص داد منظم و مستقل از متن هم هست.
در مثالی که گفتم ظاهرا وجود u اول باید سبب عدم شناسایی w شود و به نظر می رسد زبان منظم باشد ولی گویا اینگونه نیست! و من دلیلش را نمی فهمم!
(17 دى 1391 02:04 ب.ظ)mostafa272 نوشته شده توسط: [ -> ]در کتاب سپاهان در سوالی این زبان اومده و زبان مستقل از متن رو خواسته ولی جواب رو گزینه دیگه ای زده! در بعضی کتابها گفته که اگر به نوعی رشته ها به هم وصل شوند که نتوان وابستگی را تشخیص داد منظم و مستقل از متن هم هست.
در مثالی که گفتم ظاهرا وجود u اول باید سبب عدم شناسایی w شود و به نظر می رسد زبان منظم باشد ولی گویا اینگونه نیست! و من دلیلش را نمی فهمم!
اگه یکی از این u ها نبود منظم میشد (( u w wr : معادله سیگما *)) ((w wr u : معادله سیگما *)) .
مستقل از متن هم نیست به خاطر u اول و آخرش چون نمیشه با پشته ساختش
(17 دى 1391 05:57 ب.ظ)svk7 نوشته شده توسط: [ -> ] (17 دى 1391 02:04 ب.ظ)mostafa272 نوشته شده توسط: [ -> ]در کتاب سپاهان در سوالی این زبان اومده و زبان مستقل از متن رو خواسته ولی جواب رو گزینه دیگه ای زده! در بعضی کتابها گفته که اگر به نوعی رشته ها به هم وصل شوند که نتوان وابستگی را تشخیص داد منظم و مستقل از متن هم هست.
در مثالی که گفتم ظاهرا وجود u اول باید سبب عدم شناسایی w شود و به نظر می رسد زبان منظم باشد ولی گویا اینگونه نیست! و من دلیلش را نمی فهمم!
اگه یکی از این u ها نبود منظم میشد (( u w wr : معادله سیگما *)) ((w wr u : معادله سیگما *)) .
پس اگر بشه رشته u رو از w تفکیک کرد پس اون وقت مستقل از متن نیست و وابسته به متنه !چون با فرض خواندن u و قرار دادن مقادیری برای شناسایی در پشته wو w^r رو میشه تشخیص داد ولی با خالی کردن پشته نمیشه مجددا u رو شناسایی کرد و این زبان وابسته به متنه(ولی اگر u^r بود اونوقت مستقل از متن میشد) درسته؟
(17 دى 1391 06:52 ب.ظ)mostafa272 نوشته شده توسط: [ -> ] (17 دى 1391 05:57 ب.ظ)svk7 نوشته شده توسط: [ -> ] (17 دى 1391 02:04 ب.ظ)mostafa272 نوشته شده توسط: [ -> ]در کتاب سپاهان در سوالی این زبان اومده و زبان مستقل از متن رو خواسته ولی جواب رو گزینه دیگه ای زده! در بعضی کتابها گفته که اگر به نوعی رشته ها به هم وصل شوند که نتوان وابستگی را تشخیص داد منظم و مستقل از متن هم هست.
در مثالی که گفتم ظاهرا وجود u اول باید سبب عدم شناسایی w شود و به نظر می رسد زبان منظم باشد ولی گویا اینگونه نیست! و من دلیلش را نمی فهمم!
اگه یکی از این u ها نبود منظم میشد (( u w wr : معادله سیگما *)) ((w wr u : معادله سیگما *)) .
پس اگر بشه رشته u رو از w تفکیک کرد پس اون وقت مستقل از متن نیست و وابسته به متنه !چون با فرض خواندن u و قرار دادن مقادیری برای شناسایی در پشته wو w^r رو میشه تشخیص داد ولی با خالی کردن پشته نمیشه مجددا u رو شناسایی کرد و این زبان وابسته به متنه(ولی اگر u^r بود اونوقت مستقل از متن میشد) درسته؟
ww مستقل از متن نیس چون نمیشه با پشته پیاده اش کرد
(17 دى 1391 01:17 ب.ظ)azad_ahmadi نوشته شده توسط: [ -> ]سلام. برای تشخیص مستقل بودن یک زبان، یک راه ساده این هست که اونایی که به هم وابسته هستند رو با یک خط به هم متصل کنیم، اگه خطوطی که بین وابسته ها همدیگر رو قطع کردن، این زبان مستقل از متن نیست. مثلا تو همین مثالی که نوشتی دوتا u(اولی و آخری) به هم وابسته هستن و w و معکوسw بهم وابسته هستن اما این خطوط یکدیگر رو قطع نمی کنن،
پس مستقل از متن هست. توجه کن که مثلا a^i b^j c^i c^j می تونیم جای دوتا c آخری رو عوض کنیم. در هرصورت قسمت مهمی که باید بهش توجه بشه، شرط وابستگی بین عنصرها هست. و البته میشه با لم تزریق هم نامنظم یا نامستقل بودن زبان ها رو اثبات کرد.
این تو همه زبانها صادق نیست مثلا تو همین u w wr u ،چون نمیشه u اول و آخرو باپشته تشخیص داد.