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

سوال در مورد زبان منظم، مستقل از متن

ارسال:
  

ida_isp پرسیده:

سوال در مورد زبان منظم، مستقل از متن

سلام من یه اشکال اســـــــــاسی نظریه دارم. وقتی یه تست میدن و میگن کدوم یک از زبان های زیر منظم است، منظم نیست، مستقل از متن هست، نیست و.... باید چه طوری تشخیص داد؟؟؟؟؟Huh
فقط میدونم اگر متناهی باشه منظمه!!
کلا کسی میتونه یه جمعبندی از این نکته‌ها یا تکنیک هایی که بشه باهاهش تشخیص داد زبان منظمه، مستقل از متنه و... بکنه؟!
ممنون

۰
ارسال:
  

ida_isp پاسخ داده:

سوال در مورد زبان منظم، مستقل از متن

۱۳ نفر بازدید کردند اما ۱ نفر هم جوابمو نداده....مرسی!Smile

۰
ارسال:
  

ف.ش پاسخ داده:

سوال در مورد زبان منظم، مستقل از متن

این چیزی که میگم واسه اثبات نیست ولی واسه خودتون توی تستها میتونید استفاده کنید.

واسه اینکه بگیم منظم نیست باید ببینیم نیاز به حافظه هست یا نه مثلا اگر به شما بگن زبان a^n b^n منظمه شما سعی میکنید واسش dfa بکشید اما می بینید که کشیدن dfa ممکن نیست چون شما نیاز دارید که بدونید چقدر a خوندید که به همون تعداد b بخونید.پس منظم نیست.

اگر بشه با پشته پیاده سازیش کرد یا واسش گرامر مستقل از متن نوشت مستقل از متنه.
مثلا همون گرامری که نشد واسش dfa کشید میشه راحت واسش گرامر نوشت یا اینکه گفت توی پشته به ازای هر b که میخونیم یه a خط میزنیم و ..... (یه ایده کلی که بدونیم میشه با پشته پیاده سازی کرد)

میتونید به قسمت مباحث داغ نظریه برید و نمونه سوالات مربوط به زبانهای منظم و مستقل از متن رو بررسی کنید.
نگران نباشید با حل چند تست دستتون میاد.

۰
ارسال:
  

farazin پاسخ داده:

RE: سوال در مورد زبان منظم، مستقل از متن

کلا این و یادتون باشه که زبان های منظم نیاز به حافظه ندارن.مثلا اون مثالی که آفاق خانوم فرمودن ما برای تولید یک رشته از این زبان‌، چون تعداد a‌ها و b‌ها با هم برابره پس وقتی n تا a تولید می کنیم باید n تا هم b تولید بکنیم که این نیاز به حافظه داره پس منظم نیست. ولی می تونیم این زبان و با یک ماشین pda یعنی یه دونه پشته پیاده سازی بکنیم.به تعداد a‌ها push می کنیم و به تعداد b‌ها pop.پس تونستیم با یه دونه پشته پیاده سازی بکنیم بنابراین CF یا همون مستقل از متن هستش. ولی اگه مثلا a^n b^n c^n بود می بینیم که نمی تونیم با یدونه پشته پیاده سازی بکنیم .بنابراین مثلا اگه n=2 باشه دو تا پشته نیاز داریم که می تونیم تو پشته اول دو تا a رو push بکنیم.بعد دو تا b رو تو پشته اول pop می کنیم و همزمان تو پشته دوم push می کنیم.بعدش به تعداد c هامون که دو تا هستش از پشته دوم pop می کنیم.می بینیم که دو تا پشته خالی شدن.پس این زبان چون به دو تا پشته نیاز داره یعنی ۲-pda هستش بنابراین CS یا وابسته به متن هستش
مشاهده‌ی وب‌سایت کاربر

۰
ارسال:
  

ida_isp پاسخ داده:

سوال در مورد زبان منظم، مستقل از متن

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

ارسال:
  

farazin پاسخ داده:

RE: سوال در مورد زبان منظم، مستقل از متن

(۱۸ آذر ۱۳۹۰ ۱۲:۲۷ ب.ظ)ida_isp نوشته شده توسط:  خیلی متشکر دوستان
فقط منظور از حافظه مثلا چیزی مثل پشته است؟ یا به اصطلاح مثلا یه جایی که بشه توش نوشت که مثلا چندتا a تا الآن دیده؟!

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

۰
ارسال:
  

Ali-B پاسخ داده:

RE: سوال در مورد زبان منظم، مستقل از متن

امروز داشتم یه نگاهی به جزوه باغبانی می‌کردم، (جزوه‌ای که بچه‌ها برای دانلود گذاشته بودن.) تو عکسی که گذاشتم، منظورش از حافظه متناهی چیه؟
من که فکر میکنم مدرس اینجا دچار اشتباه شده، حافظه، حافظه است، و اگه به حافظه نیاز باشه، زبان منظم نیست.


ارسال:
  

hadi_m پاسخ داده:

RE: سوال در مورد زبان منظم، مستقل از متن

