Блог

Итак, язык выглядит следующим образом:

E = {#x1 # x2 … #xi где алфавит равен {0,1} * и ни одна строка не может быть дубликатом другой строки }

Я пытаюсь создать диаграмму состояний для этого, но еще до этого я придумывал алгоритм для ее решения, но проблема, с которой я сталкивался, заключалась в том, что всякий раз, когда я сравниваю первые две строки, мне приходится отмечать каждый символ символом ‘x’. Так как же мне восстановить первую строку? Например, сначала я сравниваю x1 и x2, к тому времени, когда я закончу, в x2 и все символы в x1 будут отмечены ‘x’, поэтому, когда я перейду к x3, x1 не с чем сравнивать.

Вместо того, чтобы помечать рассматриваемые символы крестиком, пометьте их специальными символами, соответствующими помечаемым символам. Итак, вместо того, чтобы писать x для 0 и x для 1, напишите a для 0 и b для 1. Фактически, продолжайте и используйте символы c и d также для замены значений в «самой ранней вещи, которую мне нужно проверить», чтобы вы могли проверить все пары. Высокоуровневое описание машины Тьюринга, использующей эту стратегию, выглядит следующим образом:

1. начните считывать первые входные данные, заменив 0 на c и 1 на d
2. перейдите ко второму входному сигналу, и если второй входной сигнал пока совпадает, запишите a для 0 и b для 1, затем продолжайте. Если это не совпадение, мы знаем, что эти входные данные не совпадают, и мы можем начать сравнивать другие пары. Измените входные данные, которые вы проверяете, только на a и b, и сбросьте первый ввод только на 0 и 1.
3. повторите этот процесс, пропуская все a и b, которые уже есть, чтобы проверить все пары, включающие первый член.
4. как только вы проверите все пары, включающие первый член, вычеркните его (возможно, используя x), а затем повторите весь процесс с оставшимися входными данными

Это проверит все пары и сработает, как ожидалось. Ключ, как вы правильно предположили, в способности восстанавливать части входных данных, что означает, что вам нужны дополнительные символы в вашем ленточном алфавите. Никогда не стесняйтесь вводить ленточные символы — они бесплатны и никогда не повредят.