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

تشخیص زبان منظم و زبان مستقل از متن

ارسال:
  

monmon123 پرسیده:

تشخیص زبان منظم و زبان مستقل از متن

سلام چطوری زبا منظم رو از مستقل از متن تشخیص بدم؟
چطور بفهمم سوالم تکراری نیست که مطرحش نکنم؟

۲
ارسال:
  

Jooybari پاسخ داده:

RE: تشخیص زبان منظم و زبان مستقل از متن

سلام. زبان منظم زبانیه که بشه با یه ماشین متناهی یا گرامر منظم یا عبارت منظم تعریفش کرد. با لم تزریق میشه مشخص کرد که زبان منظمه یا نه.

ارسال:
  

Pakniat پاسخ داده:

RE: تشخیص زبان منظم و زبان مستقل از متن

(۰۵ مهر ۱۳۹۳ ۱۱:۱۹ ب.ظ)fatemeh69 نوشته شده توسط:  امیدوارم توضیحاتمو متوجه بشید
من فکر میکنم با لم تزریق زبان منظم میشه مستقل از متن نبودن زبان ها رو تشخیص داد ، می خواستم نظرتون رو در این مورد بدونم.
یافتن تمامی ارسال‌های این کاربر

ارسال:
  

fatemeh69 پاسخ داده:

RE: تشخیص زبان منظم و زبان مستقل از متن

(۰۷ مهر ۱۳۹۳ ۱۲:۵۴ ق.ظ)Pakniat نوشته شده توسط:  من فکر میکنم با لم تزریق زبان منظم میشه مستقل از متن نبودن زبان ها رو تشخیص داد ، می خواستم نظرتون رو در این مورد بدونم.

خیر این طور نیست با لم تزریق ویژه زبان های منظم تنها و تنها و تنها می توان نامنظم بودن یک زبانی را اثبات کرد
یافتن تمامی ارسال‌های این کاربر

ارسال:
  

Pakniat پاسخ داده:

RE: تشخیص زبان منظم و زبان مستقل از متن

(۰۷ مهر ۱۳۹۳ ۰۲:۳۶ ق.ظ)fatemeh69 نوشته شده توسط:  
(07 مهر ۱۳۹۳ ۱۲:۵۴ ق.ظ)Pakniat نوشته شده توسط:  من فکر میکنم با لم تزریق زبان منظم میشه مستقل از متن نبودن زبان ها رو تشخیص داد ، می خواستم نظرتون رو در این مورد بدونم.

خیر این طور نیست با لم تزریق ویژه زبان های منظم تنها و تنها و تنها می توان نامنظم بودن یک زبانی را اثبات کرد

مثال نقض دارید ؟
یافتن تمامی ارسال‌های این کاربر

ارسال:
  

fatemeh69 پاسخ داده:

RE: تشخیص زبان منظم و زبان مستقل از متن

(۰۷ مهر ۱۳۹۳ ۱۱:۳۴ ب.ظ)Pakniat نوشته شده توسط:  
(07 مهر ۱۳۹۳ ۰۲:۳۶ ق.ظ)fatemeh69 نوشته شده توسط:  
(07 مهر ۱۳۹۳ ۱۲:۵۴ ق.ظ)Pakniat نوشته شده توسط:  من فکر میکنم با لم تزریق زبان منظم میشه مستقل از متن نبودن زبان ها رو تشخیص داد ، می خواستم نظرتون رو در این مورد بدونم.

خیر این طور نیست با لم تزریق ویژه زبان های منظم تنها و تنها و تنها می توان نامنظم بودن یک زبانی را اثبات کرد

مثال نقض دارید ؟

