Автомат

[mastedm]

Хм, у меня другое определени детерминированного автомата:
Пусть $M = (Q, \Sigma, \delta, q_0, F)$ - конечный автомат. Назовём автомат $M$ детерминированным, если множество $\delta (q,a)$ содержит не более одного состояния для любых $q \in Q$ и $a \in \Sigma$

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

mastedm писал(а):

Хм, у меня другое определени детерминированного автомата:
Пусть $M = (Q, \Sigma, \delta, q_0, F)$ - конечный автомат. Назовём автомат $M$ детерминированным, если множество $\delta (q,a)$ содержит не более одного состояния для любых $q \in Q$ и $a \in \Sigma$

Надо сказать, довольно нестандартное определение. Получается, что автомат вообще без стрелок --- тоже детерминированный?! Странно как-то это...

[mastedm]

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

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

mastedm писал(а):

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

Вы не правы.

[mastedm]

ну да, ведь всегда для недостающих символов можно ввести фиктивное состояние, из которого никогда нельзя попасть в конечное.

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

Совершенно верно.

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

Вот, почитайте, что я первокурсникам рассказываю: http://www.nsu.ru/education/podzorov/Alg/Course.pdf Там вначале всё про автоматы. А то без конца одну и ту же простую тему мусолите.

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

[mastedm]

Не поверите, но у меня достаточно хороших источников и помимо Википедии (у меня с ней нехорошие отношения сложились). Вот правда определения в них несколько различаются.

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

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

Что значит "ложная ветка программы"?

[mastedm]

Если реализовывать автомат в виде программы, то фиктивные состояния можно выкинуть, потому что ветки в эти состояния не приведут к допуску строки

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

Вы программированием занимаетесь или математикой?

Если математикой, то тут всё просто. Есть определение (ДКА или чего-то там ещё), есть объект --- берёте и проверяете, удовлетворяет ли он определению. Определения же в математике даются с целью максимально упростить доказательства, а не с целью упрощения программной реализации.

А если программированием, то Вам тогда, по моему, в другой форум надо: http://dxdy.ru/viewforum.php?f=3

P. S. Анекдот знаете?

Задача номер 1: вскипятить чайник.

Решение физика: налить в чайник воды, нарубить дров, растопить печь, поставить чайник на неё, подождать, когда закипит.

Решение математика: такое же.

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

Решение физика: нарубить дров, растопить печь, поставить чайник на неё, подождать, когда закипит.

Решение математика: вылить воду из чайника, после чего задача сведётся к предыдущей.

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

Господа, ничего если я вмешааюсь?

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

Надо сказать, довольно нестандартное определение.

Нестандартное в какой области? Вот я открываю Ахо А., Ульман Дж. — Теория синтаксического анализа, перевода и компиляции (Том 1. Синтаксический анализ) на странице 138, и читаю:

Определение: Пусть $M=(Q, \Sigma, \delta, q_0,F)$ — недетерменированный конечный автомат. Назовём $M$ детерменированным, если множество $\delta(q, a)$ содержит не более одного состояния для любых $\q \in Q$ и $a \in \Sigma$. Если $\delta(q,a)$ всегда содержит точно одно состояние, то автомат $M$ назовём полностью определённым.

детерминированный = determenistic
полностью определённыё = completely specified

Позвольте уверить, что это определение широко распространено в теории формальных грамматик и формальных языков. Оно вполне разумно: зная состояние автомата и входной символ можно однозначно сказать, в какое состояние он перейдёт. Не это ли есть детерминизм?

mastedm писал(а):

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

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

Фиктивный в программировании обычно применяется в смысле «не являющийся таковым». Например, фиктивный элемент «начало-конец» может замыкать двусвязный список в кольцо, не являясь элементом списка.

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

[mastedm]

Я бы сказал, что занимаюсь больше прикладной математикой.

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

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

P.S. Пока я писал, появилось сообщение Профессора Снэйпа. Хочу добавить, что к какому разделу относится теория формальных грамматик, мне, например, совсем неочевидно. То, что матан используется в физике не делает вопрос по матану частью физического форума.

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

В английской википедии определение ДКА такое, как я говорил (выделение в тексте моё):

Цитата:

In the theory of computation, a deterministic finite state machine or deterministic finite automaton (DFA) is a finite state machine where for each pair of state and input symbol there is one and only one transition to a next state.

См. здесь: http://en.wikipedia.org/wiki/Determinis ... te_machine

В русской википедии определение ДКА таково, как вы говорите. Из текста статьи это непонятно, но то, что это так, видно из иллюстрации: http://ru.wikipedia.org/wiki/%D0%98%D0% ... %D0%90.jpg

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

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

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

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

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

То, что матан используется в физике не делает вопрос по матану частью физического форума.

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

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

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

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

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

Вы не обратили внимание, что Ахо-Ульман — это перевод с англицкого? Я пытался подчеркнуть это, дав перевод терминов из оригинала.

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

чем то, что вы сейчас преподносите.

see ur steps

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

Кроме того, теорема Майхилла-Нероуда для ДКА

От того, что мы в теореме заменим слова «детерменированный» на «полностью определённый», теорема мало пострадает.


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

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

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

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

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