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

حافظه در زبانهای منظم

پاسخ جدید به سوال اصلی موضوع
۰
subtitle
ارسال: #۱
  

- rasool - پرسیده:

Star حافظه در زبانهای منظم

هو العلیم

زبان اول‌: [tex]L=\left \{ W:(n_{a}(w)-n_{b}(w)) mod3 =1 \right \}[/tex]

در این زبان نیاز به حافظه داریم. چون باید تعداد a‌ها را در جایی ذخیره کنیم و بعدش بر اساس اون مقدار a‌ها‌، b بیاوریم و بالعکس. یعنی مدام باید تعداد a یا b‌ها رو داشته باشیم تا بر اساس اونها چنین رابطه ای رو set نگه داریم. (پس تعداد a ‌ها و b‌ها به هم وابسته است)
پس چرا این زبان منظمه؟
می شه بگیم چون حافظه‌ی مورد نیازش محدود و مشخصه و با حالتهای dfa قابل شبیه سازیه در نتیجه منظمه؟
(من راه حل حافظه ای شون رو می خوام)
همچنین برای زبانهای زیر که منظم هستند:

زبان دوم : [tex]L=\left \{ W:(n_{a}(w)-n_{b}(w)) mod3 \neq 0\right \}[/tex]

زبان سوم‌: زبانی که در آن( تعداد a ‌ها زوج و تعداد b‌ها هم زوج) باشه. (زبان اصلاح شد)

[b]زبان چهارم‌: a^n b^m بطوریکه m+n زوج است.


و فرق ساختاری ۴ زبان بالا با زبان پنجم [tex]L=\left \{ W\epsilon \sum ^{*}:n_{a}(w)<n_{b}(w)\right \}[/tex] چیه که در این یکی که وابستگی بین تعداد a و b داریم و در واقع وابستگی بین تعداد تولید اونها هستش و این یعنی نیاز به حافظه (یعنی تعداد a‌ها رو باید داشته باشیم تا بر اساس اون b تولید بشه) نتیجه به نامنظم بودنش می دهد.
اما توی ۴ زبان بالا علیرغم وجود این وابستگی‌ها منظم اند.

اگر فرصت دارید ...


ممنونم .

۰
ارسال: #۲
  

fatima1537 پاسخ داده:

زبانهای منظم

(۰۴ بهمن ۱۳۹۰ ۱۰:۲۵ ب.ظ)yaali نوشته شده توسط:  می شه بگیم چون حافظه‌ی مورد نیازش محدود و مشخصه و با حالتهای dfa قابل شبیه سازیه در نتیجه منظمه؟
به نظر من هم درسته چون میشه این وابستگی عددی حروف الفبا به همدیگر رو با چند حالت محدود پیاده سازی کرد پس میشه منظم.
(۰۴ بهمن ۱۳۹۰ ۱۰:۲۵ ب.ظ)yaali نوشته شده توسط:  و فرق ساختاری ۴ زبان بالا با زبان مثلا [tex]L=\left \{ W\epsilon \sum ^{*}:n_{a}(w)<n_{b}(w)\right \}[/tex] چیه که این یکی که وابستگی بین تعداد a و b داریم و در واقع وابستگی بین تعداد تولید اونها هستش و این یعنی نیاز به حافظه (یعنی تعداد a‌ها رو باید داشته باشیم تا بر اساس اون b تولید بشه)و در نتیجه نامنظم بودنش.

ارسال: #۳
  

- rasool - پاسخ داده:

RE: زبانهای منظم

متشکرم

(۰۴ بهمن ۱۳۹۰ ۱۱:۱۶ ب.ظ)fatima1537 نوشته شده توسط:  اما دقت بفرمایید که این زبان آخریه منظم نیستش.
یافتن تمامی ارسال‌های این کاربر

۰
ارسال: #۴
  

fatima1537 پاسخ داده:

زبانهای منظم

اصلاح شد.با زبان زیر اشتباه گرفته بودم
(۰۴ بهمن ۱۳۹۰ ۱۰:۲۵ ب.ظ)yaali نوشته شده توسط:  [tex]L=\left \{ W:(n_{a}(w),n_{b}(w)) \right \}[/tex]( تعداد a ‌ها زوج b‌ها هم زوج)
چون تعداد aها وbها مشخص نیست پس نمیتوان با تعدادی حالت محدود پیاده سازی کرد.وباید حتما یک ماشین پشته ای باشد که تعداد aها وbها رو بشماره پس منظم نیست

