حل تمرین نظریه محاسبات/فصل اول/حل تمرین1-33

حل تمرین 1-33

تمرین

تعریف غیر رسمی تراگذار با حالت محدود را در تمرین 1-19 مطالعه کنید. ثابت کنید که هیچ تراگذار با حالت محدودی نمی‌تواند خروجی wR را برای ورودی w تولید کند اگر w و wR را روی الفبای {0, 1} تعریف شده باشد.

حل

چون در w بعضی از انتقالات ممکن است چندین ترکیب مختلف از ورودی و خروجی داشته باشد بنابراین هیچ تراگزار با حالت محدودی نمی تواند خروجی معکوس برای ورودی w تولید کند (روی الفبای صفر و یک).

--Mazinani88 ‏۱۸ آوریل ۲۰۰۹، ساعت ۰۷:۲۲ (UTC)