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

@secwow · Регистрация: 18.11.2014

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

Здравствуйте!
Есть некое регулярное выражение, по которому нужно построить конечный автомат (x*|y)* , я не как не могу понять как его построить, знак итерации после скобор вводит меня в ступор

@3D Homer · 19.04.2016, 00:23

Чтобы построить автомат с эпсилон-переходами (эпсилон обозначает пустую строку), постройте автомат, принимающий x* | y и добавьте эпсилон-переходы из принимающих состояний в начальное, а также сделайте начальное состояние принимающим.

@secwow · 19.04.2016, 10:12 **[ТС]**

Так?

@3D Homer · 19.04.2016, 17:03

Нет.

Сообщение от 3D Homer

постройте автомат, принимающий x* | y

Если из вашего автомата убрать эпсилон-переходы, он не будет принимать x* | y.

Добавлено через 1 час 49 минут
Можно строить по правилам построения автомата по регулярному выражению, но, если я не ошибаюсь, (x* | y)* = {x, y}*, то есть это язык, содержащий все слова из x и y.

@secwow · 19.04.2016, 17:34 **[ТС]**

Т.е., вот так тоже пойдёт?
Посоветуйте, пожалуйста, книги где про этом можно почитать.

@3D Homer · 19.04.2016, 17:40

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

Т.е., вот так тоже пойдёт?

Да.

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

Посоветуйте, пожалуйста, книги где про этом можно почитать.

Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. «Введение в теорию автоматов, языков и вычислений», 2-е издание, М.: Издательский дом «Вильямс», 2002.

Michael Sipser. «Introduction to the Theory of Computation», 2nd edition, Thomson Course Technology, 2006.

Новые блоги и статьи Все статьи Все блоги /
Памятка для бота и "визитка" для читателей "Semantic Universe Layer (Слой семантической вселенной)" Hrethgir 19.04.2026 Сгенерировано для краткого описания по случаю сборки и компиляции скелета серверного приложения. И пусть после этого скажут, что статьи сгенерированные AI - туфта и не интересно. И это не реклама -. . .	Запрет удаления строк ТЧ документа при определенном условии Maks 19.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "Аккумуляторы", разработанного в конфигурации КА2. У данного документа есть ТЧ, в которой в зависимости от прав доступа. . .	Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .	Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .
My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .

@secwow 0 / 0 / 2 Регистрация: 18.11.2014 Сообщений: 46

	Есть некое регулярное выражение, по которому нужно построить конечный автомат 18.04.2016, 21:01. Показов 2443. Ответов 5 Метки нет (Все метки) Здравствуйте! Есть некое регулярное выражение, по которому нужно построить конечный автомат (x\|y) , я не как не могу понять как его построить, знак итерации после скобор вводит меня в ступор 0

@3D Homer $Эксперт по математике/физике$ 5016 / 3628 / 1164 Регистрация: 01.09.2014 Сообщений: 9,792
	19.04.2016, 00:23
	Чтобы построить автомат с эпсилон-переходами (эпсилон обозначает пустую строку), постройте автомат, принимающий x* \| y и добавьте эпсилон-переходы из принимающих состояний в начальное, а также сделайте начальное состояние принимающим. 1

@secwow 0 / 0 / 2 Регистрация: 18.11.2014 Сообщений: 46
	19.04.2016, 10:12 [ТС]
	Так? Миниатюры 0

@secwow 0 / 0 / 2 Регистрация: 18.11.2014 Сообщений: 46
	19.04.2016, 17:34 [ТС]
	Т.е., вот так тоже пойдёт? Посоветуйте, пожалуйста, книги где про этом можно почитать. Миниатюры 0

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

Решение