۰
ارسال: #۵
  

- rasool - پاسخ داده:

زبانهای منظم

در پست اولی که زده‌ام پنج زبان رو معرفی کردم.
آقای لینز چهار تای اول رو منظم دونسته و فقط پنجمی رو نامنظم.

سوال من اینه که راه تشخیص اینکه فلان وابستگی رو می شه با FA پیاده کرد یا نه هستش. یعنی تفاوت ساختاری ۴ زبان اول با زبان پنجم.( چون در همه‌ی اونها وابستگی بین تعداد a‌و b‌ و در نتیجه نیاز به حافظه رو داریم)

۰
ارسال: #۶
  

fatima1537 پاسخ داده:

زبانهای منظم

یه راه خوب برای اینکه تشخیص داد زبان منظمه یا نه لم تزریق یا pumping هست(لم تزریق برای تشخیص منظم نبودنه).البته یه مقدار به تمرین نیاز داره که این دید رو به دست بیاریم(اینطور که من با خوندنش متوجه شدم) و یه راهش هم هست که با تمرین زیاد بتونیم تشخیص بدیم آیا میشه برای یک زبان یه ماشین منظم رسم کنیم؟یا اینکه حتما زبان رو با یک ماشین پشته ای پیاده سازی کرد؟
مثلا مثالهایی که در بالازدید جزء مثالهایی اند که توی اغلب کتابها هستند و با چند بار تمرین کردن اینها و چند مثال مشابه دیگه متوجه خواهیم شد این زبانها رو با تعداد معدودی از حالتها می توان رسم کرد ولی برای پیاده سازی وابستگی تعدادی مثال چهارم (چون عضو سیگما استار هم هست) دیگر با تعداد معدود نمی شود و باید حتما شمارش کرد

۰
ارسال: #۷
  

- rasool - پاسخ داده:

زبانهای منظم

با تشکر.

بله. لم تزریق هم هست. منتها من در این سوال روش حافظه ای مد نظرم هستش .

(۰۴ بهمن ۱۳۹۰ ۱۱:۵۰ ب.ظ)fatima1537 نوشته شده توسط:  مثالهایی که در بالازدید جزء مثالهایی اند که توی اغلب کتابها هستند و با چند بار تمرین کردن اینها و چند مثال مشابه دیگه متوجه خواهیم شد این زبانها رو با تعداد معدودی از حالتها می توان رسم کرد ولی برای پیاده سازی وابستگی تعدادی مثال پنجم(چون عضو سیگما استار هم هست) دیگر با تعداد معدود نمی شود و باید حتما شمارش کرد
بله. تایید می شه. من هم فکر می کنم که تجربه و تمرین خیلی کمک می کنه. منتها دنبال روشی کلاسیک برای تمیز بین این دو دسته زبان بودم.

۰
ارسال: #۸
  

fatima1537 پاسخ داده:

زبانهای منظم

من هم فقط تجربی تشخیص میدم بعضی وقتها هم اشتباه تشخیص دادم! کتاب لینز رو هم خوندم در این مورد چیزی متوجه نشدم. شاید بوده من متوجه نشدم

ارسال: #۹
  

sasanlive پاسخ داده:

RE: زبانهای منظم

(۰۴ بهمن ۱۳۹۰ ۱۰:۲۵ ب.ظ)yaali نوشته شده توسط:  زبان سوم‌: [tex]L=\left \{ W:(n_{a}(w),n_{b}(w)) \right \}[/tex]( تعداد a ‌ها زوج b‌ها هم زوج)

زبان چهارم‌: a^n b^m بطوریکه m+n زوج است.


و فرق ساختاری ۴ زبان بالا با زبان پنجم [tex]L=\left \{ W\epsilon \sum ^{*}:n_{a}(w)<n_{b}(w)\right \}[/tex] چیه که در این یکی که وابستگی بین تعداد a و b داریم و در واقع وابستگی بین تعداد تولید اونها هستش و این یعنی نیاز به حافظه (یعنی تعداد a‌ها رو باید داشته باشیم تا بر اساس اون b تولید بشه) نتیجه به نامنظم بودنش می دهد.
اما توی ۴ زبان بالا علیرغم وجود این وابستگی‌ها منظم اند.

اگر فرصت دارید ...


ممنونم .
سلام.
تو سواله ۱و۲ نمیدونم yaali جان جواب تمرینو ندارین؟
یا با جواب مشکل دارین؟
ضمنا این سوالو تو لینز پیدا نکردم.دقیقتر بگین شاید تو کتابه صراف زاده نباشه.

