Автомат

[Профессор Снэйп]

незваный гость писал(а):

Вам не приходилось сталкиваться со школами в математике? и, в частности, с терминологическими традициями школ? В Питере московский терминологический акцент режет ухо.

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

незваный гость писал(а):

Автор темы свернул, я уверен, на то определение, которое давалось у него на лекциях.

Возможно.

Кстати, и Ахо-Ульмана я не читал. Судя по названию, там что-то прикладное и больше для программистов, чем для математиков.

Терминологию при разработке своего курса я в основном заимствовал из книги

H. R. Lewis, C. H. Papadimitriou, Elements of the theory of computation.

Там во введение сказано, что по ней читали курс в Массачусетском Технологическом.

[незваный гость]

Профессор Снэйп писал(а):

Говоря о конечных автоматах, автор темы свернул на практику программирования: дескать, именно эти автоматы я буду считать детерминированными, поскольку они более "естественны" точки зрения программной реализации.

Думаю, что мир устроен проще: автор пишет, что он понимает, playing his strength. А реальным обоснованием терминологии является близость такого автомата к языку и к грамматике. Поскольку грамматика в принципе конструктивный объект, она может не содержать (и обычно не содержит) правил на все случаи жизни. Язык же и вовсе не знает тупиковых состояний — там есть только множество хороших цепочек.

Поскольку превращение детерминированного автомата в полностью определённый — это простой технический шаг, я понимаю Ахо и иже с ним, которые пользовались термином как им удобно.

Есть ещё и исторический аспект: я полагаю, что книга Ахо, опубликованная в Штатах в 1972 году, писалась в то время, когда наука ещё только создавалась, а терминология не устоялась. Может быть, сейчас и Ахо применяет другую терминологию. Для mastedm это безразлично: для него существует только один правльный вариант, вариант лектора.

Добавлено спустя 11 минут 52 секунды:

P.S. В предисловии Ахо А., Ульман Дж. написано, что книга возникла на базе записей лекций, прочитанных на старших курсах Принстона.

Посмотрел я ссылку на Wikipedia. Дык там прямо написано, во перво́й строке: in the theory of computation. Wiki аккуратнее, чем Вы.

[Профессор Снэйп]

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

И вот, надо же --- терминология всё никак устояться не может!

Грамматики, конечно, чуть посложнее, да я о них и мало знаю --- так, на уровне определений, могу сформулировать, что означают классы иерархии Хомского, и всё. Но, боюсь, это всё равно не тот уровень, что $T$-сводимость и степени перечислимости. Зато в практическом плане, вероятно, гораздо больше значат.

Добавлено спустя 1 минуту 15 секунд:

незваный гость писал(а):

Посмотрел я ссылку на Wikipedia. Дык там прямо написано, во перво́й строке: in the theory of computation. Wiki аккуратнее, чем Вы.

Бр-р-р... А мы про какую теорию говорим?

Добавлено спустя 3 минуты 7 секунд:

Кстати, Ахо-Ульман по Вашей ссылке для меня недоступен. В смысле пишут, что скачать книгу нельзя.

[незваный гость]

Профессор Снэйп писал(а):

Бр-р-р... А мы про какую теорию говорим?

Не знаю:!: Автор темы не сказал. Может быть, теорию вычислимости, а может быть — формальные языки.

Профессор Снэйп писал(а):

Кстати, Ахо-Ульман по Вашей ссылке для меня недоступен

Для меня — тоже. Я снимал бумажную с полки.

Добавлено спустя 1 минуту 47 секунд:

Профессор Снэйп писал(а):

Но, боюсь, это всё равно не тот уровень, что $T$-сводимость и степени перечислимости.

Там хватает своих вполне тяжёлых проблем. В частности тех, которые абсолютно не нужны практикам.

[MaхVT]

Профессор Снэйп писал(а):

Впрочем, автомат такой:

Три состояния: $q_1$, $q_2$ и $q_3$. Состояние $q_1$ начальное, оно же заодно и конечное. Других конечных состояний нет. Алфавит состоит из символов $a$ и $b$. Всего в автомате 3 $a$-перехода: из $q_1$ в $q_2$, из $q_2$ в $q_3$ и из $q_3$ в $q_1$ и 3 $b$-перехода: из $q_1$ в $q_3$, из $q_3$ в $q_2$ и из $q_2$ в $q_1$.

Задание такое же: записать регулярное выражение, задающее язык, распознаваемый этим конечным автоматом.

Посмотрим, как я с теорией конечных автоматов познакомился.

Ответ такой получился:

$$\big(a(ab)^{\ast}(aa\cup b)\cup ba\cup bb(ab)^{\ast}(aa\cup b)\big)^{\ast}$$

[Профессор Снэйп]

MaхVT писал(а):

Профессор Снэйп писал(а):

Впрочем, автомат такой:

Три состояния: $q_1$, $q_2$ и $q_3$. Состояние $q_1$ начальное, оно же заодно и конечное. Других конечных состояний нет. Алфавит состоит из символов $a$ и $b$. Всего в автомате 3 $a$-перехода: из $q_1$ в $q_2$, из $q_2$ в $q_3$ и из $q_3$ в $q_1$ и 3 $b$-перехода: из $q_1$ в $q_3$, из $q_3$ в $q_2$ и из $q_2$ в $q_1$.

Задание такое же: записать регулярное выражение, задающее язык, распознаваемый этим конечным автоматом.

Посмотрим, как я с теорией конечных автоматов познакомился.

Ответ такой получился:

$$\big(a(ab)^{\ast}(aa\cup b)\cup ba\cup bb(ab)^{\ast}(aa\cup b)\big)^{\ast}$$

Ответ правильный! Поздравляю!!

Правда автомат симметричный и ответа тоже хочется симметричного. Наверное, красивее было бы преобразовать полученное к выражению

$$ (a(ab)^\ast(aa \cup b) \cup b(ba)^\ast(bb \cup a))^\ast $$

А то одинокое $ba$ без $ab$ в ответе настораживает (хотя, конечно же, ни в коем разе не является ошибкой).

Вот, кстати, ещё одна задача. Она действительно олимпиадная. Но если и её решите, то я буду очень удивлён в случае неполучения Вами пятёрки (Между делом, когда там эта пересдача? Я ещё даже не смотрел расписание на следующий семестр.)