Построить детерминированный автомат для регулярного выражения

@Ivan912 · Регистрация: 26.01.2019

Author24 — интернет-сервис помощи студентам

Построить детерминированный автомат для регулярного выражения ((c+a)b*)* Я построил этот автомат какие состояния будут финальными и почему? Тут в регулярном выражение две звёздочки подряд как правильно это раскрывать? Может ли быть последовательность нулевой длины?

@3D Homer · 17.08.2019, 23:38

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

Сообщение от Ivan912

какие состояния будут финальными и почему?

Очевидно, оба верхних.

Сообщение от Ivan912

Может ли быть последовательность нулевой длины?

Язык вида r* всегда включает в себя пустое слово по определению.

@Ivan912 · 18.08.2019, 07:25 **[ТС]**

почему оба верхних? я так понимаю ,что пустое слово в s0 попадает.А всё остальное ловит s1 поэтому оно финальное

Добавлено через 1 час 57 минут
((c+a)b*)* = (с+a)*b* вот так можно раскрывать?

Добавлено через 21 минуту
знак '+' обозначает обьеденение?

@Катафалк · 18.08.2019, 07:35

Сообщение от Ivan912

((c+a)b*)* = (с+a)*b* вот так можно раскрывать?

Нельзя, например слово b принадлежит второму языку, но не принадлежит первому.

Добавлено через 1 минуту

Сообщение от Ivan912

почему оба верхних? я так понимаю ,что пустое слово в s0 попадает.А всё остальное ловит s1 поэтому оно финальное

Ну вот потому и оба, ты сам на свой вопрос ответил.

@Ivan912 · 18.08.2019, 08:21 **[ТС]**

знак '+' обозначает обьеденение?

Добавлено через 5 минут
ещё такой вопрос как правильно начать строить автомат по этому ((c+a)b*)* я сначала построил для скобок,(c+a) потом посмотрел то что есть две звёздочки и предположил ,что так зацикливается

@3D Homer · 18.08.2019, 15:21

Сообщение от Ivan912

знак '+' обозначает обьеденение?

Обычно да. Если L(r) — язык, описываемый регулярным выражением r, то $https://www.cyberforum.ru/cgi-bin/latex.cgi?L(r_1+r_2)=L(r_1)\cup L(r_2)$ .

Сообщение от Ivan912

ещё такой вопрос как правильно начать строить автомат по этому ((c+a)b*)*

Можно строить либо из здравого смысла, либо по науке. Во втором случае можно преобразовать регулярное выражение в НКА и затем в ДКА. При этом автомат может получиться излишне сложным, но его можно минимизировать известным методом. Преобразование выражения в НКА описывается в разделе 3.2.3 книги Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений. М.: Вильямс, 2008.

Новые блоги и статьи Все статьи Все блоги /
Работа с объемным DOM в javascript Htext 04.04.2025 Сегодня прочитал статью тут о расходах памяти в JS, ее утечках и т. п. И вот что вспомнил из своей недавней практики. Может, кому пригодится. Хотя, в той статье об этом тоже есть. Дело в том, что я. . .	Оптимизация производительности Node.js с помощью кластеризации run.dev 04.04.2025 Масштабирование приложений для обработки тысяч и миллионов запросов — обыденная задача для многих команд. Node. js, благодаря своей асинхронной событийно-ориентированной архитектуре, стал популярной. . .	Управление зависимостями в Python с Poetry py-thonny 04.04.2025 Стандартный инструмент для установки пакетов в Python - pip - прекрасно справляется с базовыми сценариями: установил пакет командой pip install и используешь его. Но что произойдёт, когда разные. . .	Мониторинг с Prometheus в PHP Jason-Webb 04.04.2025 Prometheus выделяется среди других систем мониторинга своим подходом к сбору и хранению метрик. В отличие от New Relic, который использует агентный подход и отправляет данные во внешнее хранилище,. . .	Пакет Context в Golang: Управление потоками и ресурсами golander 04.04.2025 Работа с горутинами в Go часто напоминает управление непослушными детьми - они разбегаются кто куда, делают что хотят и не всегда завершаются вовремя. К счастью, в Go 1. 7 появился пакет context,. . .
Контейнеризация React приложений с Docker Reangularity 03.04.2025 Контейнеризация позволяет упаковать приложение со всеми его зависимостями в автономный контейнер, который можно запустить на любой платформе с установленным Docker. Это существенно упрощает процессы. . .	Свой попап в SwiftUI mobDevWorks 03.04.2025 SwiftUI, как декларативный фреймворк от Apple, предоставляет множество инструментов для создания пользовательских интерфейсов. В нашем распоряжении есть такие API как alerts, popovers, action sheets. . .	Антипаттерны микросервисной архитектуры ArchitectMsa 03.04.2025 Хорошо спроектированная микросервисная система может выдержать испытание временем, оставаясь гибкой, масштабируемой и устойчивой к большинству проблем. Такая архитектура обладает высоким уровнем. . .	std::mutex в C++: Советы и примеры использования bytestream 03.04.2025 std::mutex - это механизм взаимного исключения, который гарантирует, что критический участок кода выполняется только одним потоком в каждый момент времени. Это простое, но могущественное средство. . .	Не удержался от оценки концепции двигателя Стирлинга. Hrethgir 03.04.2025 Сколько не пытался - она выдавала правильные схемы, причём случайно рисовала горячие области в середине, холодные по краям, трубки с краёв в низ и магнит в соединяющей, но при этой выдавала описание. . .

