ارسال: #۱

۳۰ آبان ۱۳۹۱, ۰۳:۱۵ ب.ظ

hp1361 پرسیده:

حل تمرین کتاب لینز-بخش ۲-۲

با عرض سلام خدمت تمام دوستان مانشتی

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

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

*توضیح در مورد راه حل ها*
۱- سوالاتی که باید در اون اثبات صورت بگیره فعلا در دستور کار قرار نداره
۲-اگر جوابی احیاناً اشتباه بود با پیام خصوصی لطف کنید اطلاع بدید تا در سریع ترین زمان ممکن اصلاح نمایم.
۳-اینکه در انتهای تاپیک چند ارسال بصورت شماره سوال بعلاوه چند ستاره گذاشته ام(۱۵-***) بخاطر اینه که بعد از ارسال یک پاسخ فوراً نمیشه ارسال جدیدی انجام داد و ارسال های جدید در داخل ارسال قبلی قرار میگیرند.بخاطر همین ارسال ها رو موقتا ایجاد کرده ام.
۴-شاید این مورد خیلی بدیهی باشه ولی خوب شاید هم بکار بیاد چون دوستان به اون اشاره کردند:برای مشاهده جواب بر روی تصویر پیوست شده کلیک کنید تا با کیفیت کامل در صفحه ای جدید نمایش داده بشه.
۵-دوستان لطف کنند جهت تشکر از دکمه مربوطه استفاده کنند تا جواب ها بصورت متوالی بوسیله هر ارسال نمایش داده شود.(جهت پرسیدن سوال و یا انتقاد و پیشنهاد از پیام خصوصی استفاده شود. پیام هایی که احتمال استفاده شون بره در تاپیک قرار داده خواهد شد)

سوالات

۱- با تمام جزئیات، ادعای عنوان شده در بخش قبلی را ثابت کنید که اگر در یک گراف انتقال راهی با برچسب w وجود داشته باشد، آنگاه باید راهی با برچسب w با طول نابیشتر از

$\Lambda \left ( 1 \Lambda \right )\left | w \right |$ موجود باشد.

***حل نشده***

ارسال: #۲

۰۶ آذر ۱۳۹۱, ۰۱:۲۷ ب.ظ

hp1361 پاسخ داده:

RE: حل تمرین کتاب لینز-بخش ۲-۲

۷- یک پذیرنده متناهی غیرقطعی با حداکثر پنج حالت برای مجموعه

$\left \{ abab^{n}:n\geqslant 0 \right \}\cup \left \{ aba^{n}:n\geqslant 0 \right \}$ طراحی کنید.

ارسال: #۳

۰۶ آذر ۱۳۹۱, ۰۲:۴۰ ب.ظ

hp1361 پاسخ داده:

حل تمرین کتاب لینز-بخش ۲-۲

۸-یک پذیرنده متناهی غیرقطعی با سه حالت بسازید که زبان

$\left \{ ab,abc \right \}^{*}$ را بپذیرد.

ارسال: #۴

۳۰ آبان ۱۳۹۱, ۱۱:۰۴ ب.ظ

hp1361 پاسخ داده:

حل تمرین کتاب لینز-بخش ۲-۲

۲- یک پذیرنده متناهی قطعی بیابید که زبان تعریف شده بوسیله پذیرنده متناهی غیر قطعی در شکل ۲-۸ را بپذیرد.

شکل ۲-۸

جواب

ارسال: #۵

۰۱ آذر ۱۳۹۱, ۰۴:۲۹ ب.ظ

hp1361 پاسخ داده:

حل تمرین کتاب لینز-بخش ۲-۲

۳- یک پذیرنده متناهی قطعی بیابید که مکمل زبان تعریف شده بوسیله پذیرنده متناهی غیر قطعی در شکل ۲-۸ را بپذیرد.

شکل ۲-۸

جواب

ارسال: #۶

۰۵ آذر ۱۳۹۱, ۱۱:۲۱ ق.ظ

hp1361 پاسخ داده:

حل تمرین کتاب لینز-بخش ۲-۲

۴ -در شکل ۲-۹ توابع

$\delta ^{*}\left ( q_{0},1011 \right )$ و

$\delta ^{*}\left ( q_{1},01 \right )$ را بیابید.

شکل ۲-۹

جواب الف

جواب ب

ارسال: #۷

۰۵ آذر ۱۳۹۱, ۰۹:۱۵ ب.ظ

hp1361 پاسخ داده:

حل تمرین کتاب لینز-بخش ۲-۲

