درس نظریه زبان ها و ماشین ها از جمله دروسی است که دانشجویان به آن کم‌توجهی می‌کنند و نتیجه خوبی از آن کسب نمی‌کنند. اما اگر بتوانید عملکرد خوبی در این درس در کنکور داشته باشید، از دیگران متمایز می‌شوید. در ادامه پاسخ تشریحی نظریه زبان ها و ماشین ها سال ۱۴۰۳ بیان شده است. اگر می‌خواهید پاسخ تشریحی این درس برای کنکور سالهای دیگر را داشته باشید می‌توانید از پلتفرم آزمون یا دوره نکته و تست نظریه زبان ها و ماشین ها استفاده کنید.
فیلم پاسخ تشریحی تستهای نظریه زبان ها و ماشین ها کنکور ارشد کامپیوتر ۱۴۰۳
پاسخ تشریحی نظریه زبان ها و ماشین ها ۱۴۰۳
متوسط ماشین متناهی $M$ به شکل زیر، مفروض است. $L(M)$ معادل زبان تعریف شده توسط کدام مورد است؟ ماشین‌های متناهی
سؤال 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}$
این سؤال گزینه درست ندارد و سازمان سنجش این سؤال را حذف کرد.
آسان کدام مورد، درست است؟ خانواده زبان‌های بازگشتی و شمارش پذیر بازگشتی
راه‌حل اول:
گزینه 3 صحیح است.
گزینه اول: غلط است. زبان‌های شمارش‌پذیر بازگشتی نسبت‌به عمل مکمل باز هستند.
گزینه دوم: غلط است. مجموعه ماشین‌های تورینگ غیرهم‌ارز شمارا است در‌حالی‌که ناشمارا زبان وجود دارد.
گزینه سوم: درست است. زبان معادل ماشین شمارش‌پذیر بازگشتی نام دارد.
گزینه چهارم: غلط است. زبان‌هایی که ماشین تورینگ تصمیم‌گیرنده (decider) دارند الگوریتم عضویت دارند که زبان‌های بازگشتی هستند. اگر ماشین تورینگ به‌ازای ورودی‌هایی وارد حلقه‌ی بی‌نهایت شود که نتوانیم تشخیص دهیم که آیا مشغول کار طولانی هست یا وارد حلقه‌ی بی‌نهایت شده است ماشین تورینگ تصمیم‌گیرنده نیست. گزینه صحیح 3 می‌باشد.
راه‌حل دوم:
طبق خواص زبان های شمارش پذیر بازگشتی (RE) این زبان ها نسبت به عمل مکمل بسته نیستند پس گزینه اول نادرست است.
زبان هایی وجود دارند که نمیتوان برای آن ها ماشین تورینگ رسم کرد(زبان های غیر RE ) گزینه دوم نادرست است.
در مورد گزینه 3 با توجه به این که تمام زبان هایی که برای آن ها ماشین تورینگ وجود دارد حتما برای آن ها گرامر بدون محدودیت وجود دارد و جزو خانواده زبان های RE هستند پس این گزینه صحیح است.
دقت کنید که در حالت کلی عضویت در خانواده زبان های RE تصمیم پذیر نیست پس گزینه 4 نادرست است.
متوسط کدام‌یک از زبان‌های زیر، مستقل از متن نیست؟ خصوصیات زبان‌های مستقل از متن
گزینه 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$ مستقل از متن است.
متوسط کدام مورد، درست است؟ ساده سازی گرامرهای مستقل از متن
راه‌حل اول:
گزینه 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}$
برای حل این سؤال میتوان باتوجه به گرامر گفت هرموقع که $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}$
آشنایی با درس نظریه زبان ها و ماشین ها
درس نظریه زبان ها و ماشین ها به بررسی زبان‌ها و ماشین‌های محض محاسباتی می‌پردازد. این درس پنج تست در کنکور ارشد کامپیوتر دارد. اگر می‌خواهید اطلاعات بیشتری کسب کنید به صفحه درس نظریه زبان ها و ماشین ها مراجعه کنید. همچنین برای آشنایی با تستهای کنکور درس نظریه به صفحه دوره نکته و تست نظریه زبان ها و ماشین ها مراجعه کنید.
روش های دسترسی به پاسخ تشریحی نظریه زبان ها و ماشین ها کنکور ۱۴۰۳
دو روش برای دسترسی به پاسخ تشریحی تمامی تست های درس نظریه زبان ها و ماشین ها در نظر گرفته‌ایم:
دوره نکته و تست نظریه زبان ها و ماشین ها
تمامی تست های درس نظریه زبان ها و ماشین ها به‌صورت تشریحی در د دوره نکته و تست نظریه زبان ها و ماشین ها حل شده است. همچنین در حین حل این تست‌ها به نکات کلیدی اشاره شده است که با دانستن آنها می‌توانید سریع‌تر به تست‌ها پاسخ دهید.
دوره نکته و تست نظریه زبان ها و ماشین ها
پلتفرم آزمون درس نظریه زبان ها و ماشین ها
پلتفرم آزمون و بانک تست و مجموعه سوالات کنکور ارشد کامپیوتر، آی‌تی و علوم کامپیوتر
سیستم قدرتمند آزمون کنکور کامپیوتر - اولین و تنها سیستم آزمون رشته کامپیوتر
داوطلبین کنکور ارشد کامپیوتر، آی‌تی و علوم کامپیوتر، با این پلتفرم نیازی به تهیه هیچ کتابی ندارید، بهتر از هر کتاب مجموعه سوالات
علاوه بر حل تشریحی تمامی تست های درس نظریه زبان ها و ماشین ها، پلتفرم آزمون محیطی برایتان فراهم کرده است که شما می‌توانید با دیگر دانشجویان به رقابت بپردازید، از سؤالات تألیفی استفاده کنید، آزمون شخصی‌سازی شده ایجاد کنید و…. برای کسب اطلاعات بیشتر و ثبت‌نام در پلتفرم آزمون می‌توانید به صفحه پلتفرم آزمون کنکور کامپیوتر مراجعه کنید.
جمع‌بندی
این مقاله به دو روش برای دسترسی به پاسخ تشریحی تمامی تستهای کنکور ارشد کامپیوتر برای درس نظریه زبان ها و ماشین ها اشاره کرده است: (۱) استفاده از دوره نکته و تست نظریه زبان ها و ماشین ها (۲) استفاده از پلتفرم آزمون . با آرزوی موفقیت برای شما داوطلبان عزیز.
چگونه می‌توانم به پاسخ تشریحی تستهای کنکور نظریه زبان ها و ماشین ها دسترسی داشته باشم؟
استفاده از دوره نکته و تست نظریه زبان‌ها و ماشین‌ها یا استفاده از پلتفرم آزمون درس نظریه نظریه زبان‌ها و ماشین‌ها
آیا با تهیه منابع ذکر شده، نیازمند کتاب یا منبع دیگری هستم؟
خیر، این منابع جامعیت کافی دارند و شما نیاز به منبع دیگری ندارید.
