Автомат

[MestnyBomzh]

Существует ли конечный автомат, определяющий, верно ли, что во входном слове (в алфавите ${a,b,c}$) одинаковое число букв $a$ и $b$? Мой ответ: нет. Получается, если у нас идут несколько букв $a$ подряд, то нам нужно под каждую букву $a$ выделить состояния, то есть, мы должны помнить количество букв $a$. Например, для слова $aaaaab$ нужно будет по крайней мере $5$ состояний, чтобы помнить сколько $a$ было, но есть у нас будет слово $aaaaaab$, то уже понадобится $6$ состояний, получается, что конечного автомата не существует, так?

[Sonic86]

Так.
Только такие доказательства все-таки считаются неформальными.
Более формальным будет доказательство, использующее лемму о накачке.

[MestnyBomzh]

Понял. Спасибо!

[svv]

А разрешается считать, что строка записана на конечной ленте, и состояние ячеек можно менять?

[MestnyBomzh]

заменять $a,b,c$ можно на единицы или нули. Но слово записано на бесконечной, всё же, ленте

[svv]

Так нельзя ли тогда устроить, чтобы каретка ездила влево-вправо и попеременно уничтожала буквы $a$ и $b$ (писала на их месте что-то ещё)? Ищем $a$ слева, не нашли — ищем справа, ищем $b$ слева и так далее. Не нашли пары — количества не совпадают. Кажется, что можно извернуться.

[nikvic]

svv в сообщении #831662 писал(а):

Так нельзя ли тогда устроить, чтобы каретка ездила влево-вправо и попеременно уничтожала буквы $a$ и $b$ (писала на их месте что-то ещё)?

Поищите различие между м. Тьюринга и конечным автоматом...

[MestnyBomzh]

svv, автомат только в одну сторону ездит, в этом то и проблема

[Sonic86]

Вообще-то автомат никуда не ездит. Автомат - это такой конечный ориентированный орграф с дугами, размеченными символами алфавита. При приеме строки на вход он может перейти в какое-то состояние. Все.

[MestnyBomzh]

Это же всего лишь визульное представление, которое намного легче воспринимается, нежели такое громоздкое определение..

[svv]

Спасибо, я понял, очень жаль.

[Sonic86]

(Оффтоп)

MestnyBomzh в сообщении #831684 писал(а):

Это же всего лишь визульное представление, которое намного легче воспринимается, нежели такое громоздкое определение..

Вы о чем? Для него разве есть визуальное представление?
Мне представление в виде орграфа вполне нравится. И оно вполне такое визуальное

[MestnyBomzh]

(Оффтоп)

Сразу после изучения машины Тьюринга такое представление очень даже к месту...по крайней мере для меня:)

[svv]

(Оффтоп)

Sonic86
У меня эти два представления не противоречат друг другу. Внутри автомата, описанного MestnyBomzh, есть этот орграф. Просто образ, который MestnyBomzh привёл, делает акцент на том, что символы вводятся последовательно, каждый символ только один раз. Вы, кстати, написали, что вводится вся строка сразу.

[MestnyBomzh]

(Оффтоп)

аа, понял оплошность, у меня действительно представление такое, что ввелась сразу вся строка)