۵-در شکل ۲-۱۰،

$\delta ^{*}\left ( q_{0},a \right )$ و

$\delta ^{*}\left ( q_{1},\lambda \right )$ را بیابید.

ارسال: #۸

۰۶ آذر ۱۳۹۱, ۱۲:۲۷ ب.ظ

hp1361 پاسخ داده:

حل تمرین کتاب لینز-بخش ۲-۲

۶-برای پذیرنده متناهی غیرقطعی در شکل ۲-۹،

$\delta ^{*}\left ( q_{0},1010 \right )$ و

$\delta ^{*}\left ( q_{1},00 \right )$ را بیابید.

الف)

ب)

$\delta ^{*}(q_{0},00)=\varnothing$

ارسال: #۹

۰۶ آذر ۱۳۹۱, ۰۳:۵۴ ب.ظ

hp1361 پاسخ داده:

RE: حل تمرین کتاب لینز-بخش ۲-۲

۹- آیا فکر میکنید تمرین ۸ میتواند با کمتر از ۳ حالت حل شود؟

خیر. از آنجایی که الفبای ما شامل ۳ عضو است، جهت تولید این زبان حداقل به ۳ حالت متمایز نیاز است.

ارسال: #۱۰

۰۶ آذر ۱۳۹۱, ۰۵:۰۵ ب.ظ

teacherpc پاسخ داده:

RE: حل تمرین کتاب لینز-بخش ۲-۲

(۰۶ آذر ۱۳۹۱ ۰۳:۵۴ ب.ظ)hp1361 نوشته شده توسط: ۱۰-یک پذیرنده متناهی غیرقطعی با چهارحالت برای $L=\left \{ a^{n}:n\geq 0 \right \}\cup \left \{ b^{n}a:n\geq 1 \right \}$ بیابید.

۱۱-****

دوست عزیزم ممنون که وقت میزاری و این تصاویر با کیفیت رو میزاری برا بچه ها
من فایرفاکسم خطا میداد اکسپشن و نشون نمیداد تصاویر رو
تنظیمش کردم الان نشون میده ممنون پیام دادین همینطور ممنونم از eternal عزیز که ایشون هم نکته شما رو گفتن مرسی عالی بودند تصاویر

ارسال: #۱۱

۰۶ آذر ۱۳۹۱, ۰۵:۲۳ ب.ظ

hp1361 پاسخ داده:

حل تمرین کتاب لینز-بخش ۲-۲

۱۰-الف)یک پذیرنده متناهی غیرقطعی با سه حالت بیابید که زبان

$L= \left \{ a^{n}:n\geq 1 \right \}\cup \left \{ b^{m}a^{k}:m\geq 0,k\geq0 \right \}$ را بپذیرد.

ب)آیا فکر میکنید که زبان بخش الف می تواند بوسیله یک پذیرنده متناهی غیرقطعی با کمتر از سه حالت پذیرفته شود؟

پاسخ: بله. زبان

$\left \{ a^{n}:n\geq 1 \right \}$ درون زبان

$\left \{ b^{m}a^{k}:m,k\geq 0 \right \}$ وجود دارد.

ارسال: #۱۲

۰۶ آذر ۱۳۹۱, ۰۸:۵۶ ب.ظ

hp1361 پاسخ داده:

حل تمرین کتاب لینز-بخش ۲-۲

۱۱-یک پذیرنده متناهی غیرقطعی با چهارحالت برای

$L=\left \{ a^{n}:n\geq 0 \right \}\cup \left \{ b^{n}a:n\geq 1 \right \}$ بیابید.

ارسال: #۱۳

۰۶ آذر ۱۳۹۱, ۱۰:۱۸ ب.ظ

hp1361 پاسخ داده:

حل تمرین کتاب لینز-بخش ۲-۲

۱۲ -کدامیک از رشته های ۰۰، ۰۱۰۰۱، ۱۰۰۱۰، ۰۰۰، ۰۰۰۰ بوسیله پذیرنده متناهی قطعی زیر پذیرفته می شود؟

سوال : زبان پذیرفته شده توسط این ماشین چیست؟

ارسال: #۱۴

۰۷ آذر ۱۳۹۱, ۰۷:۳۵ ق.ظ

hp1361 پاسخ داده:

حل تمرین کتاب لینز-بخش ۲-۲

۱۳ - مکمل زبان پذیرفته شده بوسیله پذیرنده متناهی غیر قطعی در شکل ۲-۱۰ چیست ؟

ارسال: #۱۵

