پاسخ تشریحی نظریه زبان ها و ماشین ها کنکور ارشد کامپیوتر 1403

درس نظریه زبان‌ ها و ماشین‌ هادرس نظریه زبان ها و ماشین هااین صفحه عالی به معرفی درس نظریه زبان‌ها و ماشین‌ها پرداخته است، همچنین به اهمیت درس نظریه در کنکور ارشد کامپیوتر، سرفصل‌ها، معرفی مراجع و فیلم‌های آموزشی این درس پرداخته است. از جمله دروسی است که دانشجویان به آن کم‌توجهی می‌کنند و نتیجه خوبی از آن کسب نمی‌کنند. اما اگر بتوانید عملکرد خوبی در این درس در کنکور داشته باشید، از دیگران متمایز می‌شوید. در ادامه پاسخ تشریحی نظریه زبان ها و ماشین ها سال ۱۴۰۳ بیان شده است. اگر می‌خواهید پاسخ تشریحی این درس برای کنکور سال‌‌های دیگر را داشته باشید می‌توانید از پلتفرم آزمون یا دوره نکته و تست نظریه زبان ها و ماشین ها استفاده کنید.

پاسخ تشریحی نظریه زبان‌ ها و ماشین ها ۱۴۰۳

متوسط ماشین متناهی $M$ به شکل زیر، مفروض است. $L(M)$ معادل زبان تعریف شده توسط کدام مورد است؟ ماشین‌های متناهی

1 $\begin{array}{c} S\to Sb|aAb|\varepsilon \\ A\to Sa|bAa\ \ \ \ \end{array}$

2 $\begin{array}{c} S\to Sb|Ab|\varepsilon \\ A\to Sa|Ab\ \ \ \ \end{array}$

3 ${\left(a\left.a\right|abab|abaab^*a|b\right)}*$

4 $\begin{array}{c} S\to bS|aAaS|aAbaS|\varepsilon \\ A\to aS|bA\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \end{array}$

سؤال 46) گزینه صحیح ندارد. سؤال حذف شده است.

اگر $\mathit{\Sigma}=\left\{a,b\right\}$ درنظر بگیریم ماشین متناهی $M$ قطعی است و گرامر آن به‌شکل

$\begin{array}{c}S\to aB\left|bC\right|\varepsilon \\ B\to aS|bB\ \ \ \ \\ C\to bS\left|aB\right|\varepsilon \ \end{array}$

است که در گزینه‌ها نیست. برای حل این سؤال بهترین راه تولید جملات هر گزینه و مقایسه‌ی آن با جملات تولیدی ماشین $M$ می‌باشد. اگر تمام جملات تولیدی توسط گرامر یا عبارت منظم توسط ماشین $M$ تولید می‌شد و برعکس گرامر یا عبارت منظم با ماشین $M$ معادل است. درنتیجه ما دنبال مثال نقض می‌گردیم تا گزینه‌ها را رد کنیم.

گزینه‌ی اول:

$\begin{array}{cc}S{{\stackrel{2}{\Rightarrow}}}aAb{{\stackrel{5}{\Rightarrow}abAab{{\stackrel{4}{\Rightarrow}abSaab{{\stackrel{3}{\Rightarrow}abaab\times \text{پذیرفته} \mathrm{\ }\text{نمی‌شود}\ \mathrm{M}\ \text{این}\mathrm{\ }\text{کلمه}\mathrm{\ }\text{توسط}}}}}}} & \ \ \ \ \ \ \ \begin{array}{c} S\to Sb^1|aAb^2|{\varepsilon }^3 \\ A\to Sa^4|bAa^5\ \ \ \ \ \ \end{array} \end{array}$

این گزینه صحیح نیست.

گزینه دوم:

