Как сделать граф машины Тьюринга, который распознает all words with an even number of a's, но является not a decider и ничем другим. Кроме того, как сделать decider машинный граф Тьюринга для того же языка.
Строить решающую машину, а не решающую машину Тьюринга
Ответы (1)
Язык всех слов с четным числом букв a является обычным языком, поэтому простой DFA с двумя состояниями примет этот язык. Та же машина представляет собой решающую ТМ с двумя состояниями, которая не использует ленту ни для чего, кроме чтения ввода.
Чтобы превратить такое решающее устройство в распознающее-не-решающее (поскольку все решающие устройства тоже являются распознавателями), мы должны заставить TM явно распознавать строки с нечетным числом символов «а» и вместо того, чтобы просто останавливать-отклонять, переходить в бесконечный цикл. Это можно легко сделать с помощью одного состояния.
person
Patrick87
schedule
29.06.2020
