L و L' دو زبان هستند. چند تا از گزارههای زیر درست است؟ (توضیح نماد ≤ : برای دو زبان A و B مینویسیم A ≤ B هرگاه A تقلیلپذیر تورینگی به B باشد.) اگر L تصمیمپذیر باشد و L ≤ L' آنگاه L' تصمیمپذیر است. اگر L ≤ L' و L' ≤ L آنگاه L = L' . اگر L ≠ φ, Σ^() آنگاه L ≤ L^c . ( L^c زبان مکمل L است.)

سوال ۹۵ کنکور ارشد علوم کامپیوتر ۱۳۹۹

نظریه زبان‌ها و ماشین‌هاسختماشین‌های تورینگ

اهمیت

۰/۵

$L$ و $L'$ دو زبان هستند. چند تا از گزاره‌های زیر درست است؟ (توضیح نماد $\le$ : برای دو زبان $A$ و $B$ می‌نویسیم $A \le B$ هرگاه $A$ تقلیل‌پذیر تورینگی به $B$ باشد.)

اگر $L$ تصمیم‌پذیر باشد و $L \le L'$ آن‌گاه $L'$ تصمیم‌پذیر است.
اگر $L \le L'$ و $L' \le L$ آن‌گاه $L = L'$ .
اگر $L \ne \phi,\ \Sigma^{*}$ آن‌گاه $L \le L^{c}$ . ( $L^{c}$ زبان مکمل $L$ است.)

#turing-machine#turing-reducibility#decidability#many-one-reduction#complement#turing-equivalence