$\begin{array}{cc}S{{\stackrel{2}{\Rightarrow}}}Ab{{\stackrel{4}{\Rightarrow}}}Sab{{\stackrel{3}{\Rightarrow}}}ab\times \text{پذیرفته}\mathrm{\ }\text{نمیشود}\ \mathrm{M}\ \text{این}\mathrm{\ }\text{کلمه}\mathrm{\ }\text{توسط }& \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \begin{array}{c}S\to Sb^1\left|Ab^2\right|{\varepsilon }^3 \\ A\to Sa^4|Ab^5\ \ \ \ \ \ \end{array} \end{array}$

این گزینه صحیح نیست.

گزینه سوم:

${(aa|abab|abaab^*a|b)}^*$

عبارت $abaab^*a$ ،$aa$ ماشین را در حالت $q_0$ قرار می‌دهد درنتیجه ${(aa+abaab^*a)}^*$ ماشین را درحالت $q_0$ قرار می‌دهد و توسط $M$ پذیرفته می‌شود.

عبارت‌های $abab$ ،$b$ ماشین را در حالت $q_2$ قرار می‌دهند، $q_2$ حالت پذیرفته‌شده است امّا به‌دليل اين‌كه حالت شروع نيست بايد تركيب‌های آن با بقيه كلمات بررسی شود.

$\begin{array}{ccc}abababab\ \ \ \ \ \ \ \ \ & در\mathrm{\ }\text{حالت}\ {\mathrm{q}}_{\mathrm{2}}\mathrm{\ }\text{قرار}\mathrm{\ }\text{می‌گیرد}\mathrm{\ M\ }\text{ماشین }& \checkmark \\ ababaa\ \ \ \ \ \ \ \ \ \ \ \ \ \ & \text{در}\mathrm{\ }\text{حالت}\ {\mathrm{q}}_0\mathrm{\ }\text{قرار}\mathrm{\ }\text{می‌گیرد}\mathrm{\ }\mathrm{M}\mathrm{\ }\text{ماشین }& \checkmark \\ abababaab^*a\ \ & \text{در}\mathrm{\ }\text{حالت}\ {\mathrm{q}}_0\mathrm{\ }\text{قرار}\mathrm{\ }\text{می‌گیرد}\mathrm{\ }\mathrm{M}\mathrm{\ }\text{ماشین }& \checkmark \\ ababb\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ & \text{در}\mathrm{\ }\text{حالت}\ {\mathrm{q}}_0\mathrm{\ }\text{قرار}\mathrm{\ }\text{می‌گیرد}\mathrm{\ }\mathrm{M}\mathrm{\ }\text{ماشین }& \checkmark \end{array}$

برای $b$ نیز دقیقاً همین حالات برقرار است. با این مرحله به این نتیجه رسیدیم که عبارت منظم گزینه 3 حداقل زیرمجموعه‌ی ماشین $M$ می‌باشد امّا با کمی دقت می‌توان یافت که کلمه‌ی $ab^*a$ توسط گزینه 3 قابل تولید نیست در‌حالی‌که ماشین $M$ آن‌را می‌پذیرد.

گزینه چهارم:

$\begin{array}{cc}S{{\stackrel{2}{\Rightarrow}}}aAaS{{\stackrel{0}{\Rightarrow}aaSaS{{\stackrel{4,4}{\Longrightarrow}aaa\ \times \text{پذیرفته}\mathrm{\ }\text{نمی‌شود}\ M\ \text{این}\mathrm{\ }\text{کلمه}\mathrm{\ }\text{توسط}\mathrm{\ \ \ \ }}}}} & \begin{array}{c}\ \ \ S\to bS^1|aAaS^2|aAbaS^3|{\varepsilon }^4 \\ A\to aS^5|bA^6\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \end{array} \end{array}$

این سؤال گزینه درست ندارد و سازمان سنجش این سؤال را حذف کرد.

آسان کدام مورد، درست است؟ خانواده زبان‌های بازگشتی و شمارش پذیر بازگشتی

1 زبان‌های شمارش‌پذیر بازگشتی، نسبت به عمل مکمل بسته‌اند.

2 تعداد ماشین‌های تورینگِ غیرهم‌ارز، برابر با تعداد زبان‌هاست.

3 تمام زبان‌های پذیرفته‌شده توسط ماشین تورینگ، شمارش‌پذیر بازگشتی هستند.

4 به‌ازای تمام زبان‌هایی که ماشین تورینگ پذیرنده دارند، می‌توان الگوریتم عضویت پیشنهاد داد.

راه‌حل اول:

گزینه 3 صحیح است.

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

گزینه دوم: غلط است. مجموعه ماشین‌های تورینگ غیرهم‌ارز شمارا است در‌حالی‌که ناشمارا زبان وجود دارد.

گزینه سوم: درست است. زبان معادل ماشین شمارش‌پذیر بازگشتی نام دارد.

گزینه چهارم: غلط است. زبان‌هایی که ماشین تورینگ تصمیم‌گیرنده (decider) دارند الگوریتم عضویت دارند که زبان‌های بازگشتی هستند. اگر ماشین تورینگ به‌ازای ورودی‌هایی وارد حلقه‌ی بی‌نهایت شود که نتوانیم تشخیص دهیم که آیا مشغول کار طولانی هست یا وارد حلقه‌ی بی‌نهایت شده است ماشین تورینگ تصمیم‌گیرنده نیست. گزینه صحیح 3 می‌باشد.

راه‌حل دوم:

طبق خواص زبان های شمارش پذیر بازگشتی (RE) این زبان ها نسبت به عمل مکمل بسته نیستند پس گزینه اول نادرست است.

زبان هایی وجود دارند که نمیتوان برای آن ها ماشین تورینگ رسم کرد(زبان های غیر RE ) گزینه دوم نادرست است.

در مورد گزینه 3 با توجه به این که تمام زبان هایی که برای آن ها ماشین تورینگ وجود دارد حتما برای آن ها گرامر بدون محدودیت وجود دارد و جزو خانواده زبان های RE هستند پس این گزینه صحیح است.

دقت کنید که در حالت کلی عضویت در خانواده زبان های RE تصمیم پذیر نیست پس گزینه 4 نادرست است.

متوسط کدام‌یک از زبان‌های زیر، مستقل از متن نیست؟ خصوصیات زبان‌های مستقل از متن

1 $L=\left\{a^tb^t\left.c^{2t}\right|t>0\right\}$

2 $L=\left\{a^tb^{t+m}\left.c^m\right|t,m>0\right\}$

3 $L=\left\{a^tb^m\left.c^{t+m}\right|t,m>0\right\}$

4 $L=\left\{a^tb^{t-m}\left.c^m\right|t>m>0\right\}$

گزینه 1 صحیح است.

به‌طور کلی برای حل این تیپ سؤالات باید دید آیا زبان‌های داده‌شده می‌توانند با pushdown automate پیاده‌سازی شوند یا خیر. اگر PDA معادل برای زبان وجود داشت زبان مستقل از متن است.

گزینه اول: $L=\left\{a^tb^t\left.c^{2t}\right|t>0\right\}$

اگر به‌ازای هر $a$ در ورودی، “0” در استک، push کنیم مجبوریم برای شمارش تعداد $b$ ها و بررسی و برابری آن با تعداد $a$ ها “0” ها را pop کنیم، درنتیجه نمی‌توانیم تعداد $c$ ها را ارزیابی کنیم. درنتیجه زبان مستقل از متن نیست و این گزینه صحیح است.

گزینه دوم: $L=\left\{a^tb^{t+m}\left.c^m\right|t,m>0\right\}=\left\{a^tb^tb^m\left.c^m\right|t,m>0\right\}$

باتوجه به استدلال ذکر شده در گزینه 1 زبان مستقل از متن است. می‌توان استدلال اشاره شده را به شکل زیر خلاصه کرد.

$\begin{array}{c}a^t\ \ \ \ \ \ b^t\ \ \ \ \ \ b^m\ \ \ \ c^m \\ \diagdown / \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \diagdown / \ \\ \mathrm{\ push\ pop\ \ \ \ \ push\ pop\ \ } \end{array}$

