Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






  • Сервис онлайн-записи на собственном Telegram-боте
    Тот, кто работает в сфере услуг, знает — без ведения записи клиентов никуда. Мало того, что нужно видеть свое расписание, но и напоминать клиентам о визитах тоже. Нашли самый бюджетный и оптимальный вариант: сервис VisitTime.
    Для новых пользователей первый месяц бесплатно.
    Чат-бот для мастеров и специалистов, который упрощает ведение записей:
    Сам записывает клиентов и напоминает им о визите;
    Персонализирует скидки, чаевые, кэшбэк и предоплаты;
    Увеличивает доходимость и помогает больше зарабатывать;
    Начать пользоваться сервисом
  • Построение минимального автомата






    Пусть Â = (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 ) для такого же входного символа.

    Указанное соответствие представлено на рис. 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 ) являются неотличимыми.






    © 2023 :: MyLektsii.ru :: Мои Лекции
    Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
    Копирование текстов разрешено только с указанием индексируемой ссылки на источник.