جواب سوال ۳ و ۴ و ۵ رو میذارم.
روشهای حل تستی اینجور مسائل عموما به این شکل هستن.
در سوال ۳ نیاز به کشیدن ماشین نبود صرفا برای فهمیدن سوال شکلو کشیدم.

در سوال سوم جواب تنها ماشینه ۳ هست که در شکل زیر رسم کردم.چون با عجله شکلو کشیدم تو سوال ندیدم که a,b هر دو تعدادشون زوجه و چون وقت نداشتم , دیگه شکلو تصحیح نکردم.

پس جواب ۳ که گذاشتم جواب سوالتون نیست و جواب همونیه که بالا گفتم.

[تصویر: 64406_1_1379095741.JPG]


بخاطره سریع نوشتن بدخطم نوشتم. دیگه من از همه عقبترم عذرم پذیرفتست Big Grin.

.
یافتن تمامی ارسال‌های این کاربر

۰
ارسال: #۱۰
  

Jooybari پاسخ داده:

حافظه در زبانهای منظم

سلام. ۴تا زبان اول که منظمن و پنجمی هم مستقل از متن(یا بهتر بگم مستقل از زمینه)
برای زبان شماره ۱ یه dfa با ۳ حالت میشه ساخت. از هر حالت با a به حالت بعد و با b به حالت قبل میره. یعنی با a از q0 به q1 و با b از q0 به q2 میره. حالت q0 شروع و حالت q1 هم جوابه.

[tex]\delta (q_0,a)=q_1[/tex]
[tex]\delta (q_0,b)=q_2[/tex]
[tex]\delta (q_1,a)=q_2[/tex]
[tex]\delta (q_1,b)=q_0[/tex]
[tex]\delta (q_2,a)=q_0[/tex]
[tex]\delta (q_2,b)=q_1[/tex]

دلیل منظم بودنش هم اینه که ما فقط ۳ وضعیت خاص رو نگه میداریم نه مقدار aها و bها.

برای زبان شماره ۲ هم مشابه شماره ۱ میشه. زبانش همونه حالت شروعش هم همونه ولی حالت پایانی هم q1 و هم q2 میشه.

برای زبان شماره ۳ میشه این dfa رو کشید:

[tex]\delta (q_0,a)=q_1[/tex]
[tex]\delta (q_0,b)=q_2[/tex]
[tex]\delta (q_1,a)=q_0[/tex]
[tex]\delta (q_1,b)=q_3[/tex]
[tex]\delta (q_2,a)=q_3[/tex]
[tex]\delta (q_2,b)=q_0[/tex]
[tex]\delta (q_3,a)=q_2[/tex]
[tex]\delta (q_3,b)=q_1[/tex]

حالت شروع و پایانش q0میشه. یعنی داریم در q0 تعداد a,b زوج، در q1 تعداد a فرد و b زوج، در q2 تعداد a زوج و b فرد و در q3 تعداد a,b فرد.

برای زبان ۴ هم مشابه زبان ۳ هست (البته چندتا از حرکاتش حذف میشه.) با این تفاوت که q0 و q3 هردو حالات پایانی هستن.

برای زبان ۵ هم میشه این ماشین پشته ای با ۲ حالت رو کشید Sadچون نمیتونم چیزی آپلود کنم فقط میتونم حرکتهارو بنویسم)

q0 حالت شروع و q1 حالات پایانیمونه:

از q0 به q0 این حرکتهارو داریم:

[tex]a,$ \rightarrow a$[/tex]
[tex]a,a \rightarrow aa[/tex]
[tex]b,$ \rightarrow b$[/tex]
[tex]b,a \rightarrow \lambda[/tex]
[tex]b,b \rightarrow bb[/tex]

از q0 به q1 داریم:

[tex]\lambda ,a \rightarrow a[/tex]

و از q0 به q1 داریم:

[tex]b ,a \rightarrow \lambda[/tex]

از q1 به q1 داریم:

[tex]a ,a \rightarrow aa[/tex]

ارسال: #۱۱
  

sasanlive پاسخ داده:

RE: حافظه در زبانهای منظم

(۰۵ بهمن ۱۳۹۰ ۰۱:۵۰ ق.ظ)Lakikharin نوشته شده توسط:  سلام. ۴تا زبان اول که منظمن و پنجمی هم مستقل از متن(یا بهتر بگم مستقل از زمینه)
برای زبان شماره ۱ یه dfa با ۳ حالت میشه ساخت. از هر حالت با a به حالت بعد و با b به حالت قبل میره. یعنی با a از q0 به q1 و با b از q0 به q2 میره. حالت q0 شروع و حالت q1 هم جوابه.

