1
이것이 가능합니까? 결정자가 {| M은 TM이고 | L (M) | = n}을 결정한다고 가정하십시오. 결정자를 구성하려면 {| M은 TM이고 | L (M) | = n-1} 을 결정하십시오. 가능한 경우 어떻게?결정자가 {<M> | M은 TM이고 | L (M) | = n}을 결정하면 결정자가 n-1을 결정합니다.
A
답변
0
| L (M) | = n - 1, 언어 L (N) = L (M) U {a}에 대해 TM N을 구성하는 것을 상상해보십시오. 여기서 a는 언어 L (M)의 알파벳이 아닌 기호입니다. N은 M이 수락하는 문자열과 M이 수락 할 수없는 다른 하나의 문자열을 정확히 받아들입니다. 따라서 M은 n - 1 개의 문자열을 허용하는 경우에만 N은 n 개의 문자열을 허용합니다. | L (M) | = n - 1이면 N에 대한 결정자를 실행하고 | L (N) | = n.
저는이 문제를 cs.stackexchange.com에서 더 잘 맞는 순수 이론적 인 CS에 관한 것이므로 주제를 벗어난 것으로 끝내기로했습니다. – templatetypedef