سوال ۸۸ کنکور ارشد علوم کامپیوتر ۱۴۰۱

دو عبارت زیر را درنظر بگیرید: الف) فرض کنیم M یک NFA (اتوماتای متناهی نامعین) باشد و ′M یک NFA کاملاً شبیه M با این تفاوت که حالت‌های پایانی (پذیرش) ′M غیرپایانی و حالت‌های غیرپایانی ′M در M حالت‌های پایانی شده‌اند. در این‌صورت زبان ′M مکمل زبان M است. ب) فرض کنیم M یک NFA با زبان L باشد و ′M از روی M با پاک‌کردن کلیه یال‌های خروجی از تمام حالت‌های پذیرش به‌دست آمده است. در این‌صورت داریم: $L(M') = \{\, w \in L : w = uv \text{ که } u \in L \text{ و } v \in \Sigma^{+} \text{ وجود ندارد} \,\}$ کدام‌یک از این دو عبارت صحیح است؟