Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 2 ] 
Автор Сообщение
 Заголовок сообщения: Построение ДКА по НКА
СообщениеДобавлено: 13 фев 2013, 08:19 
Не в сети
Начинающий
Зарегистрирован:
13 фев 2013, 08:17
Сообщений: 1
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Есть такое регулярное выражение:

b {c V a} V {a V c} bc {a V b}

По нему автомат получается недетерминированным, т.к. по состоянию 0 по b идем в состояние 1 и через 0 по b идем в 6 одновременно. Как можно преобразовать автомат в детерминированный? Может, алгоритм где-то есть точный?

Где найти алгоритм построения не по недетерминированному графу, а по самому регулярному выражению? Т.е. я строю таблицу переходов и выходов, а ее надо как-то дополнить, чтобы автомат стал детерминированным. Как это сделать?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Построение ДКА по НКА
СообщениеДобавлено: 13 фев 2013, 13:22 
Не в сети
Последняя инстанция
Аватара пользователя
Зарегистрирован:
03 апр 2012, 03:09
Сообщений: 4112
Cпасибо сказано: 116
Спасибо получено:
1823 раз в 1515 сообщениях
Очков репутации: 379

Добавить очки репутацииУменьшить очки репутации
Посмотрите в книжке Серебрякова "Теория и реализация языков программирования". Там можно найти алгоритм преобразования НКА в ДКА. Вроде бы там даже есть построение ДКА сразу по РВ, но не уверен.

Мне, правда, не совсем понятно, как у Вас получился НКА по такому выражению. У меня сразу получился ДКА, вот таблица:

[math]\begin{array}{l|c|c|c|}&a&b&c\\\hline0(\mathrm{start})&3&1&3\\\hline1&2&&2\\\hline2(\mathrm{end})&&&\\\hline3&&4&\\\hline4&&&5\\\hline5&2&2&\\\hline\end{array}[/math]

Или я что-то не так в РВ понял? Сразу предупреждаю: как Вы РВ написали, так я его и понял :)

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Human "Спасибо" сказали:
mad_math
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 2 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Построение равнобедренной трапеции - задача на построение

в форуме Геометрия

maksim03

15

757

29 апр 2022, 10:25

Геометрическое построение на плоскости(анализ, построение,

в форуме Аналитическая геометрия и Векторная алгебра

ahgel1990

1

683

15 дек 2014, 02:54

Построение ЛЭП

в форуме MATLAB

creidid

1

550

07 июн 2017, 17:48

Построение

в форуме Геометрия

Andreww

2

414

28 мар 2018, 21:18

Построение графика

в форуме Информатика и Компьютерные науки

[Rita]

4

346

19 май 2019, 22:25

Построение с однойлинейкой

в форуме Размышления по поводу и без

Race

45

1509

19 май 2017, 11:17

Построение сечений

в форуме Геометрия

Dobromira

1

354

11 ноя 2014, 19:17

Задача на построение

в форуме Геометрия

v_i_t_a_l_0012

2

209

22 дек 2019, 16:18

Задача на построение

в форуме Геометрия

v_i_t_a_l_0012

3

308

22 дек 2019, 16:54

Построение ЛК из строк

в форуме Теория чисел

Nataly-Mak

6

336

27 дек 2019, 21:05


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 24


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved