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

$S\to Sb\left|Ab\right|ϵ$

$A\to Sa|Ab$

${\left(aa\left|abab\right|abaa{b}^{\cdot }a|b\right)}^{\cdot }$

$S\to bS\left|aAaS\right|aAbaS|ϵ$

$A\to aS|bA$

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

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

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

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

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

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

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

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

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

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

$\left\{a^m{b}^n{c}^p|m+n>p\right\}$

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