برای چی مثال نقض دارم یا نه؟
من می گم لم تزریق زبان های منظم اصولا به هدف اثبات نامنظمی زبان های نامنظم طراحی شده و کاربرد دیگری ندارد
شما می گید خیر می شه باهاش مستقل از متن نبودن رو هم تشخیص داد
اگر حرفتون درسته براش مثال بیارید مثلا یه زبان مستقل از متن [tex]L=\{a^nb^n,\: n>=0\: \}[/tex] رو بدیم به لم تزریق واسمون اثبات می کنه که نامنظمه و اگر زبان غیر مستقل از متن [tex]L=\{a^nb^nc^n,\: n>=0\: \}[/tex] رو هم به لم تزریق بدهیم باز برامون ثابت می کنه که اینزبان نامنظمه و واسه لم تزریق روند کار روی این دو زبان یکسانه و واسش مهم نیست که زبان نامنظم ما آیا مستقل از متن هم هیت یا خیر مهم اینه که نامنظمه.
نمی دونم فرضیه ذهنی شما چیه و چه دلیلایی واسش دارید اگه دلایلتونو بنویسید و با چند مثال بیان کنید بیشتر متوجه منظورتون می شم
یافتن تمامی ارسال‌های این کاربر

ارسال:
  

Pakniat پاسخ داده:

RE: تشخیص زبان منظم و زبان مستقل از متن

(۰۸ مهر ۱۳۹۳ ۰۱:۳۴ ق.ظ)fatemeh69 نوشته شده توسط:  
(07 مهر ۱۳۹۳ ۱۱:۳۴ ب.ظ)Pakniat نوشته شده توسط:  
(07 مهر ۱۳۹۳ ۰۲:۳۶ ق.ظ)fatemeh69 نوشته شده توسط:  
(07 مهر ۱۳۹۳ ۱۲:۵۴ ق.ظ)Pakniat نوشته شده توسط:  من فکر میکنم با لم تزریق زبان منظم میشه مستقل از متن نبودن زبان ها رو تشخیص داد ، می خواستم نظرتون رو در این مورد بدونم.

خیر این طور نیست با لم تزریق ویژه زبان های منظم تنها و تنها و تنها می توان نامنظم بودن یک زبانی را اثبات کرد

مثال نقض دارید ؟

برای چی مثال نقض دارم یا نه؟
من می گم لم تزریق زبان های منظم اصولا به هدف اثبات نامنظمی زبان های نامنظم طراحی شده و کاربرد دیگری ندارد
شما می گید خیر می شه باهاش مستقل از متن نبودن رو هم تشخیص داد
اگر حرفتون درسته براش مثال بیارید مثلا یه زبان مستقل از متن [tex]L=\{a^nb^n,\: n>=0\: \}[/tex] رو بدیم به لم تزریق واسمون اثبات می کنه که نامنظمه و اگر زبان غیر مستقل از متن [tex]L=\{a^nb^nc^n,\: n>=0\: \}[/tex] رو هم به لم تزریق بدهیم باز برامون ثابت می کنه که اینزبان نامنظمه و واسه لم تزریق روند کار روی این دو زبان یکسانه و واسش مهم نیست که زبان نامنظم ما آیا مستقل از متن هم هیت یا خیر مهم اینه که نامنظمه.
نمی دونم فرضیه ذهنی شما چیه و چه دلیلایی واسش دارید اگه دلایلتونو بنویسید و با چند مثال بیان کنید بیشتر متوجه منظورتون می شم

من فکر می کنم لم pumping ابزاری است که برای اثبات : نامنظم بودن ، مستقل از متن بودن و غیر خطی بودن میشه استفاده کرد ، در زبان های نامنظم به صورت dfa و در مستقل از متن بودن به صورت گرامر مستقل از متن بیان میشه ، مثلا [tex]w.w^R[/tex]رو می تونید اثبات کنید نامنظمه ، اما مستقل از متن هست چون براش گرامر داریم اما [tex]a^nb^nc^n[/tex] رو با همون لم تزریق زبان نامنظم میشه اثبات کرد مستقل از متن نیست چون براش نه گرامر و نه pda داریم اما با یک i میشه خارج کرد.
در مجموع به دنبال دلیلی برای قوی تر بودن لم مستقل از متن نسبت به نامنظم می گردم و فکر می کنم لم مستقل از متن بیان دیگه ای از لم نامنظم هست !
یافتن تمامی ارسال‌های این کاربر

