Здравствуйте, LaptevVV, Вы писали:

LVV>>>Автомат-распознаватель и автомат-преобразователь — это разные вещи.
N>>Это одна и та же вещь. Только в первом случае у неё выход — "да / нет / ещё не знаю, продолжайте кормить". Иногда первое или второе объединяются с третьим.
LVV>Не совсем.
LVV>В автомате-преобразователе в каждом состоянии запускается некая функция. После ее работы устанавливается новое состояние...
LVV>А в автомате-распознавателе этого делать нет необходимости, достаточно просто установить новое состояние.

В таком случае, распознаватель является частным случаем преобразователя с тривиальной функцией реакции на входное изменение, которая ничего не делает

N>>А личные выпады в таких беседах обычно не украшают.
LVV>Прежде, чем вопросы на форумах задавать, ТС стоило бы сначала хоть что-то почитать.
LVV>А то он о состояниях судит по состояниям алкогольного опьянения.
LVV>И абстрактную машину сравнивает с вольво...
LVV>Подобный ОПЫТ я в сфере программирования учитывать не обязан.

jIMHO, это не опыт. Это психологическая защитная реакция на откровенный пригруз.
Разумеется, эта реакция показывает отсутствие достаточного жизненного опыта, который бы посоветовал сказать что-то в духе "Проф, не грузите попусту, я ничего не понял. Прошу найти другие слова." Как говорил один классик, "ещё 3000 лет назад писали, что молодёжь ленива, невоспитанна и распущенна. С тех пор ничего не изменилось. Наверно, это наследственное."
Но я с ним согласен в том смысле, что надо более адекватно вводить контекст. Даже классическое определение автомата как тройки из множества входных значений, множества состояний и функции перехода лучше, чем введение какой-то "машины", которая сразу вызывает кучу разносторонних и несочетаемых ассоциаций. А в программировании, ящетаю(tm), по крайней мере для процедурных языков, объяснение таких вещей должно происходить иллюстрацией процесса во времени.

Кстати, вот подумал — всё-таки техника старых времён имела то преимущество, что наглядно иллюстрировала прохождение выполнения программ по шагам и по связям между шагами. Умножение чисел на арифмометре "Феликс" было дешёвым способом и прочувствовать алгоритм (механически! моторная память тут очень помогает), и оценить последствия каждой ошибки (лишний или недостаточный сдвиг или поворот). Смартфоны не дадут такой опыт

LVV>Личных выпадов тут нет.
LVV>Сначала хотя бы со статьей Кодта пусть ознакомится — куда я его и послал.

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

Здравствуйте, LaptevVV, Вы писали:

G>>Объясните простым языком что такое конечный автомат? Желательно с примерами.
LVV>Сядьте там и слухайте сюды:
LVV>КА — это машина, которая получает строку (в более общем случае — последовательность не обязательно символов),
LVV>рассматривает эту строку "под микроскопом"
LVV>и признает строку кошерной или не кошерной.
LVV>В более общем случае — преобразует строку в еще чего-нибудь, что пан запрограммирует.
LVV>Конечный — количество состояний этой машины конечно.

Если вы так же читаете лекции, то не завидую вашим студентам.

Здравствуйте, netch80, Вы писали:

LVV>>В автомате-преобразователе в каждом состоянии запускается некая функция. После ее работы устанавливается новое состояние...
LVV>>А в автомате-распознавателе этого делать нет необходимости, достаточно просто установить новое состояние.
N>В таком случае, распознаватель является частным случаем преобразователя с тривиальной функцией реакции на входное изменение, которая ничего не делает
Естественно.
Собственно, автомат преобразователь появился из практических нужд — надо же константы преобразовывать в двоичную форму...
http://inter-vuz.tuit.uz/Elib_baza//INTUIT.ru/html/department/ds/introsaa/4/1.html

LVV>>Прежде, чем вопросы на форумах задавать, ТС стоило бы сначала хоть что-то почитать.
LVV>>А то он о состояниях судит по состояниям алкогольного опьянения.
LVV>>И абстрактную машину сравнивает с вольво...
LVV>>Подобный ОПЫТ я в сфере программирования учитывать не обязан.
N>jIMHO, это не опыт. Это психологическая защитная реакция на откровенный пригруз.
Знаешь, опять повторю: прежде, чем задавать вопрос на форуме, я пытаюсь максимально самостоятельно разобраться в теме. И только если нифига не доходит — пишу вопрос.
У меня был один знакомый программер, который постоянно бегал ко мне с вопросами по всяким мелочам. В конце-концов я его прямо спросил: почему я это знаю, а ты нет — ведь ты старше меня и должен быть опытнее.
Причина была именно в том, что чел предпочитал СПРОСИТЬ, а не докопаться самому. Он так и сказал: так ЛЕГЧЕ.
N>Разумеется, эта реакция показывает отсутствие достаточного жизненного опыта, который бы посоветовал сказать что-то в духе "Проф, не грузите попусту, я ничего не понял. Прошу найти другие слова." Как говорил один классик, "ещё 3000 лет назад писали, что молодёжь ленива, невоспитанна и распущенна. С тех пор ничего не изменилось. Наверно, это наследственное."

