ارسال: #۱

۰۴ بهمن ۱۳۹۰, ۱۰:۲۵ ب.ظ

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

هو العلیم

زبان اول‌:

$L=\left \{ W:(n_{a}(w)-n_{b}(w)) mod3 =1 \right \}$

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

زبان دوم :

$L=\left \{ W:(n_{a}(w)-n_{b}(w)) mod3 \neq 0\right \}$

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

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

و فرق ساختاری ۴ زبان بالا با زبان پنجم

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

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

ممنونم .

ارسال: #۲

۰۴ بهمن ۱۳۹۰, ۱۱:۱۶ ب.ظ

fatima1537 پاسخ داده:

زبانهای منظم

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

به نظر من هم درسته چون میشه این وابستگی عددی حروف الفبا به همدیگر رو با چند حالت محدود پیاده سازی کرد پس میشه منظم.

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

ارسال: #۳

۰۴ بهمن ۱۳۹۰, ۱۱:۲۴ ب.ظ

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

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

متشکرم

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

ارسال: #۴

۰۴ بهمن ۱۳۹۰, ۱۱:۳۶ ب.ظ

fatima1537 پاسخ داده:

زبانهای منظم

اصلاح شد.با زبان زیر اشتباه گرفته بودم

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

چون تعداد aها وbها مشخص نیست پس نمیتوان با تعدادی حالت محدود پیاده سازی کرد.وباید حتما یک ماشین پشته ای باشد که تعداد aها وbها رو بشماره پس منظم نیست

ارسال: #۵

۰۴ بهمن ۱۳۹۰, ۱۱:۴۳ ب.ظ

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

زبانهای منظم

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

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

ارسال: #۶

۰۴ بهمن ۱۳۹۰, ۱۱:۵۰ ب.ظ

fatima1537 پاسخ داده:

زبانهای منظم

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

ارسال: #۷

۰۴ بهمن ۱۳۹۰, ۱۱:۵۷ ب.ظ

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

زبانهای منظم

با تشکر.

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

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

بله. تایید می شه. من هم فکر می کنم که تجربه و تمرین خیلی کمک می کنه. منتها دنبال روشی کلاسیک برای تمیز بین این دو دسته زبان بودم.

ارسال: #۸

۰۵ بهمن ۱۳۹۰, ۱۲:۱۱ ق.ظ

fatima1537 پاسخ داده:

زبانهای منظم

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

ارسال: #۹

۰۵ بهمن ۱۳۹۰, ۰۱:۰۸ ق.ظ

sasanlive پاسخ داده:

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

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

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

و فرق ساختاری ۴ زبان بالا با $L=\left \{ W\epsilon \sum ^{*}:n_{a}(w)<n_{b}(w)\right \}$ چیه که در این یکی که وابستگی بین تعداد 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 هم جوابه.

$\delta (q_0,a)=q_1$

$\delta (q_0,b)=q_2$

$\delta (q_1,a)=q_2$

$\delta (q_1,b)=q_0$

$\delta (q_2,a)=q_0$

$\delta (q_2,b)=q_1$

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

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

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

$\delta (q_0,a)=q_1$

$\delta (q_0,b)=q_2$

$\delta (q_1,a)=q_0$

$\delta (q_1,b)=q_3$

$\delta (q_2,a)=q_3$

$\delta (q_2,b)=q_0$

$\delta (q_3,a)=q_2$

$\delta (q_3,b)=q_1$

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

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

برای زبان ۵ هم میشه این ماشین پشته ای با ۲ حالت رو کشید Sad

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

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

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

$a,$ \rightarrow a$$

$a,a \rightarrow aa$

$b,$ \rightarrow b$$

$b,a \rightarrow \lambda$

$b,b \rightarrow bb$

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

$\lambda ,a \rightarrow a$

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

$b ,a \rightarrow \lambda$

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

$a ,a \rightarrow aa$

ارسال: #۱۱

۰۵ بهمن ۱۳۹۰, ۰۲:۱۱ ق.ظ

sasanlive پاسخ داده:

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

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

$\delta (q_0,a)=q_1$
$\delta (q_0,b)=q_0$
$\delta (q_1,a)=q_2$
$\delta (q_1,b)=q_0$
$\delta (q_2,a)=q_1$
$\delta (q_2,b)=q_0$

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

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

ارسال: #۱۲

۰۵ بهمن ۱۳۹۰, ۰۳:۱۲ ق.ظ

Jooybari پاسخ داده:

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

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

ارسال: #۱۳

۰۵ بهمن ۱۳۹۰, ۰۹:۰۸ ق.ظ

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

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

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

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

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

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

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

ارسال: #۱۴

۰۵ بهمن ۱۳۹۰, ۱۲:۱۸ ب.ظ

sasanlive پاسخ داده:

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

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

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

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

نه نیاز به هیچ حافظه نامحدودی نداریم.
چون نیاز به مچ کردن a با b نیست. یعنی a و b هیچ وابستگی به هم ندارن.
تو ضمیمه گفتم جوابش به شکل زیر هست. که هیچ وابستگی بین a و b نیست.

$(aa)^{*}(bb)^{*} a(aa)^{*}b(bb)^{*}$

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

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

بله.
اگه بتونیم برای زبانی dfa یا nfa رسم کنیم زبان منظمه. چون دیگه نیاز به حافظه نامحدود نداره.

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

اگه حتما نیاز به پشته برای رسمش باشه دیگه منظم نیست.
این در شرایطی که نیاز داریم وابستگی رو بین اعضا برقرار کنیم.

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

ارسال: #۱۵

۰۵ بهمن ۱۳۹۰, ۱۲:۲۱ ب.ظ

Jooybari پاسخ داده:

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

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

$\delta (q_0,a)=q_1$

$\delta (q_0,b)=q_2$

$\delta (q_1,a)=q_0$

$\delta (q_1,b)=q_3$

$\delta (q_2,b)=q_4$

$\delta (q_3,b)=q_5$

$\delta (q_4,b)=q_2$

$\delta (q_5,b)=q_3$

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

ارسال: #۱۶

۰۵ بهمن ۱۳۹۰, ۱۲:۴۷ ب.ظ

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

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

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

$\delta (q_0,a)=q_1$
$\delta (q_0,b)=q_2$
$\delta (q_1,a)=q_0$
$\delta (q_1,b)=q_3$
$\delta (q_2,b)=q_4$
$\delta (q_3,b)=q_5$
$\delta (q_4,b)=q_2$
$\delta (q_5,b)=q_3$

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

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

ارسال: #۱۷

۰۵ بهمن ۱۳۹۰, ۰۱:۵۷ ب.ظ

Jooybari پاسخ داده:

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

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

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

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

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

زبانهای منظم

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

زبانهای منظم

زبانهای منظم

زبانهای منظم

زبانهای منظم

زبانهای منظم

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

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

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

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

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

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

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

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

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

Can I see some ID?

Feeling left out?

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

Feeling left out?