ارسال:
  

fatemeh69 پاسخ داده:

RE: تشخیص زبان منظم و زبان مستقل از متن

(۱۰ مهر ۱۳۹۳ ۰۱:۰۱ ق.ظ)Pakniat نوشته شده توسط:  من فکر می کنم لم pumping ابزاری است که برای اثبات : نامنظم بودن ، مستقل از متن بودن و غیر خطی بودن میشه استفاده کرد ، در زبان های نامنظم به صورت dfa و در مستقل از متن بودن به صورت گرامر مستقل از متن بیان میشه ، مثلا [tex]w.w^R[/tex]رو می تونید اثبات کنید نامنظمه ، اما مستقل از متن هست چون براش گرامر داریم اما [tex]a^nb^nc^n[/tex] رو با همون لم تزریق زبان نامنظم میشه اثبات کرد مستقل از متن نیست چون براش نه گرامر و نه pda داریم اما با یک i میشه خارج کرد.
در مجموع به دنبال دلیلی برای قوی تر بودن لم مستقل از متن نسبت به نامنظم می گردم و فکر می کنم لم مستقل از متن بیان دیگه ای از لم نامنظم هست !

من فکر می کنم شما چند مفهوم رو باهم مخلوط کرده اید
این مطالب رو می گم صرفا برای این که پایه های ذهنی م رو بیان کنم
اولا ما سه لم تزریق داریم لم تزریق ویژه زبان های منظم - لم تزریق ویژه زبان های مستقل از متن- لم تزرریق ویژه زبان های خطی
نظریه درسی با پایخه ی ریاضی است یعنی اگر جدا از کنکور به آن نگاه کنیم هر چیزی را باید اثبات کرد
گاهی ما می گوییم فلان منظم است به ما می گویند این حرفت را اثبات کن ما فورا برای آن زبان dfa می کشیم یا گرامر منظم می دهیم یا با عبارت منظم بیان می کنیم می گوییم بفرما این هم اثباتش
گاهی ما می گوییم فلان زبان نامنظم است می گویند اثبات کن ما می گوییم خب هیچ dfa ای برای آن وجود ندارد
می گویند:از کجا معلوم؟! شاید برای آن dfa ای باشد اما تو نتواسته ای پیدا کنی اثبات کن که هیچ dfa ای برای آن وجود ندارد

این جاست که لم تزریق به کار ما می آۀید
یعنی لم تزریق زبان های منظم اثباتی ریاضی محور برای نامنظم بودن یک زبان نامنظم است
و لم تزریق زبان های مستقل از متنی اثباتی برای مستقل از متن نبودن یک زبان غیر مستقل از متن است
و لم تزریق مخصوص زبان های خطی اثباتی برای غیر خطی بودن یک زبان غیر خطی است.

حالا طبق طبقه بندی چامسکی کوچکترین مجموعه زبان ها منظم هیتند و که زیر مجموعه ی مجوعه ی بزرگتری به نام زبان های مستقل از متن هستند و آن ها زیر مجموعه ی مجوعه ی بزرگتری یعنی زبان های حساس به متن هستند که خود زیر مجوعه ی مجوعه ی بزرگتری به نام زبان های نوع صفر (r.e) هستند.

