زمان کنونی: ۲۹ خرداد ۱۳۹۸, ۱۱:۲۰ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

مشکل در تشخیص ویژگی های زبان مستقل از متن قطعی

ارسال:
  

mostafa2012 پرسیده:

مشکل در تشخیص ویژگی های زبان مستقل از متن قطعی

باسلام
ببخشید من ویژگی های زبان مستقل از متن قطعی رو نمیدونم ... کتاب پوران هم گفته مراجعه شود به کتاب مرجع!
بسته بودن یعنی چه؟
بیزحمت به ترتیب توضیح دهید:
[تصویر:  329269_cvts31j8lsiurtupf6te.png]

۳
ارسال:
  

ana9940 پاسخ داده:

RE: مشکل در تشخیص ویژگی های زبان مستقل از متن قطعی

وقتی گفته میشه که مثلا زبان های منظم تحت اشتراک بسته هستند، یعنی اینکه اگه دو زبان منظم L1 و L2 داشته باشیم اشتراک اون دو هم منظم هست.
زبان های مستقل از متن قطعی فقط روی عملگرهای مکمل ،همریختی معکوس و اشتراک منظم بسته هستند.
توی این جدول همه موارد جامع و کامل هست:
[تصویر:  329287_ton6m71v5wnjmtgklsr6.png]

ارسال:
  

mostafa2012 پاسخ داده:

RE: مشکل در تشخیص ویژگی های زبان مستقل از متن قطعی

(۰۴ بهمن ۱۳۹۳ ۱۲:۴۸ ق.ظ)ana9940 نوشته شده توسط:  وقتی گفته میشه که مثلا زبان های منظم تحت اشتراک بسته هستند، یعنی اینکه اگه دو زبان منظم L1 و L2 داشته باشیم اشتراک اون دو هم منظم هست.
زبان های مستقل از متن قطعی فقط روی عملگرهای مکمل ،همریختی معکوس و اشتراک منظم بسته هستند.
توی این جدول همه موارد جامع و کامل هست:
[تصویر:  329287_ton6m71v5wnjmtgklsr6.png]

سلام
باتشکر از توضیحاتتون!Idea

