Конечные автоматы - Что это? (попроще)

[Аллиас]

Здравствуйте. Такой вопрос:

Что такое "конечные автоматы" в применении к AS3?

Я читал определение на википедии и еще на нескольких сайтах, и понял что это что-то сродни регулярным выражениям (во всяком случае меня интересует именно такое их применение). Заумные дискретно-математические определения мне не особо понятны, и хотелось бы посмотреть на реализацию автомата "воочию". Но дело в том, что подходящего практического примера на AS3 я не нашел, а других языков программирования я пока не понимаю (ну разве-что JavaScript).

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

[iflamberg]

чего орать-то?

[Герыч]

неконечный автомат?? я знаю только конечные, а в них недетрменированные.
Даже википедия на мой к ней вежливый вопрос "неконечный автомат" написала:

Возможно, вы имели в виду: конечный автомат

И ты вообще хочешь узнать то о них(пусть даже и неконечных=) )?

[Аллиас]

Сообщение от iflamberg

чего орать-то?

Так лучше?

2Герыч

Сори, я и вправду имел ввиду "конечные автоматы", ошибся
и да, я хочу про них узнать побольше

[DarkLight]

и да, я хочу про них узнать побольше

Вузовский учебник по дискретной математике в помощь.

[Герыч]

конечный автомат.. с точки зрения программиста - это интерфейс:

interface StateMachine {
       function reset();
       function sendLetter(letter:Letter);
       function getState():State;
       function isStateGood(state:State):Boolean;
}

у конечного автомата(по теории) есть входная лента(со словом некоторого языка), с которой по очереди берётся по букве a, начальное состояние q0, текущее состояние q, функция перехода q'=g(q,a) и множество хороших состояний.
Ты прогоняешь через автомат слово по буковке. Под действием каждой буквы и текущего состояния автомат меняет своё состояние. В конце слова ты смотришь текущее состояние и узнаёшь, к какому классу относится слово-к хорошему или плохому.
А применительно к интерфейсу псевдо-код примерно такой:

function isWordGood(w:Word,sm:StateMachine):Boolean{
  sm.reset();
  for each(l:Letter in w)
    sm.sendLetter(l);
  return sm.isStateGood(sm.getState());
}

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

[iflamberg]

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

[BlooDHounD]

вообще-то в регулярках рекурсии есть.

[iflamberg]

Как я понимаю, в перле только.
/[abc]+/ - это не рекурсия. Это, как раз таки пример конечного автомата.

Но вообще не хочу флуд разводить, так как вот здесь я никак не гуру - за всю жизнь только три раза регулярки сложные составлял. Вот статья на хабре, если интересно http://habrahabr.ru/blogs/crazydev/63944/

[Аллиас]

Меня на самом деле "конечные автоматы", заинтересовали после того, как я случайно нашел эту ссылку: Парсер BBCode на КА, просто здесь КА выставляют так, что они будто бы сами по себе быстрее РэгЭкспов (теперь я понимаю, что РВ сами есть КА), и еще "конечный автомат" - звучит необычно

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

Всем большое спасибо за предоставленную информацию. Буду тренировать логику, чувствую в серьезном программировании без этого никуда.