Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Построение минимального автомата
|
|
Пусть Â = (A, B, Q, j, y) - это произвольный автомат и Q = { q 1,..., q n}. Отношение неотличимости состояний автомата Â разбивает Q на классы неотличимых состояний: Q 1,..., Q d.
Определим множество состояний Q * = { q 1,..., q d}. Содержательно всякое состояние q i соответствует классу неотличимых состояний Q i.
Определим две вспомогательные функции
h: Q ® { 1,..., d } и x: { 1,..., d } ® { 1,..., n }следующими соотношениями:
1) " q j Î Q (h(q j) = i Û q j Î Q i);
2) " j = 1,..., d (x(j) = i Û i = 
).
Отображение h преобразует состояния автомата Â в номера классов неотличимых состояний, содержащих эти состояния.
Отображение h сопоставляет всякому классу неотличимых состояний состояние этого класса с наименьшим индексом.
Определим автомат Á = (A, B, Q *, F, Y). Функции F и Y этого автомата задаются соотношениями:
1) " a Î A, q i Î Q *(F(a, q i) = q h(j( a , q x (i)));
2) " a Î A, q i Î Q *(Y(a, q i) =y(a, q x(i))).
То есть всякий шаг работы автомата Á из состояния q i для произвольного входного символа аналогичен шагу работы автомата Â из состояния q x( i ) для такого же входного символа.
— Регулярная проверка качества ссылок по более чем 100 показателям и ежедневный пересчет показателей качества проекта.
— Все известные форматы ссылок: арендные ссылки, вечные ссылки, публикации (упоминания, мнения, отзывы, статьи, пресс-релизы).
— SeoHammer покажет, где рост или падение, а также запросы, на которые нужно обратить внимание.
SeoHammer еще предоставляет технологию Буст, она ускоряет продвижение в десятки раз, а первые результаты появляются уже в течение первых 7 дней.
Указанное соответствие представлено на рис. 7.8.
Q i
q x(i) q i
 Á
a (y(a, qx (i))) a (y(a, qx (i)))
Q r
j(a, qx (i)) q r
Рис. 7.8
При этом новое состояние q r автомата Á определяется классом Q j состояний автомата Â, который содержит состояние j(a, q x(i)).
2. Доказательство минимальности автомата Á
Докажем, что " 
Î A *(
() = 
()).
Проведем доказательство этого свойства индукцией по длине слова . При этом дополнительно будет доказываться вспомогательное утверждение: если F*(a, q i)= q r, то j*(a, q x( i ))Î Qr, а состояния j*(a, q x( i )) и q x( r ) являются неотличимыми.
|
|