Комментарии 27
Есть ощущение, что автор оригинала только-только узнал, что существуют конечные автоматы и пытается их запихнуть всюду куда дотягиваются руки.
Это ромбики и овалы со стрелочками?
В любой момент времени система находится в одном из определённых состояний, а переходы инициируются при наступлении ...
Мне всегда было интересно послушать что скажут проповедники конечных автоматов на вопрос:
А в каком состоянии находится конечный автомат в момент перехода?
Но они почему-то всегда избегают ответа на этот вопрос.
Сперва ответьте на два вопроса:
Кто такие "проповедники конечных автоматов"?
С какой стати в системе, где переход не может произойти мгновенно (синхронно, атомарно), применяется автоматный подход?
Интересно, а где это переход может произойти мгновенно?
Пример можете привести?
В лексических анализаторах языков. Там весь переход заключается в одной операции присвоения.
Это классический пример. Вы когда-нибудь задумывались, что "под капотом" у регулярных выражений? А там - конечный автомат (либо автомат с магазинной памятью).
Вы когда-нибудь задумывались, что "под капотом" у регулярных выражений? А там - конечный автомат (либо автомат с магазинной памятью).
мне не надо задумываться, я код вижу.
Конечные автоматы это концепция из прошлого века, если не сказать из прошлого тысячилетия. По ней строились первые процессоры, но даже из архитектуры процессоров она отодвинулась на позицию исторических, хотя конечно фундаментальных знаний, потому что ее практическая ценность стремится к нулю при произошедшем значительном усложнении даже аппаратных систем. Считать состоянием то что записано к килобайтах, а тем более в мегабайтах - это что-то странное - сколько же у вас состояний? больше чем атомов во вселенной?
Регулярные выражения обрабатываются через стек вызовов, одного присваивания там явно не достаточно, исли вы конечно полноценные регулярные выражения имели ввиду, а не то на чем кто-то изучает конечные автоматы.
Конечные автоматы это концепция из прошлого века, если не сказать из прошлого тысячилетия.
Возраст - не повод полностью отказываться от инструмента или методологии. Последовательную запись и выполнение операторов, условные операторы и циклы тоже давным-давно придумали, но ничего, пользуемся и по сей день.
сколько же у вас состояний? больше чем атомов во вселенной?
Всех возможных состояний системы (в автоматном программировании их называют вычислительными) - да, может быть и больше, чем атомов. А вот важных для управления системой (это управляющие состояния) - намного меньше.
Как пример - баланс средств на счете может быть любым, от нуля до бесконечности. Значение баланса - вычислительное состояние. Но для совершения действия в системе (т.е. для управления системой) важно лишь, достаточно ли на счету средств для оплаты покупки. Вычислительных состояний потенциально бесконечно много, но управляющих в данном конкретном примере - всего два.
Примерно всё, что Вы написали в этом посте - неправда.
И реализацию регулярных выражений Вы, очевидно, тоже не смотрели.
Вот сегодня мне потребовалось решить задачу с подсчётом подстрок вида "ab", "ba", изолированное "a" , изолированное "b", причем, если, например, вошло "ab", то его второй символ не может считаться частью "ba" или изолированным "b" - т.е. найденные подстроки не должны пересекаться.
Эту задачу мне оказалось проще описать конечным автоматом, чем регулярным выражением. Состоянием конечного автомата служил предыдущий символ.
Эту задачу мне оказалось проще описать конечным автоматом, чем регулярным выражением
есть некоторая разница между
"мне оказалось проще описать "
и
"мое решение (определенным способом) оказалось проще" - тут вопрос а насколько эффективным было решение тем способом от которого вы отказались, может вы что-то там неправильно поняли и поэтому нашли не самое оптимальное решение из возможных? С чем вы сравнивали? -мы же не знаем.
Ни того ни другого мы, к сожалению, проверить не сможем в этом случае, я полагаю. Поэтому остается только порадоваться вашим успехам, задача решена - это главное!
Для повышения производительности, целесообразно построить по моему КА эквивалентное ему регулярное выражение. (Я пишу на JS, регулярки - "из коробки", следовательно - быстрее).
Я просто хотел сказать, что для удобства разработки парсеров, полезно знать и этот формализм тоже. Не всегда регулярку можно быстро написать "влоб".
Для повышения производительности, целесообразно построить по моему КА эквивалентное ему регулярное выражение.
Я что-то очень сомневаюсь что КА поможет вам (или кому-либо) найти правильное регулярное выражение, потому что, насколько я помню и понимаю, это очень разные подходы, вы либо думаете в терминах КА либо в терминах регулярных выражений, фактически это разные пространства решений, но одно на другое можно натянуть конечно, но такой симбиоз будет очень не эффективным решением насколько я знаю.
Я с регулярными выражениями работал 20 лет назад еще на языке Perl, после нескольких недель практики у меня был восторг от того, что я могу написать любую обработку строк на них запросто, я поэтому это и запомнил, восторг не забывается. Мой вам совет, забудьте хоть на время про КА и попрактикуйтесь в регулярных выражениях, возможно через какое-то время вы увидите мир новыми глазами.
Я что-то очень сомневаюсь что КА
Очень зря. В любом учебнике по КА Вы найдёте теорему, что для любого КА существует эквивалентное ему регулярное выражение, и чисто механический алгоритм построения такового. (Кстати, между прошлым и этим постом, я это сделал).
Это одно пространство решений.
У Вас почему-то сформировалось представление, будто автоматное программирование - это другая вселенная. А на самом деле это просто математический формализм, в некоторых случаях удобный. И, подобно любому другому математическому формализму, он не требует отказываться от всего остального, просто даёт ещё один взгляд на то же самое.
И совет "забыть хоть на время о КА" - очень странный. Я о них вспоминаю сугубо в тех задачах, которые поддаются описанию с их помощью, и только тогда, когда другие решения оказываются слишком непрозрачными (как в этом случае).
Очень зря. В любом учебнике по КА Вы найдёте теорему, что для любого КА существует эквивалентное ему регулярное выражение
в вашем учебнике определен критерий эффективности алгоритма?
Вы можете сравнить эффективность алгоритмов разного типа на конкретной аппаратной платформе? Можете получить числинную абсолютную метрику для сравнения?
Я думаю что нет, и тогда этот учебник на практике бесполезен. То что запрограммировать можно что угодно, мне не надо доказывать я и так это знаю как очевидную аксиому.
Я как раз про это вам и напоминал, про то что это теория из прошлого века, для людей которые все еще сомневаются в возможностях программирования.
Уже давно пора заниматься оценкой эффективности разных способов построения алгоритмов, вместо того чтобы снова и снова доказывать что можно запрограммировать что угодно.
можно даже ввести численную метрику оценки эффективности кода с точки зрения читаемости этого кода! Вы в вашей книжке что-то про это видели? Можете доказать математически что копи-паст в общем случае хуже чем параметризованный код? При этом существуют исключения из этого правила при определенных условиях.
Я к тому что есть в программировании элементарные вещи, про которые прочитать оказывается негде.
Если сосредоточиться на изучении только теории древних греков, вы никогда не дойдете до теории относительности.
Древние греки придумали не самую плохую теорию, наверно даже передовую для своего времени, но только для своего времени.
Не позволяйте одной книжке ограничить ваш кругозор древней теорией!
Мне кажется, тут нужно различать состояния автомата и состояния системы, управляемой автоматом. Автомат должен быть спроектирован и реализован так, чтобы его состояния сменялись мгновенно/синхронно/атомарно. В таких условиях Ваш вопрос будет лишен смысла.
Автомат должен быть спроектирован и реализован так, чтобы его состояния сменялись мгновенно/синхронно/атомарно. В таких условиях Ваш вопрос будет лишен смысла.
Мне кажется что мой вопрос лишен смысла потому что тем кто оперирует терминологией конечных автоматов сейчас совершенно не интересно каким образом меняются состояния, им интересно порассуждать что считать состояниями. Эти рассуждения всегда очень красиво выглядят в глазах аудитории.
Это похоже на переходный процесс и чтобы все было корректно на время переходного процесса система не должна позволять другим процессам ничего менять в текущем. Как способ достижения этого можно взять например транзакцию.
Не статья, а вода просто. Да и заголовок вводит в заблуждение. В любой библиотеке для описания fsm то же самое напишут, только четко и по делу. Зачем тащить бесполезные статьи ноунеймов?
Создаём надёжные API для бэкенда при помощи конечных автоматов: подробное руководство