(۲۴ آذر ۱۳۹۰ ۰۴:۴۳ ب.ظ)ali.alhambra نوشته شده توسط:  امروز داشتم یه نگاهی به جزوه باغبانی می‌کردم، (جزوه‌ای که بچه‌ها برای دانلود گذاشته بودن.) تو عکسی که گذاشتم، منظورش از حافظه متناهی چیه؟
من که فکر میکنم مدرس اینجا دچار اشتباه شده، حافظه، حافظه است، و اگه به حافظه نیاز باشه، زبان منظم نیست.
سلاام
داشتم کامنت دوستان رو مرور میکردم گفتم خالی از لطف نباشه یه سری توضیحات تکمیلی در باب تکمل توضیح دوستان بدم .
اولا جزوه یی که نوشتید کاملا درسته اما چطور!!!
یه نگرش نادرست وجود داره که میگن اگر زبانی حافظه خواست منظم نیست ..این نحو بیان اشتباهست و اینگونه نیست در واقع ما در زبان منظم هم حافظه داریم اما این حافظه محدود هست و با حالتها شبیه سازی میشه وقتی از یک حالت به حالت دیگر میرویم یعنی داریم گذشته رشته رو به خاطر میسپاریم و این یعنی حافظه .
مثلا زبان [tex]a^{1000000}b^{1000000}[/tex]

یک زبان منظم هست و ماشین منظم این زبان [tex]2 * 1000000[/tex] حالت دارد .در واقع همانطور که واقف هستید ما این حافظه رو با حالتها ایجاد کردیم ووقتی از یکی حالت به حالت دیگر میرویم گذشته شته رو به خاطر میسپاریم .
من عمدا تعداد ارقام رو زیاد وارد کردم چون میخوام یه نتیجه گیری کنم .
ببنید اگر ما نیاز به حافظه محدود و مشخص داشته باشیم انوقت میوانیم این حافظه محدود را با حالتها شبیه سازی کنیم و زبان منظم خواهد بود اگر در این مثال یک ملیارد یا بیشتر هم می بود باز هم منظم هست .
اما در رشته [tex]a^{n}b^{n}[/tex]
از انجا که مقدار [tex]n[/tex]
مشخص نیست لذا نمی توانیم هیچ تصمیم گیری در رابطه با اینکه رشته ما به چقدر حافظه نیاز دارد داشته باشیم لذاا این زبان نیاز به حافظه نامشخص و به عبارتی نامحدود دارد که قابل شبیه سازی به وسیله حالتها نیست
نتیجه گیری:
پس ما در زبان منظم هم حافظه داریم اما حافظه محدود و کاملا مشخص هست (چون تعداد حالتها مشخص هست )و این حافظه با حالتها شبیه سازی میشود .
امیدوارم تونسته باشم کمکی کرده باشم.
یافتن تمامی ارسال‌های این کاربر



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  متن به هم ریخته در نرم افزار Notepad HAMID3F ۱۵ ۸,۳۱۶ ۱۷ شهریور ۱۳۹۹ ۰۸:۲۶ ق.ظ
آخرین ارسال: rezasedghi100
  سوال در مورد سهمیه رتبه اولی rezamim2020 ۰ ۱۲۰ ۱۶ شهریور ۱۳۹۹ ۰۴:۳۵ ب.ظ
آخرین ارسال: rezamim2020
  معرفی سایت برای شروع یک کسب وکار مستقل sadrasamina ۰ ۷ ۰۹ مرداد ۱۳۹۹ ۱۱:۲۸ ق.ظ
آخرین ارسال: sadrasamina
  دو سوال در مورد درخت BST(درخت جستجوی دودویی) امیدوار ۲ ۱,۵۰۷ ۰۷ مهر ۱۳۹۸ ۰۶:۴۵ ب.ظ
آخرین ارسال: hamzadebaroon
  سوال در مورد دروس جبرای و چارت ارشد کامپیوتر/هوش دانشگاه تهران imali ۱ ۶۵۵ ۰۴ مهر ۱۳۹۸ ۰۱:۴۶ ق.ظ
آخرین ارسال: marvelous
  گرامر منظم Sanazzz ۶ ۱,۷۸۸ ۳۱ اردیبهشت ۱۳۹۸ ۰۴:۳۲ ب.ظ
آخرین ارسال: Sanazzz
  گرامر مستقل از متن Sanazzz ۴ ۱,۶۰۱ ۱۲ دى ۱۳۹۷ ۰۹:۵۹ ب.ظ
آخرین ارسال: Sanazzz
  متن ایمیل برای نویسنده مقاله Iran2014 ۲ ۹۶۰ ۱۰ مهر ۱۳۹۷ ۰۹:۱۵ ب.ظ
آخرین ارسال: Iran2014
  سوال در مورد منبع و دروس آزمون استخدامی mostafa272 ۳ ۱,۴۳۸ ۰۱ تیر ۱۳۹۷ ۱۲:۰۷ ق.ظ
آخرین ارسال: majidnourirad10
  سوال در مورد دانشگاه آزاد قزوین, ارشد شبکه های کامپیوتری networki ۰ ۶۸۷ ۲۱ خرداد ۱۳۹۷ ۱۲:۵۳ ب.ظ
آخرین ارسال: networki

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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