Но молодежь же надо воспитывать!
Вот я довольно часто у нынешних 2-3 курсах спрашиваю: ты где и КЕМ работать будешь. В 99% случаев ответ — не знаю...
Хотя некоторые уже работают...
Так и тут: ничего не понимаю. А конкретнее? И выясняется, что студент даже не пытался что-то прочитать и хоть как-то понять.
За 20 лет в универе — насмотрелся.
N>Но я с ним согласен в том смысле, что надо более адекватно вводить контекст. Даже классическое определение автомата как тройки из множества входных значений, множества состояний и функции перехода лучше, чем введение какой-то "машины", которая сразу вызывает кучу разносторонних и несочетаемых ассоциаций. А в программировании, ящетаю(tm), по крайней мере для процедурных языков, объяснение таких вещей должно происходить иллюстрацией процесса во времени.
Должно.
И мы об этом в своем Семантике думаем...
N>Кстати, вот подумал — всё-таки техника старых времён имела то преимущество, что наглядно иллюстрировала прохождение выполнения программ по шагам и по связям между шагами. Умножение чисел на арифмометре "Феликс" было дешёвым способом и прочувствовать алгоритм (механически! моторная память тут очень помогает), и оценить последствия каждой ошибки (лишний или недостаточный сдвиг или поворот). Смартфоны не дадут такой опыт
Да, именно так.
Когда даже не на Феликсе, а на ЭЛКЕ сделаешь численный метод ручками — вопросов практически не остается.
LVV>>Личных выпадов тут нет.
LVV>>Сначала хотя бы со статьей Кодта пусть ознакомится — куда я его и послал.
N>Ваша позиция понятна, но я всё равно думаю, что это не идеальный способ понять концепции состояния и воздействия.
Не знаю. У меня в свое время почему-то проблем с изучением конечных автоматов не возникло ну просто никаких.
Интересно было! Я помнится, на ассмеблере ЕС запрограммировал автомат перевода целого в двоичную систему...

Здравствуйте, LaptevVV, Вы писали:

LVV>На входе — последовательность элементов. Чаще всего — строка символов.
LVV>КА рассматривает эту последовательность символов, и выдает ответ, принадлежит ли эта строка некоему языку или нет.

КА, вообще-то, выдаёт ответ — последовательность переходов (автомат Мили) или последовательность входов в состояния (автомат Мура).
Автоматы Мили и Мура изоморфны.

Частным случаем, когда содержательный вывод находится в двух финальных состояниях, и будет "принадлежит/нет".

Даже лексеры не являются такими банальными да-нет-распознавателями, а сегментируют и классифицируют входной поток символов по лексемам (т.е. там множество финальных состояний, да ещё и нечестных — автомат программно зациклен, переходит в стартовое состояние после выделения очередной лексемы).

Более сложный случай — FST, finite state transformer, — имеет содержательный вывод на промежуточных состояниях.

Примеры FST:
— Вся железная схемотехника; количество состояний определяется количеством регистров или триггеров.
— Регекспы, как ни странно! Скобки в регекспах видели? Они нужны для сегментации, а сегментация — это как раз выводы (ага! скобка!) на промежуточных состояниях.
— Распознавание речи. По-хорошему, человеческий язык — вообще контекстно-зависимый, но грубое приближение — это n-граммы и конечные фразы. Глупо вытаскивать фразу целиком в конечное состояние (получается комбинаторный взрыв), если можно выводить отдельные слова этой фразы по ходу распознавания. Опять же, сегментация.

Здравствуйте, Grundik2, Вы писали:

G>Объясните простым языком что такое конечный автомат? Желательно с примерами.

Есть некоторая система, которая взаимодействует с окружающей средой. На вход от среды система получает какие-то сигналы, в ответа сама что-то выдает. Чтобы система делала что-то более-менее умное, ей необходимо запоминать историю входных сигналов и от этой истории что-то выдавать в ответ. Таких возможных историй, составленных из различных комбинаций входных сигналов, может быть очень много, а запоминать много и то, что было давно, не хочется. Поэтому все такие истории в системе разделены на классы эквивалентности. Скажем, система помнит пять последних сигналов и этого ей хватает, -- вот эти наборы историй из классов и будут памятью системы. Классы историй называют состояниями. В принципе, системе ничего не нужно, кроме как при получении входного сигнала что-то писать на выход и переходить в состояние (класс историй), которое обусловлено этим новым сигналом. Вот так машина и ходит между состояниями по входным сигналам.

