Блог

Это задание, которое у меня есть для модуля. Я разбираюсь в машинах Тьюринга, проблема для меня в том, как мне убедиться, что соотношение сохраняется. Я вижу, как можно было бы это проверить, если бы мы могли проверять каждые 5 цифр без смешивания (например, {aababaabab}), но для таких слов, как: {aaaaaabbbb}. Очень растерян.

Есть какие-нибудь советы / помощь?

Я предполагаю, что это означает, что соотношение n / m = 3/2, где n — количество вхождений a, а m — количество вхождений b.

Для решения общего случая возможно множество решений; вот одно, которое может быть легко понять.

1. просматривая слева направо, найдите 3 вхождения a. Пропустите A, B и b. Замените три найденных a на A и вернитесь к началу ленты. Если вы нажмете на конец ленты, не пересекая ни a, ни b, остановитесь -примите. Если вы дошли до конца ленты, увидев несколько a и b, но не по крайней мере три a, остановите -отклоните. В противном случае переходите к шагу 2.
2. просматривая слева направо, найдите 2 вхождения b. Пропустите A, B и a. Замените два найденных b на B и вернитесь к началу ленты. Если вы дойдете до конца, не увидев хотя бы двух b, остановите -отклоните. Повторяйте, начиная с шага 1, пока не остановите принятие или не остановите отклонение.

Примеры:

 aababaabab    aaaaaabbbb     aaaaabbbb
AAbAbaabab    AAAaaabbbb     AAAaabbbb
AABABaabab    AAAaaaBBbb     AAAaaBBbb
AABABAAbAb    AAAAAABBbb     halt_reject
AABABAABAB    AAAAAABBBB
halt_accept   halt_accept