[tex]\delta (q_0,a)=q_1[/tex]
[tex]\delta (q_0,b)=q_0[/tex]
[tex]\delta (q_1,a)=q_2[/tex]
[tex]\delta (q_1,b)=q_0[/tex]
[tex]\delta (q_2,a)=q_1[/tex]
[tex]\delta (q_2,b)=q_0[/tex]

دلیل منظم بودنش هم اینه که ما فقط ۳ وضعیت خاص رو نگه میداریم نه مقدار aها و bها.

جواب این سوال غلطه.
abba رو تولید میکنه که جزء زبان نیست.
یافتن تمامی ارسال‌های این کاربر

۰
ارسال: #۱۲
  

Jooybari پاسخ داده:

حافظه در زبانهای منظم

متشکر. حالتهاشو اشتباه نوشته بودم. درستش کردم.

۰
ارسال: #۱۳
  

- rasool - پاسخ داده:

حافظه در زبانهای منظم

از همه‌ی اساتید سپاسگزارم.

لطفا به این سوال من دقت بفرمایید:

مگه توی زبان چهارم نیاز به حافظه نداریم؟ چون تعداد b‌ها باید بر حسب تعداد a‌ها تنظیم بشه.یعنی a و b به هم وابسته هستند.

البته نتیجه گیری من این شد که:
اگر حافظه‌ی مورد نیازش محدود و مشخص باشه و با حالتهای dfa قابل شبیه سازی باشه منظمه.(حالا اینکه کدوم زبان این شرایط رو داره هم با دیدن زبانهای این تیپی و تمرین و تجربه و ... خواهد بود)( مانند زبانهای اول تا چهارم)

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

ارسال: #۱۴
  

sasanlive پاسخ داده:

RE: حافظه در زبانهای منظم

(۰۵ بهمن ۱۳۹۰ ۰۹:۰۸ ق.ظ)yaali نوشته شده توسط:  از همه‌ی اساتید سپاسگزارم.

لطفا به این سوال من دقت بفرمایید:

مگه توی زبان چهارم نیاز به حافظه نداریم؟ چون تعداد b‌ها باید بر حسب تعداد a‌ها تنظیم بشه.

نه نیاز به هیچ حافظه نامحدودی نداریم.
چون نیاز به مچ کردن a با b نیست. یعنی a و b هیچ وابستگی به هم ندارن.
تو ضمیمه گفتم جوابش به شکل زیر هست. که هیچ وابستگی بین a و b نیست.
[tex](aa)^{*}(bb)^{*} a(aa)^{*}b(bb)^{*}[/tex]

ولی در زبان پنجم نیاز به حافظه داریم تا اول b رو بتونیم به اندازه a تولید کنیم و بعد مقدارb رو بتونیم بیشتر از a قرار بدیم. که این نیاز به حافظه نامحدود داره.

(۰۵ بهمن ۱۳۹۰ ۰۹:۰۸ ق.ظ)yaali نوشته شده توسط:  گر حافظه‌ی مورد نیازش محدود و مشخص باشه و با حالتهای dfa قابل شبیه سازی باشه منظمه
بله.
اگه بتونیم برای زبانی dfa یا nfa رسم کنیم زبان منظمه. چون دیگه نیاز به حافظه نامحدود نداره.

(۰۵ بهمن ۱۳۹۰ ۰۹:۰۸ ق.ظ)yaali نوشته شده توسط:  و اگر حافظه مورد نیازش نامحدود و نامشخص باشه و با حالتهای dfa قابل شبیه سازی نباشه نا منظمه.
اگه حتما نیاز به پشته برای رسمش باشه دیگه منظم نیست.
این در شرایطی که نیاز داریم وابستگی رو بین اعضا برقرار کنیم.


کلا باید تو اینجور سوالا با ابتکار خودتون شکل زبانو بتونین به شکلی در بیارین که وابستگی بین اعضای زبان ازبین بره. اگه تونستین اینکارو بکنین , زبان منظمه.
در غیر اینصورت منظم نیست.
یافتن تمامی ارسال‌های این کاربر

۰
ارسال: #۱۵
  

Jooybari پاسخ داده:

حافظه در زبانهای منظم

نتیجه گیریتون درسته. توی زبان چهارم فقط باید تعداد زوج یا فرد بودن aهارو درنظر بگیرید. یعنی:

[tex]\delta (q_0,a)=q_1[/tex]
[tex]\delta (q_0,b)=q_2[/tex]
[tex]\delta (q_1,a)=q_0[/tex]
[tex]\delta (q_1,b)=q_3[/tex]
[tex]\delta (q_2,b)=q_4[/tex]
[tex]\delta (q_3,b)=q_5[/tex]
[tex]\delta (q_4,b)=q_2[/tex]
[tex]\delta (q_5,b)=q_3[/tex]

حالتت q0 شروع و حالات q2 و q5 هم جوااب هستن.

ارسال: #۱۶
  

- rasool - پاسخ داده:

RE: حافظه در زبانهای منظم

(۰۵ بهمن ۱۳۹۰ ۱۲:۲۱ ب.ظ)Lakikharin نوشته شده توسط:  نتیجه گیریتون درسته. توی زبان چهارم فقط باید تعداد زوج یا فرد بودن aهارو درنظر بگیرید. یعنی:

[tex]\delta (q_0,a)=q_1[/tex]
[tex]\delta (q_0,b)=q_2[/tex]
[tex]\delta (q_1,a)=q_0[/tex]
[tex]\delta (q_1,b)=q_3[/tex]
[tex]\delta (q_2,b)=q_4[/tex]
[tex]\delta (q_3,b)=q_5[/tex]
[tex]\delta (q_4,b)=q_2[/tex]
[tex]\delta (q_5,b)=q_3[/tex]

حالتت q0 شروع و حالات q2 و q5 هم جوااب هستن.

ممنونم. البته این FA‌ی شما رشته‌ی ab رو نمی پذیره با اینکه جزء زبان هست.
یافتن تمامی ارسال‌های این کاربر

۰
ارسال: #۱۷
  

Jooybari پاسخ داده:

حافظه در زبانهای منظم

ببخشید مثل اینکه q0 و q3 و q4 پایانیه. توی q2,q5 مجموع a,b همیشه فرده. شرمنده. Big Grin

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


موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
Wink دانلود نظریه زبانهای پیتر لینز ویرایش ۵ + حل armin.sheikh ۵ ۱۲,۵۷۴ ۰۲ خرداد ۱۳۹۹ ۰۸:۲۶ ب.ظ
آخرین ارسال: gillda
  گرامر منظم Sanazzz ۶ ۷,۴۴۳ ۳۱ اردیبهشت ۱۳۹۸ ۰۴:۳۲ ب.ظ
آخرین ارسال: Sanazzz
  حافظه نانو Sanazzz ۱ ۲,۰۲۱ ۱۲ اردیبهشت ۱۳۹۸ ۱۲:۲۶ ق.ظ
آخرین ارسال: Sanazzz
  نحوه مشخص کردن بیت‌های حافظه کنترل Erfan_Ekh ۰ ۲,۰۸۷ ۰۹ تیر ۱۳۹۷ ۰۳:۱۷ ب.ظ
آخرین ارسال: Erfan_Ekh
Photo ساده سازی عبارت منظم etedadi ۰ ۲,۲۱۷ ۱۶ خرداد ۱۳۹۷ ۰۷:۰۴ ب.ظ
آخرین ارسال: etedadi
  منبع زبانهای برنامه سازی مفاهیم شی گرا m_sardaari ۰ ۱,۸۸۴ ۱۷ اردیبهشت ۱۳۹۷ ۰۱:۰۶ ب.ظ
آخرین ارسال: m_sardaari
  مهندسی کامپوتر ۹۵ - حافظه مجازی mahshid_dd ۲ ۳,۰۶۶ ۰۲ اردیبهشت ۱۳۹۷ ۰۲:۰۵ ب.ظ
آخرین ارسال: mahshid_dd
  عبارت منظم fsmtnc ۱ ۲,۲۲۶ ۲۱ دى ۱۳۹۶ ۰۶:۵۵ ب.ظ
آخرین ارسال: msour44
  درخواست حل سوال ۷۲ از کامپیوتر ۹۶- مشکل در فهم حافظه نانو Sepideh96 ۱ ۲,۳۷۶ ۱۷ دى ۱۳۹۶ ۰۹:۲۷ ب.ظ
آخرین ارسال: yahmat
  گرامر منظم fsmtnc ۲ ۳,۱۳۸ ۱۴ دى ۱۳۹۶ ۱۱:۵۷ ق.ظ
آخرین ارسال: fsmtnc

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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