۰۷ آذر ۱۳۹۱, ۱۲:۰۸ ب.ظ

hp1361 پاسخ داده:

حل تمرین کتاب لینز-بخش ۲-۲

۱۴ - فرض کنید

$L$ زبان پذیرفته شده بوسیله پذیرنده متناهی غیر قطعی در شکل ۲-۸ باشد. یک پذیرنده متناهی غیر قطعی بیابید که

$L \cup \left \{ a^{5} \right \}$ را بپذیرد.

سوال : پذیرنده متناهی قطعی این زبان را رسم کنید.

ارسال: #۱۶

۰۷ آذر ۱۳۹۱, ۰۱:۳۶ ب.ظ

hp1361 پاسخ داده:

حل تمرین کتاب لینز-بخش ۲-۲

۱۵ - توصیف ساده ای از زبان تمرین ۱۳ ارائه دهید.

زبان این پذیرنده

$L=\left \{ \lambda \right \}$ می باشد. یعنی فقط رشته به طول صفر پذیرفته و در همان وضعیت ابتدایی قرار می گیرد که وضعیت نهایی است.

ارسال: #۱۷

۰۷ آذر ۱۳۹۱, ۰۲:۴۹ ب.ظ

hp1361 پاسخ داده:

حل تمرین کتاب لینز-بخش ۲-۲

۱۶ - یک پذیرنده متناهی غیر قطعی بیابید که

$\left \{ a \right \}^{*}$ را بپذیرد بطوریکه اگر در گراف انتقال آن یک یال تنها حذف شود (بدون هیچگونه تغییر دیگری)، ماشین بدست آمده

$\left \{ a \right \}$ را بپذیرد.

سوال : برای این تمرین آیا میتوان پذیرنده متناهی غیر قطعی ای ساخت که از بین یال ها هر کدام که حذف شود همین نتیجه را بدهد؟

ارسال: #۱۸

۰۷ اسفند ۱۳۹۴, ۱۲:۱۵ ب.ظ

ymgh96 پاسخ داده:

RE: حل تمرین کتاب لینز-بخش ۲-۲

(۰۷ آذر ۱۳۹۱ ۰۲:۴۹ ب.ظ)hp1361 نوشته شده توسط: ۱۶ - یک پذیرنده متناهی غیر قطعی بیابید که $\left \{ a \right \}^{*}$ را بپذیرد بطوریکه اگر در گراف انتقال آن یک یال تنها حذف شود (بدون هیچگونه تغییر دیگری)، ماشین بدست آمده $\left \{ a \right \}$ را بپذیرد.

سوال : برای این تمرین آیا میتوان پذیرنده متناهی غیر قطعی ای ساخت که از بین یال ها هر کدام که حذف شود همین نتیجه را بدهد؟

با سلام
این ماشین الان لاندا را میپذیرد؟
چون قرار است {a}* را بپذیرد که خوب شامل لاندا هم هست...

ارسال: #۱۹

۰۷ آذر ۱۳۹۱, ۰۴:۰۳ ب.ظ

hp1361 پاسخ داده:

حل تمرین کتاب لینز-بخش ۲-۲

۱۷ - آیا تمرین ۱۶ می تواند با استفاده از یک پذیرنده متناهی قطعی حل شود؟ اگر چنین است،راه حل را ارائه دهید، اگر نیست استدلالاتی قانع کننده برای نتیجه خود ارائه دهید.

جواب : خیر. از آنجائیکه زبان

$\left \{ a \right \}^{*}$ شامل

$\lambda$ می باشد، با حذف هیچ یالی این رشته از بین نخواهد رفت و لذا با حذف هر کدام از یال های هر ماشین متناهی قطعی ای کماکان این رشته تولید خواهد شد که با خواسته سوال که تولید صرفاً

$\left \{ a \right \}$ می باشد متضاد است.

ارسال: #۲۰

۰۷ آذر ۱۳۹۱, ۱۱:۱۱ ب.ظ

hp1361 پاسخ داده:

حل تمرین کتاب لینز-بخش ۲-۲

۱۸- تغییرات زیر را برای تعریف ۲-۶ در نظر بگیرید. یک nfa با چندین وضعیت ابتدایی بصورت پنج تایی

$M=\left ( Q,\Sigma ,\delta ,Q_{0},F \right )$ تعریف می شود که در آن

$Q_{0}\subseteq Q$ مجموعه ای از وضعیت های ابتدایی ممکن است. زبان پذیرفته شده توسط چنین ماشینی بصورت زیر تعیف می شود:

