2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

 
 
 
 Re: Автомат
Сообщение01.03.2014, 13:17 
Аватара пользователя
Понял. Спасибо!

 
 
 
 Re: Автомат
Сообщение01.03.2014, 13:24 
Аватара пользователя
А разрешается считать, что строка записана на конечной ленте, и состояние ячеек можно менять?

 
 
 
 Re: Автомат
Сообщение01.03.2014, 13:30 
Аватара пользователя
заменять $a,b,c$ можно на единицы или нули. Но слово записано на бесконечной, всё же, ленте

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

 
 
 
 Re: Автомат
Сообщение01.03.2014, 14:20 
Аватара пользователя
svv в сообщении #831662 писал(а):
Так нельзя ли тогда устроить, чтобы каретка ездила влево-вправо и попеременно уничтожала буквы $a$ и $b$ (писала на их месте что-то ещё)?

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

 
 
 
 Re: Автомат
Сообщение01.03.2014, 14:42 
Аватара пользователя
svv, автомат только в одну сторону ездит, в этом то и проблема

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

 
 
 
 Re: Автомат
Сообщение01.03.2014, 15:08 
Аватара пользователя
Это же всего лишь визульное представление, которое намного легче воспринимается, нежели такое громоздкое определение..

 
 
 
 Re: Автомат
Сообщение01.03.2014, 15:21 
Аватара пользователя
Спасибо, я понял, очень жаль. :-)

 
 
 
 Re: Автомат
Сообщение01.03.2014, 15:24 

(Оффтоп)

MestnyBomzh в сообщении #831684 писал(а):
Это же всего лишь визульное представление, которое намного легче воспринимается, нежели такое громоздкое определение..
:shock: Вы о чем? Для него разве есть визуальное представление?
Мне представление в виде орграфа вполне нравится. И оно вполне такое визуальное :roll:

 
 
 
 Re: Автомат
Сообщение01.03.2014, 15:46 
Аватара пользователя

(Оффтоп)

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

 
 
 
 Re: Автомат
Сообщение01.03.2014, 15:51 
Аватара пользователя

(Оффтоп)

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

 
 
 
 Re: Автомат
Сообщение01.03.2014, 15:58 
Аватара пользователя

(Оффтоп)

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

 
 
 [ Сообщений: 17 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group