خط‌های رسم شده نشانه pop ،push است. هرخط push، فقط یک خط pop باید داشته باشد و خط‌ها نیز نباید یکدیگر را قطع کنند. برای یادگیری بهتر این روش به فیلم‌های درس نظریه زبان استاد کاشفی مراجعه کنید.

گزینه سوم: $\begin{array}{c}L=\left\{a^tb^m\left.c^{t+m}\right|t,m>0\right\} \\ L=\left\{a^tb^mc^m\left.c^t\right|t,m>0\right\} \end{array}$

می‌توان نوشت:

$\begin{array}{cccc}a^t\ \ \ & b^m & \ \ \ c^m & \ \ \ \ \ c^t \\ \backslash & \ \ \backslash & / & / \\ \ \ \ \ \backslash & \mathrm{push} & \mathrm{pop} & /\ \ \ \ \\ \ \ \ \ \ \ \ \ \backslash & \ & \ & /\ \ \ \ \ \ \ \ \\ \ \ \ \ \ \ \ \ \ \ \ \ \backslash & \mathrm{push} & \mathrm{pop} & /\ \ \ \ \ \ \ \ \ \ \ \ \end{array}$

تقاطع وجود ندارد و از هر خط push یک خط pop خارج شده است پس $L$ مستقل از متن است.

گزینه چهارم:

$L=\left\{a^tb^{t-m}\left.c^m\right|t>m>0\right\}$

می‌توان $t=n+m$ نوشت که در این‌صورت $L$ برابر:

$L=\left\{a^{n+m}b^n\left.c^m\right|q_{n>0,m>0}\right\}$

$L=\left\{a^ma^nb^n\left.c^m\right|n>0,m>0\right\}$

می‌توان نوشت $\begin{array}{cccc}a^m & a^n\ \ \ & {\ \ \ \ \ b}^n & \ \ \ \ c^m \\ \begin{array}{c}\backslash \\ \ \ \ \ \backslash \\ \ \ \ \ \ \ \ \ \backslash \\ push \end{array} & \begin{array}{c}\backslash \\ push \end{array} & \begin{array}{c}/ \\ pop \end{array} & \begin{array}{c}/ \\ /\ \ \ \ \\ /\ \ \ \ \ \ \ \ \\ pop \end{array} \end{array}$، تقاطع وجود ندارد و از هر خط push یک خط pop خارج شده است. پس $L$ مستقل از متن است.

متوسط کدام مورد، درست است؟ ساده سازی گرامرهای مستقل از متن

1 الگوریتم پویش (parsing) برای زبان‌های مستقل از متن، همیشه از مرتبه نمایی است و به فرم گرامر وابسته نیست.

2 اگر گرامر یک زبان مستقل از متن، گرامری ساده (s-grammar) باشد، آن‌گاه می‌توان الگوریتم پویش (parsing) با مرتبه خطی از طول رشته‌های آن زبان داشت.

3 اگر گرامر یک زبان مستقل از متن، گرامری ساده (s-grammar) باشد، آن‌گاه می‌توان الگوریتم پویش (parsing) با مرتبه خطی از طول رشته‌های آن زبان داشت.

4 اگر قوانین لامبدا (اپسیلون) ($\lambda$ – Productions) را از یک گرامر یک زبان مستقل از متن حذف کنیم، آن‌گاه می‌توان الگوریتم پویش (parsing) با مرتبه خطی از طول رشته‌های آن زبان داشت.

راه‌حل اول:

گزینه 3 صحیح است.

بررسی گزینه‌ها:

گزینه اول: الگوریتمی به‌نام CYK وجود دارد که الگوریتم پارس برای گرامرهای Context-free (مستقل از متن) می‌باشد که در آن پیچیدگی الگوریتم وابسته به اندازه‌ی رشته ورودی و از مرتبه‌ی $O(|w|^3)$ می‌باشد.

گزینه 1 نادرست است چرا که مرتبه به فرم پویش وابسته است و مثلا فرم نرمال چامسکی با فرم غیر چامسکی یکسان نیست.

