حل تمرین نظریه محاسبات/فصل چهارم/حل تمرین ۴-۱۹

چون M یک DFA است که L(M) را تشخیص می‌دهد پس طبق مسئله 1.24 یک DFA مثل M1 برای تشخیص L(M)R وجود دارد و حال اگر این دو DFA عضو EQDFA باشند یعنی داشته باشیم<M,M1>Є EQDFA نتیجه می‌شود که MЄS زیرا برابر بودن M و M1 به این معنی است که هر رشته‌ای در L(M) باشد معکوس آن را M1 تشخیص می‌دهد و چون M وM1 برابرند پس M هم معکوس آن را تشخیص می‌دهد.