خب این یعنی اگر با لم تزریق اثبات کردیم که زبانی منظم نیست پس این زبان خارج از مجوعه ی زبان های منظم قرار می گیرید (و معلوم نیست که در مجموعه ی مستقل از متن باشد یا حساس به متن یا نوع صفر یا حتی خارج از آن.

پس زبانی که خارج از مجموعه ی منظم است معلوم نیست که آیا مستقل از متن هست یا نه


لم تزریق مخصوص زبان های منظم ، نامنظم بودن یک زبان منظم را اثبات می کند (یعنی اثبات می کند برای این زبان هیچ dfa یا گرامر منظم یا عبارت منظمی وجود ندارد) پس عضو مجموعه ی زبان های منظم نیست حالا این که عضو کدام مجوعه است معلوم نیست.


برای اثبات منظم بودن از dfa- گرامرمنظم یا عبارت منظم استفاده می کنیم
برای اثبات غیر منظم بودن از لم تزریق مخصوص زبان های منظم استفاده می کنیم

برای اثبات مستقل از متن بودن یک زبان از pda- گرامر مستقل از متن استفاده می کنیم
برای اثبات مستقل از متن نبودن از لم تزریق زبان های مستقل از متن استفاده می کنیم

برای اثبات خطی بودن زبانی از گرامر خطی استفاده می کنیم
برای اثبات غیر خطی بودن زبانی از لم تزری۴ق مخصوص زبان های غیر خطی استفاده می کنیم

هر ابزاری را بهر کاری ساخته اند!
یافتن تمامی ارسال‌های این کاربر

۱
ارسال: #۱۰
  

monmon123 پاسخ داده:

RE: تشخیص زبان منظم و زبان مستقل از متن

مشکل من اینه که هر چی از روی کتابا میخونم از لم تزریق سردر نمیارم؟؟؟میشه یادم بدین لم تزریقو؟؟؟



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  کدام زبان برای هوش مصنوعی بهتر است؟ فرق بین زبان های هوش مصنوعی چیست؟ azam2075 ۳ ۶,۰۵۹ ۱۴ مهر ۱۴۰۰ ۰۷:۲۱ ب.ظ
آخرین ارسال: علیصا
  تشخیص گوگل مپس با Live View AR برای مکان دقیق elecomco ۱ ۴,۲۵۷ ۰۵ بهمن ۱۳۹۹ ۰۲:۴۹ ب.ظ
آخرین ارسال: kooshaideal1
  متن به هم ریخته در نرم افزار Notepad HAMID3F ۱۵ ۲۳,۰۲۷ ۱۷ شهریور ۱۳۹۹ ۰۸:۲۶ ق.ظ
آخرین ارسال: rezasedghi100
  منبع متناسب با شرایط کسانی که قصد تغییر رشته دارند MrBob ۷ ۶,۱۶۳ ۱۶ آبان ۱۳۹۸ ۱۱:۳۵ ب.ظ
آخرین ارسال: marvelous
  گرامر منظم Sanazzz ۶ ۷,۰۴۱ ۳۱ اردیبهشت ۱۳۹۸ ۰۴:۳۲ ب.ظ
آخرین ارسال: Sanazzz
  گرامر مستقل از متن Sanazzz ۴ ۵,۵۲۲ ۱۲ دى ۱۳۹۷ ۰۹:۵۹ ب.ظ
آخرین ارسال: Sanazzz
  متن ایمیل برای نویسنده مقاله Iran2014 ۲ ۳,۵۳۳ ۱۰ مهر ۱۳۹۷ ۰۹:۱۵ ب.ظ
آخرین ارسال: Iran2014
  تشخیص خطا در تحلیلگر لغوی یا نحوی zahra2012 ۵ ۸,۲۹۳ ۲۶ مرداد ۱۳۹۷ ۰۴:۲۹ ب.ظ
آخرین ارسال: tohid.salmani
  تشخیص کاراکتر با شبکه عصبی safoora s ۴ ۴,۲۳۲ ۱۸ مرداد ۱۳۹۷ ۱۰:۵۰ ب.ظ
آخرین ارسال: kilookiloo
Photo ساده سازی عبارت منظم etedadi ۰ ۲,۱۱۴ ۱۶ خرداد ۱۳۹۷ ۰۷:۰۴ ب.ظ
آخرین ارسال: etedadi

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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