گزینه دوم: الگوریتم پویش از مرتبه $O(|w|^3)$ است.

گزینه سوم: درست است. اگر فرم از نوع S گرامر باشد با توجه به نوع گرامر میتوان با مرتبه خطی رشته را ساخت گزینه 3 صحیح است.

گزینه چهارم: غلط است، چون حذف لاندا تغییری ایجاد نمیکند.

متوسط کدام مورد، زبان تولید شده توسط گرامر زیر را توصیف می‌کند؟ زبان‌های مستقل از متن

$\begin{array}{c} S\to aSc\left|aS\right|A\ \ \ \ \ \ \ \ \ \ \ \\ A\to bAcc|bA|bAc|\varepsilon \end{array}$

1 $\left\{a^mb^n\left.c^p\right|2m+n\ge p\right\}$

2 $\left\{a^mb^n\left.c^p\right|m+2n\ge p\right\}$

3 $\left\{a^mb^n\left.c^p\right|m+n>p\right\}$

4 $\left\{a^mb^n\left.c^p\right|2m+2n\ge p\right\}$

برای حل این سؤال می‌توان باتوجه به گرامر گفت هرموقع که $c$ تولید می‌شود، حتماً $a$ و $b$ نیز تولید می‌شود. در قانون $S \to aSc$ به‌ازای هر $c$ یک $a$ تولید می‌شود، همچنین $a$ می‌تواند به‌تعداد دلخواه تولید شود که اگر تعداد $a$ را برابر $m$ و تعداد $c$ ها را برابر با $p$ بگیریم (باتوجه به فرض سؤال) داریم $m \ge p$. در قانون $A \to bAc$ به‌ازای هر $c$ یک $b$ تولید می‌شود و در قانون $A \to bAcc$ به‌ازای هر $2c$ یک $b$ تولید می‌شود و در قانون $A \to bA$ به هر اندازه که بخواهیم می‌توانیم $b$ تولید کنیم باتوجه به قوانین تولید $b$

اگر تعداد $b$ ها را برابر $n$ بگیریم تعداد آن در حالت که فقط از قانون $A \to bAcc$ استفاده می‌شود $2n=p$ است که با استفاده از قانون‌های دیگر به $2n \ge p$ تبدیل می‌شود.

باتوجه به $2n \ge p \ ، m \ge p$ گفت که $m+2n \ge p$ است که در آن $m+2n$ کمترین مقدار $p$ است.

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

$S\Rightarrow aSc\Rightarrow a^nSc^n\Rightarrow a^na^pSc^n\Rightarrow a^na^pAc^n\Rightarrow a^na^pb^kAc^{2k}c^n\Rightarrow a^na^pb^kb^tAc^{2k}c^n$

درصورتی‌که $t$ و $p$ صفر باشند و $A$ برابر 4 باشد.

$\begin{array}{c}\to a^nb^kc^{2k}c^n\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\ n+2k=2k+n \end{array}$

آشنایی با درس نظریه زبان‌ ها و ماشین ها

روش‌ های دسترسی به پاسخ تشریحی نظریه زبان ها و ماشین ها کنکور ۱۴۰۳

دو روش برای دسترسی به پاسخ تشریحی تمامی تست‌‌ های درس نظریه‌ زبان ها و ماشین ها در نظر گرفته‌ایم:

دوره نکته و تست نظریه زبان ها و ماشین ها

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

دوره نکته و تست نظریه زبان ها و ماشین ها

پلتفرم آزمون درس نظریه زبان‌ ها و ماشین ها

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

جمع‌بندی

این مقاله به دو روش برای دسترسی به پاسخ تشریحی تمامی تست‌‌های کنکور ارشد کامپیوتر برای درس نظریه زبان‌ ها و ماشین ها اشاره کرده است: (۱) استفاده از دوره نکته و تست نظریه زبان ها و ماشین ها (۲) استفاده از پلتفرم آزمون . با آرزوی موفقیت برای شما داوطلبان عزیز.