@Ivan912 1 / 1 / 0 Регистрация: 26.01.2019 Сообщений: 92

	Построить детерминированный автомат для регулярного выражения 17.08.2019, 07:56. Показов 4826. Ответов 5 Метки нет (Все метки) Построить детерминированный автомат для регулярного выражения ((c+a)b) Я построил этот автомат какие состояния будут финальными и почему? Тут в регулярном выражение две звёздочки подряд как правильно это раскрывать? Может ли быть последовательность нулевой длины? 0

@3D Homer $Эксперт по математике/физике$ 5014 / 3626 / 1163 Регистрация: 01.09.2014 Сообщений: 9,787
	17.08.2019, 23:38
	Сообщение было отмечено Ivan912 как решение Решение С автоматом я в целом согласен. Вместо двух стрелок из s1 можно сделать одну, помеченную всеми символами. Сообщение от Ivan912 какие состояния будут финальными и почему? Очевидно, оба верхних. Сообщение от Ivan912 Может ли быть последовательность нулевой длины? Язык вида r* всегда включает в себя пустое слово по определению. 1

@Ivan912 1 / 1 / 0 Регистрация: 26.01.2019 Сообщений: 92
	18.08.2019, 07:25 [ТС]
	почему оба верхних? я так понимаю ,что пустое слово в s0 попадает.А всё остальное ловит s1 поэтому оно финальное Добавлено через 1 час 57 минут ((c+a)b) = (с+a)b вот так можно раскрывать? Добавлено через 21 минуту знак '+' обозначает обьеденение? 0

@Катафалк 275 / 472 / 12 Регистрация: 21.06.2019 Сообщений: 2,976
	18.08.2019, 07:35
	Сообщение от Ivan912 ((c+a)b) = (с+a)b вот так можно раскрывать? Нельзя, например слово b принадлежит второму языку, но не принадлежит первому. Добавлено через 1 минуту Сообщение от Ivan912 почему оба верхних? я так понимаю ,что пустое слово в s0 попадает.А всё остальное ловит s1 поэтому оно финальное Ну вот потому и оба, ты сам на свой вопрос ответил. 0

@Ivan912 1 / 1 / 0 Регистрация: 26.01.2019 Сообщений: 92
	18.08.2019, 08:21 [ТС]
	знак '+' обозначает обьеденение? Добавлено через 5 минут ещё такой вопрос как правильно начать строить автомат по этому ((c+a)b) я сначала построил для скобок,(c+a) потом посмотрел то что есть две звёздочки и предположил ,что так зацикливается 0

@3D Homer $Эксперт по математике/физике$ 5014 / 3626 / 1163 Регистрация: 01.09.2014 Сообщений: 9,787
	18.08.2019, 15:21
	Сообщение от Ivan912 знак '+' обозначает обьеденение? Обычно да. Если L(r) — язык, описываемый регулярным выражением r, то $https://www.cyberforum.ru/cgi-bin/latex.cgi?L(r_1+r_2)=L(r_1)\cup L(r_2)$ . Сообщение от Ivan912 ещё такой вопрос как правильно начать строить автомат по этому ((c+a)b) Можно строить либо из здравого смысла, либо по науке. Во втором случае можно преобразовать регулярное выражение в НКА и затем в ДКА. При этом автомат может получиться излишне сложным, но его можно минимизировать известным методом. Преобразование выражения в НКА описывается в разделе 3.2.3 книги Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений. М.: Вильямс, 2008. 1

Построить детерминированный автомат для регулярного выражения

Решение