Может ли FSA рассчитывать?

Это может быть глупый вопрос. Это представляется очевидным , что FSA, так как оно конечно, может рассчитывать только количество символов в его входной строки до числа , ограниченного числа его состояний. Но теперь предположим, что мы оснастили FSA возможностями вывода (например, печати). Тогда было бы очень легко построить машину , способную печатать один символ для каждого символа , который он читает. Будет ли это учитываться? Если нет, то почему нет?

Вместо этого, говоря об FST: я полагаю, что невозможно создать FST, способный отображать строку произвольной длины в двоичное представление (т. Е. Число в системе счисления base-2) ее длины. Но, конечно, тривиально создавать FST, способный отображать строку произвольной длины в строку, содержащую нули (или единицы) одинаковой длины. Но это может считаться подсчетом, не так ли, поскольку FST делает представление длины входных данных. Несколько странное представление, но все же представление, не так ли?

Этот вопрос немного расплывчатый, поэтому здесь есть расплывчатый ответ: перевод унарного в унарный не является точным подсчетом, так как на самом деле машина «не знает», каков был размер ввода «в конце».

Вы, конечно, понимаете это, поэтому ставите под сомнение тот факт, что это действительно считается.

Однако перевод из унарной системы в двоичную представляется более сложной операцией, поскольку она включает в себя не только подсчет, но и арифметику.

Так что, возможно, более точное понятие, вместо того чтобы считать, сравнивать . То есть, учитывая два числа (в одинарных) и , определите, если .1 m n = $1^n$$1^m$$n=m$

Способность делать это сравнение - вот что порождает известный нерегулярный язык . И неспособность NFA считать - то, что делает этот язык нерегулярным.$\{a^nb^n: n\ge 0\}$

Интересно, что этот язык является КЛЛ. И действительно, соответствующая модель автоматов - КПК, имеет возможность делать ограниченное сравнение.

Когда вы говорите о сравнении, преобразователи больше не дают вам никакой дополнительной силы, поэтому вопрос решается в этом смысле.

Дополнительное примечание: совершенно неформально, возможность сравнения двух чисел часто может использоваться для имитации машины с 2 счетчиками Minsky Machine , которая эквивалентна ТМ.

Нет. Конечные автоматы не в счет. Они могут делать вещи, которые похожи на это, но они не могут считать. Они могут даже делать небольшие (жесткие) вычисления (например, определить, делится ли двоичное число на три ), но это не считается.

Маленькая история Вы находитесь на большой прямоугольной площади в знаменитом городе. Местные жители говорят, что площадь на самом деле квадратная. Если вы можете сосчитать, проверьте, совпадают ли горизонтальные и вертикальные числа плиток, считая плитки по сторонам квадрата. Если вы не можете сосчитать, вы все равно можете подтвердить претензию: начните с угла и идите по диагонали. Если вы точно достигнете противоположного угла, у вас есть квадрат.

В вашем примере fsa проверяет, имеет ли строка одинаковое число и , путем подсчета этих чисел на две разные выходные ленты. Другое устройство должно выполнять окончательное сравнение, если только у вас нет уловки, чтобы обрабатывать буквы и попарно и вычеркивать одно против другого. Как на площади.б а $a$$b$$a$$b$

Теперь более формальная модель для сравнения. Согласно теореме Хомского – Шютценбергера каждый бесконтекстный язык является инверсией преобразования конечного состояния языка Дика на две пары скобок (так не указывается) в википедии, но вы должны верить мне). Теперь преобразователь конечного состояния может «принимать» свой контекстно-свободный язык следующим образом (для каждого языка свой преобразователь). На входе преобразует строку в (предполагаемую) серию всплывающих окон и толчков КПК для , затем проверяет, является ли результат поведением нажатия, то есть результат является строкой вT D 2 L = T - 1 ( D 2 ) T L T L D 2 w ∈ T - 1 ( D 2 ) T ( w ) ∈ D $L$$T$$D_2$$L = T^{-1}(D_2)$$T$$L$$T$$L$$D_2$ . (Технические подробности опущены, но это так, как утверждается в теореме Ч-Ша: тогда и только тогда, когда )$w\in T^{-1}(D_2)$$T(w) \in D_2$

Суть в том, что некоторые «вычисления» выполняются преобразователем, но в тесте с скрыта большая мощность . Аналогично вашему примеру, где две буквы отсортированы на двух лентах. $D_2$

@Shaull: Спасибо за ваш ответ! Я новичок в StackExchange и не знаю, как комментировать ответ, поэтому вместо этого я решил написать ответ в надежде, что меня простят.

Хм, мне кажется, что подсчитывает шепард, подсчитывающий своих овец и пишущий отметку на листе бумаги для каждой овцы, которую он видит, или заключенный, подсчитывающий дни, проведенные в тюрьме, который пишет знаки на стене. Почему не отметит n на листке бумаги или на стенке в качестве представления числа n? Разве это не то, что называется подсчетом? AFAICS ничем не уступает (скажем) двоичному представлению, за исключением того, что оно использует больше места.

Я полагаю, что для вас «знать» означает, что в конце у него есть внутреннее представление счета. Тогда, конечно, очевидно, что FSA FST не может вычислить длину произвольной строки. Но если нам не нужны знания в этом смысле, а требуется только, чтобы FSA или FST могли сообщать результат внешнему наблюдателю, то мне кажется, что представление счета в формате подсчета должно быть в порядке.

Кроме того, если FSA оснащен как инкрементным входом, так и выходом, то он в принципе должен иметь возможность использовать свою внешнюю среду в качестве памяти для чтения / записи и, следовательно, быть таким же мощным, как машина Тьюринга. Правильно?

Спасибо, что подняли случай сравнения. Теперь, кажется, тот случай, если мы снимем требование внутреннего представления, и мы только требуем, чтобы машина способна представить результат ан внешнего наблюдателя, то мы могли бы легко построить конечный автомат, который может произвести свой род графическое представление результата. Предположим, ФСМ, после прочтения "aaaaaabbbbbb" написал

000000
000000

затем, поскольку столбцы имеют одинаковую длину, FSM принял строку "aaaaaabbbbbb". Два столбца одинаковой длины означают «да», разные длины означают «нет».

Я предполагаю, что я сгибая правила, но это то, что я хочу, так как я заинтересован в более или менее неявных предположений, которые делаются в области математической лингвистики.

Конечные автоматы могут «считать» в пределах ограниченного диапазона / число шагов , обозначенных переходов состояний. однако они не могут считать за конечное число шагов.

есть смысл , в котором FSA-как машина может рассчитывать. тесно связанная с машиной называется конечными состояния преобразователя . преобразователь действительно может рассчитывать в смысле «водопроводной» вход и выход. один преобразователь может взять входную последовательность (скажем, в двоичном виде) и «преобразовать» ее в выходную последовательность, которая увеличивается. затем один «зацепляет» (идентичные) преобразователи счетчика на 1, каждый из которых увеличивает свой вход на 1 и выводит его. его также как рудиментарный «потоковый алгоритм» .