$L\left ( M \right )=\left \{ w:\delta ^{*}\left ( q_{0},w \right ) contains \: q_{f}\: ,\: for \: any \: q_{0}\in Q_{0} \: , \: q_{f}\in F \right \}$

نشان دهید برای هر nfa با چندین وضعیت ابتدایی یک nfa با یک وضعیت ابتدایی وجود دارد که همان زبان را می پذیرد.

جواب : کافیست یک وضعیت شروع جدید

$p_{0}$ تعریف نموده و با یک

$\lambda$ به هریک از وضعیت های شروع قبلی وصل نمائیم. همچنین وضعیت های شروع قبلی را از حالت شروع خارج نمائیم.(چراکه حالا در ادامه وضعیت شروع جدید قرار دارند)

$\delta (p_{0},\lambda )=Q_{0}$

ارسال: #۲۱

۰۹ آذر ۱۳۹۱, ۱۲:۰۳ ق.ظ

hp1361 پاسخ داده:

حل تمرین کتاب لینز-بخش ۲-۲

۱۹ - فرض کنید در تمرین ۱۸ محدودیت

$Q_{0}\cap F=\varnothing$ را اعمال کنیم. آیا این محدودیت تاثیری در نتیجه دارد؟

جواب : خیر. اینکه با استفاده از یک وضعیت شروع واحد به نقاط شروع قبلی برسیم ارتباطی با این ندارد که آن وضعیت ها پایانی باشند یا خیر.

ارسال: #۲۲

۱۴ آذر ۱۳۹۱, ۰۸:۲۵ ق.ظ

hp1361 پاسخ داده:

حل تمرین کتاب لینز-بخش ۲-۲

۲۰ - با استفاده از تعریف ۲-۵ نشان دهید که برای هر nfa رابطه زیر برقرار است:

$\delta ^{*}\left ( q,wv \right )=\bigcup_{p\in \delta ^{*}\left ( q,w \right )} \delta ^{*}\left ( p,v \right )$

$for \: all \: q \in Q \: and \: all \: w,v \in \Sigma ^{*}$

تعریف ۲-۵

$for \; an \; nfa , \; the \; extended \; transition \; function \; is \; defined \; so \; that \; \delta ^{*}\left ( q_{i},w \right ) \; contains \\ \; q_{j} \; if \; and \; only \; if \; there \; is \; a \; walk \; in \; the \; transition \; graph \; from \; q_{i} \; to \; q_{j} \; labeled \; w.\\ \; this \; holds \; for \; all \; q_{i},q_{j}\in Q \; and \; w \in \Sigma ^{*}$

***حل نشده***

ارسال: #۲۳

۱۴ آذر ۱۳۹۱, ۰۹:۲۵ ق.ظ

hp1361 پاسخ داده:

RE: حل تمرین کتاب لینز-بخش ۲-۲

۲۱- یک پذیرنده متناهی غیر قطعی (nfa) که الف) دارای هیچ انتقالات

$\lambda$ نباشد و ب) برای همه

$q \in Q$ و همه

$a \in \Sigma$ ،

$\delta \left ( q,a \right )$ شامل حداکثر یک عنصر باشد، گاهی اوقات یک پذیرنده متناهی قطعی غیرکامل نامیده می شود. این امر معقول است زیرا شرایطی قابل تصور است که هیچ انتخابی جهت حرکت وجود نداشته باشد. برای

$\Sigma =\left \{ a,b \right \}$ ، پذیرنده متناهی قطعی غیرکامل زیر را به یک پذیرنده متناهی قطعی استاندارد تبدیل کنید.

توضیح : در پذبرنده متناهی قطعی غیرکامل، با توجه به اینکه

$\lambda$ و یال تکراری وجود ندارد، لذا جهت تبدیل آن به یک dfa، تنها کاری که لازم است انجام دهیم، تعریف یک تله جهت هدایت یال های تعریف نشده به آن می باشد.

ارسال: #۲۴

۱۵ آذر ۱۳۹۱, ۰۵:۰۵ ق.ظ

csharpisatechnology پاسخ داده:

حل تمرین کتاب لینز-بخش ۲-۲

توی حل سوال ۲
شکل ۲-۸
توی جوابش اصلا احتیاج به آوردن b نبود.به هر حال خلاصه ترم میشد. بد نبود یه توضیحم بنویسی تا دیگه بقیه روی اون b ها شک نکنن.