بیزحمت یک خورده در خصوص موارد زیر که توی جدول نوشته شده توضیح بدید:
- بستار ستاره (منظورش همون cleen star یعنی مثلا *a خب چی میخواد بگه => میخواد بگه *(زبان منظم) هم بسته است؟
- هم ریختی
- هم ریختی بدون لاندا
- هم ریختی معکوس
- اشتراک منظم .... به اشتراک خالی فرق میکنه؟؟

باتشکر
موفق وموید!
التماس دعا
یافتن تمامی ارسال‌های این کاربر

ارسال:
  

ana9940 پاسخ داده:

RE: مشکل در تشخیص ویژگی های زبان مستقل از متن قطعی

(۰۴ بهمن ۱۳۹۳ ۱۲:۳۴ ب.ظ)mostafa2012 نوشته شده توسط:  - بستار ستاره (منظورش همون cleen star یعنی مثلا *a خب چی میخواد بگه => میخواد بگه *(زبان منظم) هم بسته است؟
- هم ریختی
- هم ریختی بدون لاندا
- هم ریختی معکوس
- اشتراک منظم .... به اشتراک خالی فرق میکنه؟؟
اول اشترک منظم رو میگم که خیلی خیلی مهمه. اشتراک منظم یعنی اشتراک یک زبان با یک زبان منظم. مثلا زبان L1 را داریم که میدونیم منظمه و زبان L2 هم داریم که نمی دونیم مستقل از متن هست یا نه. حالا اگه اشتراک این دو زبان ، یه زبان مستقل از متن رو بده، پس L2 هم مستقل از متن بوده. این جوری هم میشه گفت : اشتراک یک زبان مستقل از متن با یک زبان منظم ، حتما مستقل از متن است، به عبارتی زبان های مستقل از متن(چه قطعی و چه غیرقطعی) تحت عمل اشتراک منظم ، بسته هستند.
(یه سری از تست ها رو با همین اشتراک منظم میشه راحت حل کرد، دست کمش نگیرید!)
بستار ستاره هم همونی هست که خودتون میگی، مثلا زبان L1 رو داریم و میدونیم منظمه، طبق بسته بودن زبان های منظم بر روی بستار ستاره ، پس [tex](L1)^{\ast}[/tex] هم منظمه. یه جوراییه بدیهی حساب میشه. مثلا اگه dfa اون زبان منظم رو داشته باشیم، حالت آغازین رو اگه پایانی کنیم رشته لاندا رو می پذیره، از آخرین حالت(ها) هم باید به حالت آغازین یه حرکت داشته باشیم که عمل ستاره رو شبیه سازی کنه.
همریختی هم به نظرم همون همومورفیسم هست که این جا گفتم بهتون:

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

همریختی معکوس و بدون لاندا رو راستش نمیدونم قضیه اش چیه و چه لزومی داشته توی جدول آورده، خب همریختی رو یه کم خاص تر کرده، حالا اگه جایی یه مثالی ازشون دیدم میذارم حتما.
یافتن تمامی ارسال‌های این کاربر

ارسال:
  

mostafa2012 پاسخ داده:

RE: مشکل در تشخیص ویژگی های زبان مستقل از متن قطعی

(۰۵ بهمن ۱۳۹۳ ۱۰:۳۲ ب.ظ)ana9940 نوشته شده توسط:  
(04 بهمن ۱۳۹۳ ۱۲:۳۴ ب.ظ)mostafa2012 نوشته شده توسط:  - بستار ستاره (منظورش همون cleen star یعنی مثلا *a خب چی میخواد بگه => میخواد بگه *(زبان منظم) هم بسته است؟
- هم ریختی
- هم ریختی بدون لاندا
- هم ریختی معکوس
- اشتراک منظم .... به اشتراک خالی فرق میکنه؟؟
اول اشترک منظم رو میگم که خیلی خیلی مهمه. اشتراک منظم یعنی اشتراک یک زبان با یک زبان منظم. مثلا زبان L1 را داریم که میدونیم منظمه و زبان L2 هم داریم که نمی دونیم مستقل از متن هست یا نه. حالا اگه اشتراک این دو زبان ، یه زبان مستقل از متن رو بده، پس L2 هم مستقل از متن بوده. این جوری هم میشه گفت : اشتراک یک زبان مستقل از متن با یک زبان منظم ، حتما مستقل از متن است، به عبارتی زبان های مستقل از متن(چه قطعی و چه غیرقطعی) تحت عمل اشتراک منظم ، بسته هستند.
(یه سری از تست ها رو با همین اشتراک منظم میشه راحت حل کرد، دست کمش نگیرید!)
بستار ستاره هم همونی هست که خودتون میگی، مثلا زبان L1 رو داریم و میدونیم منظمه، طبق بسته بودن زبان های منظم بر روی بستار ستاره ، پس [tex](L1)^{\ast}[/tex] هم منظمه. یه جوراییه بدیهی حساب میشه. مثلا اگه dfa اون زبان منظم رو داشته باشیم، حالت آغازین رو اگه پایانی کنیم رشته لاندا رو می پذیره، از آخرین حالت(ها) هم باید به حالت آغازین یه حرکت داشته باشیم که عمل ستاره رو شبیه سازی کنه.
همریختی هم به نظرم همون همومورفیسم هست که این جا گفتم بهتون:

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

همریختی معکوس و بدون لاندا رو راستش نمیدونم قضیه اش چیه و چه لزومی داشته توی جدول آورده، خب همریختی رو یه کم خاص تر کرده، حالا اگه جایی یه مثالی ازشون دیدم میذارم حتما.

باسلام و تشکر فراوان!
یافتن تمامی ارسال‌های این کاربر



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  چرا مستقل از متنه؟ Wa^nb^mW^R poldasht ۱۱ ۳,۲۵۴ ۱۴ بهمن ۱۳۹۳ ۰۹:۱۰ ب.ظ
آخرین ارسال: ss.hoseini
  خواص مستقل از متن maryam.roshan ۳ ۲,۱۸۰ ۱۲ بهمن ۱۳۹۳ ۱۱:۰۱ ب.ظ
آخرین ارسال: fatemeh69
  تشخیص قطعی بودن ۴ زبان مستقل از متن MR.oracle ۹ ۳,۷۲۳ ۱۲ بهمن ۱۳۹۳ ۱۲:۲۳ ب.ظ
آخرین ارسال: ریحان
  چرا عکس نقیض لم تزریق مستقل از متن نشان دهنده نامنظم بودنه؟ ریحان ۷ ۲,۲۳۴ ۱۲ بهمن ۱۳۹۳ ۱۲:۱۳ ب.ظ
آخرین ارسال: ریحان
Question تشخیص زبان های مستقل از متن Ametrine ۹ ۴,۳۶۶ ۱۲ بهمن ۱۳۹۳ ۰۱:۵۱ ق.ظ
آخرین ارسال: ریحان
  چرا n(a)=!n(b) مستقل از متن قطعیه؟ ریحان ۸ ۲,۴۰۷ ۱۱ بهمن ۱۳۹۳ ۱۱:۰۲ ب.ظ
آخرین ارسال: ریحان
  آیا این زبان مستقل از متن است؟؟ K<=max(i,j) Imankhani ۸ ۲,۸۰۲ ۱۱ بهمن ۱۳۹۳ ۰۷:۴۷ ب.ظ
آخرین ارسال: ریحان
  تشخیص اجتماع و اشتراک یک زبان جساس به متن با مستقل از متن یا منظم maryam.roshan ۱ ۱,۵۲۸ ۱۱ بهمن ۱۳۹۳ ۱۲:۴۳ ق.ظ
آخرین ارسال: fatemeh69
  نحوه تشخیص زبان های خطی arefeh.hp ۷ ۴,۵۹۶ ۰۹ بهمن ۱۳۹۳ ۰۱:۰۵ ق.ظ
آخرین ارسال: nazanin2020
  آیا مستقل از متن قطعی است؟${a^mb^mc^n:0≤m≤n≤۲m\}$ archer22 ۳ ۱,۷۸۱ ۰۷ بهمن ۱۳۹۳ ۰۹:۰۲ ب.ظ
آخرین ارسال: Hamid_0311

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close