ну и добавлю.. если ТС совсем захочется знать теорию, то КА частный вариант цепей Маркова... хм.. если конечно матрицу переходных вероятностей представлять с 1 единицами и в конечном пространстве...

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, Grundik2, Вы писали:

G>>Объясните простым языком что такое конечный автомат? Желательно с примерами.
А>КА это когда реакция на входное событие/воздействие зависит не только от самого события,
А>но и от некого состояния автомата. Например вам наступили на ногу в автобусе, а вы промолчали, вам еще раз наступили,
А>вы сказали больше так не делать, вам снова наступили, а вы дали в морду. Это и есть конечно-автоматное поведение — воздействие было
А>одно и тоже, ваше состояние и ответные действия менялись.

Вышеприведенный текст (с небольшим дополнением) в виде конечного автомата.

Состояния:
— Еду в автобусе, лепота! (Еду)
— Еду в автобусе, WTF? (WTF)

События (входные символы):
— Наступили на ногу
— Прошло 5 минут

Действия системы:
— многозначительно промолчать
— дать в морду

Таблица переходов. Будем записывать таблицу переходов в виде "Состояние + событие = новое состояние (действие)". Т.е. если конечный автомат находиться в некотором "состоянии" и происходит некоторое "событие", то автомат переходит в состояние "новое состояние", возможно при этом выполняя некоторое "действие":

Еду + Наступили на ногу = перейти в состояние WTF (во время перехода в новое состояние "многозначительно промолчать")
WTF + Наступили на ногу = перейти в состояние Еду (во время перехода в новое состояние "дать в морду")
Еду + прошло 5 минут = перейти в состояние Еду
WTF + прошло 5 минут = перейти в состояние Еду

Стартовое состояние автомата — Еду

По сравнение с текстом добавил событие "прошло 5 минут". По хорошему надо бы добавить еще одно состояние автомата — конечное состояние "вышел из автобуса", в которое автомат попадает когда происходит событие "моя остановка".

Здравствуйте, mefrill, Вы писали:

M>Здравствуйте, Grundik2, Вы писали:

G>>Объясните простым языком что такое конечный автомат? Желательно с примерами.

M>Есть некоторая система, которая взаимодействует с окружающей средой. На вход от среды система получает какие-то сигналы, в ответа сама что-то выдает. Чтобы система делала что-то более-менее умное, ей необходимо запоминать историю входных сигналов и от этой истории что-то выдавать в ответ. Таких возможных историй, составленных из различных комбинаций входных сигналов, может быть очень много, а запоминать много и то, что было давно, не хочется. Поэтому все такие истории в системе разделены на классы эквивалентности. Скажем, система помнит пять последних сигналов и этого ей хватает, -- вот эти наборы историй из классов и будут памятью системы. Классы историй называют состояниями. В принципе, системе ничего не нужно, кроме как при получении входного сигнала что-то писать на выход и переходить в состояние (класс историй), которое обусловлено этим новым сигналом. Вот так машина и ходит между состояниями по входным сигналам.

что делает ее конечным автоматом? почему автоматом? можете привести пример?

G>что делает ее конечным автоматом? почему автоматом? можете привести пример?

ты наверно слышал про машины тьюринга

так вот основное свойство конечного автомата -- это то что это НЕ машина Тьюринга.

У машины Тьюринга есть бесконечная лента, а у конечного автомата нет.

Фактически: конечный автомат -- это машина тьюринга которую не снаблили бесконечной лентой.

Здравствуйте, Grundik2, Вы писали:

G>что делает ее конечным автоматом?

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

G>почему автоматом?

Ну автомат, машина. Здесь надо разобраться, что такое машина. Мне нравится определение Марвина Минского: машина -- это модель какого-то процесса. Под процессом подразумевается последовательность событий, протекающих во времени. Модель этой последовательности, понятно, задающая причинно-следственные связи между событиями, и есть машина (автомат). Машина -- это частный случай того, как человек смотрит на Мир. Человек этот Мир моделирует. Если для модели время не играет важной роли, оно отбрасывается и получаем объекты, признаки, отношения между ними и т.п.. Это то, что называется модель ситуации. Если в модели время существенно, то это модель процесса -- машина.

Вообще, есть хорошая книжка Марвина Минского на эту тему: Вычисления и автоматы

G>можете привести пример?

Ну сколь угодно много. Например, пусть во внешней среде имеется два типа сигналов, обозначим их символами "a" и "b". Когда машина начала свое существование нам неизвестно, этот момент утерян где-то во глубине веков. Наша машина будет выдавать сигнал "!", если было два подряд входных сигнала "+", и сигнал "-" -- в противном случае. Предыстории задаются последовательностями (бесконечными, ведь время начала существования машины неизвестно) символов алфавита V = {a,b}. Эти последовательности (предыстории) разобьем на два класса эквивалентности: те, которые заканчиваются на aa, и все остальные. Т.е. имеем:

Класс "aa":

...aababababaa
...bbbbbbbbbaa
...aaaaaaaaaaa
...

Класс "остальные":

...aaaaaaaaaab
...bbbbbbbbbbb
...bbbbbbbbbba
...

Вот эти два класс и есть память системы -- ее состояниям. Каждый раз, получая на вход очередной символ, машина получает новую предысторию входных событий. Таким образом естественно совершается переход в соответствующий класс предысторий -- состояние машины.

Здравствуйте, мыщъх, Вы писали:

LVV>>>"Видимо они там внутри все это производят. И там же внутри все и потребляют. Нельзя ли к вам внутрь?"(с)"
N>>Сильно не уверен, что это их настолько радует. Ментальное поле за 30 лет существенно изменилось.
N>>Я уже того Жванецкого вспоминаю в лучшем случае раз в году...
М>по колбасу и я не понял. в ссср была плохая колбаса? если я правильно помню, колбаса была хорошая, при условии если она была. проблема в том, что ее не было.

Была, но мало. Фактически её производство рассчитывалось только на город, а из города она вывозилась.

М> легенды о добавлении бумаги опровергались тем, что 1 кг бумаги в ссср стоил дороже 1 кг мяса.

По сравнению с городской дотационной ценой (2.20-2.80 для чего-то приличного) — да. По сравнению с реальной (6-9) — нет.

Это одна из ключевых особенностей СССР: не так страшна была плановая экономика сама по себе — она и так практически везде плановая в ключевых отраслях. Но плановая экономика в сочетании с неестественным ценообразованием, дотациями на одно и намеренными завышениями на другое, принципиально не могла работать. Никакие конечные автоматы и машины Тьюринга (в виде компьютеров) этому не помогут

М>кстати, интересно как вв на примере жванецкого объясняет различие между глобальными переменными (с учетом пространства имен) и локальными переменными (с учетом статических).

Присоединяюсь, я бы тоже послушал.

Здравствуйте, Буравчик, Вы писали:

Б>Здравствуйте, Аноним, Вы писали:

А>>Здравствуйте, Grundik2, Вы писали:

G>>>Объясните простым языком что такое конечный автомат? Желательно с примерами.
А>>КА это когда реакция на входное событие/воздействие зависит не только от самого события,
А>>но и от некого состояния автомата. Например вам наступили на ногу в автобусе, а вы промолчали, вам еще раз наступили,
А>>вы сказали больше так не делать, вам снова наступили, а вы дали в морду. Это и есть конечно-автоматное поведение — воздействие было
А>>одно и тоже, ваше состояние и ответные действия менялись.

Б>Вышеприведенный текст (с небольшим дополнением) в виде конечного автомата.

Б>Состояния:
Б>- Еду в автобусе, лепота! (Еду)
Б>- Еду в автобусе, WTF? (WTF)


Хорошее объяснение. Простое, понятное.

Здравствуйте, mefrill, Вы писали:

M>Здравствуйте, Grundik2, Вы писали:

G>>Объясните простым языком что такое конечный автомат? Желательно с примерами.

M>Есть некоторая система, которая взаимодействует с окружающей средой. На вход от среды система получает какие-то сигналы, в ответа сама что-то выдает. Чтобы система делала что-то более-менее умное, ей необходимо запоминать историю входных сигналов и от этой истории что-то выдавать в ответ.

То есть, если у нас есть класс с состоянием, которые нельзя изменить:

class MyClass1(val a: Int) {
  def func1(b: Int) = a * b
}

это не конечный автомат, потому что класс не может изменить своего состояния, потому что a — это константа и может быть задано только один раз (в C# это const a)?

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, Grundik2, Вы писали:

G>>Объясните простым языком что такое конечный автомат? Желательно с примерами.
А>КА это когда реакция на входное событие/воздействие зависит не только от самого события,
А>но и от некого состояния автомата. Например вам наступили на ногу в автобусе, а вы промолчали, вам еще раз наступили,
А>вы сказали больше так не делать, вам снова наступили, а вы дали в морду. Это и есть конечно-автоматное поведение — воздействие было
А>одно и тоже, ваше состояние и ответные действия менялись.

после того, как мне 3 раз наступили на ногу, состояние сбрасывается к первоначальному? или оно сбрасывается только на следующий день?

Здравствуйте, Grundik2, Вы писали:

G>что делает ее конечным автоматом? почему автоматом? можете привести пример?
а) конечным автоматом её делает конечность множеств состояний, входных сигналов и выходных сигналов;
б) автоматом, потомку что работает автоматически, без участия человека;
в) пример — Электрувер Трурля (известен также как Электрибальд).