«Как сделать машину Тьюринга из {w ∈ {a, b} ∗ | 2na (w) = 3nb (w)}. Мой вопрос заключается в том, как применить условие» - PullRequest
Новая
       35

«Как сделать машину Тьюринга из {w ∈ {a, b} ∗ | 2na (w) = 3nb (w)}. Мой вопрос заключается в том, как применить условие»

1 голос
/ 22 марта 2019

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

Любые советы / помощь?

1 Ответ

0 голосов
/ 23 марта 2019

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

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

  1. сканирование слева направо, найти 3 вхождения a. Пропустить A, B и b. Измените три, которые вы найдете, на A и вернитесь к началу ленты. Если вы дотронетесь до конца ленты, не пересекая ни a, ни b, остановите прием. Если вы достигли конца ленты, увидев несколько a и b, но не менее трех a, остановите-отклоните. В противном случае перейдите к шагу 2.
  2. сканирование слева направо, найти 2 вхождения б. Пропустить 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
...