سعی کنید این مباحث رو ادامه ندید و بیشتر تست هایی رو بیارید+نکات مهم کنکوری.البته ناراحت نشیدا. از اون طرف هم خودتون ببینید مباحثش خیلی مبتدی هست.

موضوع‌های مرتبط با این موضوع...
موضوع:		نویسنده	پاسخ:	بازدید:	آخرین ارسال
	حل تمرین کتاب سیستم های فازی و کنترل فازی	neo.st	۲۳	۴۲,۲۳۳	۳۰ فروردین ۱۴۰۰ ۰۹:۳۵ ق.ظ آخرین ارسال: mahdiyehbakhshi
	حل تمرین شدن و مصاحبه دکتری	siiib70	۱	۳,۷۰۹	۱۷ بهمن ۱۳۹۹ ۱۱:۳۲ ب.ظ آخرین ارسال: hmaryam567
	کمک برای حل تمرین پایگاه داده	zhila1994	۰	۲,۲۴۹	۲۲ آذر ۱۳۹۹ ۰۱:۲۵ ب.ظ آخرین ارسال: zhila1994
	درخواست اپلود کتاب یا لینک دانلود کتاب+معرفی سایت دانلود کتاب	ریحانه	۱۲۹	۸۵,۶۵۸	۱۱ آذر ۱۳۹۹ ۰۸:۳۷ ب.ظ آخرین ارسال: Ariana2020
	[دانلود] کتاب clrs همراه با حل تمرین و پیوست فارسی	mehrdad66	۳۸	۸۹,۷۳۹	۲۴ خرداد ۱۳۹۹ ۰۴:۲۲ ب.ظ آخرین ارسال: Nargeshassani
	نظریه زبانها و ماشینها (پیتر لینز) نگارش پنجم	sina_r11	۱۳	۲۷,۱۵۳	۱۱ خرداد ۱۳۹۹ ۰۲:۲۸ ب.ظ آخرین ارسال: Z78khosrow_kh
	دانلود نظریه زبانهای پیتر لینز ویرایش ۵ + حل	armin.sheikh	۵	۱۲,۶۵۵	۰۲ خرداد ۱۳۹۹ ۰۸:۲۶ ب.ظ آخرین ارسال: gillda
	ریاضی گسسته روزن ویرایش ۷ همراه با کتاب حل تمرین ها	livestrong	۱۲	۲۱,۲۴۶	۱۷ اردیبهشت ۱۳۹۹ ۰۴:۳۷ ب.ظ آخرین ارسال: raziyeh.karbasi
	درخواست حل تمرین	nimaz4	۱	۲,۷۰۹	۲۵ آذر ۱۳۹۸ ۰۳:۵۷ ب.ظ آخرین ارسال: soltanMohammad
	کمک برای حل تمرین امنیت شبکه پیشرفته	behnazk	۰	۲,۲۴۰	۱۴ مهر ۱۳۹۸ ۱۲:۰۷ ب.ظ آخرین ارسال: behnazk

حل تمرین کتاب لینز-بخش ۲-۲

حل تمرین کتاب لینز-بخش ۲-۲

RE: حل تمرین کتاب لینز-بخش ۲-۲

حل تمرین کتاب لینز-بخش ۲-۲

حل تمرین کتاب لینز-بخش ۲-۲

حل تمرین کتاب لینز-بخش ۲-۲

حل تمرین کتاب لینز-بخش ۲-۲

حل تمرین کتاب لینز-بخش ۲-۲

حل تمرین کتاب لینز-بخش ۲-۲

RE: حل تمرین کتاب لینز-بخش ۲-۲

RE: حل تمرین کتاب لینز-بخش ۲-۲

حل تمرین کتاب لینز-بخش ۲-۲

حل تمرین کتاب لینز-بخش ۲-۲

حل تمرین کتاب لینز-بخش ۲-۲

حل تمرین کتاب لینز-بخش ۲-۲

حل تمرین کتاب لینز-بخش ۲-۲

حل تمرین کتاب لینز-بخش ۲-۲

حل تمرین کتاب لینز-بخش ۲-۲

RE: حل تمرین کتاب لینز-بخش ۲-۲

حل تمرین کتاب لینز-بخش ۲-۲

حل تمرین کتاب لینز-بخش ۲-۲

حل تمرین کتاب لینز-بخش ۲-۲

حل تمرین کتاب لینز-بخش ۲-۲

RE: حل تمرین کتاب لینز-بخش ۲-۲

حل تمرین کتاب لینز-بخش ۲-۲

Can I see some ID?

Feeling left out?

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

Feeling left out?