Построить детерминированный конечный автомат

@aire ara · Регистрация: 13.11.2018

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

Построить детерминированный конечный автомат, распознающий язык L над алфавитом {a,b}, состоящий из цепочек следующего вида: если цепочка содержит два или более вхождений символа a, то она содержит четное число символов b, если одно вхождение a, то число вхождений b нечетное. Цепочки, которые не содержат а, не принадлежат языку. Например, цепочки ab^3, abab^3a, ab^2ababab^2 допускаются, а цепочки b^3, ab^2, a^2ba не допускаются.

Пожалуйста помогите

@3D Homer · 18.01.2019, 23:01

У вас должно быть три уровня по два состояния в каждом. На каждом уровне состояния соответствуют четности количества прочитанных символов b. При каждом прочитанном a вы переходите на следующий уровень, сохраняя номер состояния внутри уровня. Осталось только определить, какие состояния принимающие на каждом уровне.

@aire ara · 19.01.2019, 18:25 **[ТС]**

спасибо

Новые блоги и статьи Все статьи Все блоги /
Результаты исследования от команды MCM (март 2025 г.) Programma_Boinc 07.04.2025 Результаты исследования от команды MCM (март 2025 г. ) В рамках наших текущих исследований мы продолжаем изучать гены, которые имеют наибольшую вероятность развития рака легких, выявленные в рамках. . .	Рекурсивные типы в Python py-thonny 07.04.2025 Рекурсивные типы - это типы данных, которые определяются через самих себя или в сочетании с другими типами, которые в свою очередь ссылаются на исходный тип. В мире программирования такие структуры. . .	C++26: Объединение и конкатенация последовательностей и диапазонов в std::ranges NullReferenced 07.04.2025 Работа с последовательностями данных – одна из фундаментальных задач, с которой сталкивается каждый разработчик. C++ прошел длинный путь в эволюции средств для манипуляции коллекциями – от. . .	Обмен данными в микросервисной архитектуре ArchitectMsa 06.04.2025 Когда разработчики начинают погружаться в мир микросервисов, они часто сталкиваются с парадоксальным правилом: "два сервиса не должны делить один источник данных". Эта мантра звучит повсюду в. . .	PostgreSQL в Kubernetes: Автоматизация обслуживания с CNPG Mr. Docker 06.04.2025 Администраторы баз данных сталкиваются с целым рядом проблем при обслуживании PostgreSQL в Kubernetes: как обеспечить правильную репликацию данных, как настроить автоматическое переключение при. . .
Async/await в TypeScript run.dev 06.04.2025 Асинхронное программирование — это подход к разработке программного обеспечения, при котором операции выполняются независимо друг от друга. В отличие от синхронного выполнения, где каждая последующая. . .	Многопоточность в C#: Синхронизация потоков UnmanagedCoder 06.04.2025 Многопоточное программирование стало неотъемлемой частью разработки современных приложений на C#. С появлением многоядерных процессоров возможность выполнять несколько задач параллельно значительно. . .	TypeScript: Классы и конструкторы run.dev 06.04.2025 TypeScript, как статически типизированный язык, построенный на основе JavaScript, привнес в веб-разработку новый уровень надежности и структурированности кода. Одним из важнейших элементов этой. . .	Многопоточное программирование: Rust против C++ golander 06.04.2025 C++ существует уже несколько десятилетий и его поддержка параллелизма постепенно наращивалась со временем. Начиная с C++11, язык получил стандартную библиотеку для работы с потоками, а в последующих. . .	std::vector в C++: от основ к оптимизации производительности NullReferenced 05.04.2025 Для многих программистов знакомство с std::vector происходит на ранних этапах изучения языка, но между базовым пониманием и подлинным мастерством лежит огромная дистанция. Контейнер std::vector. . .

@aire ara 0 / 0 / 0 Регистрация: 13.11.2018 Сообщений: 7

	Построить детерминированный конечный автомат 18.01.2019, 13:24. Показов 4931. Ответов 2 Метки нет (Все метки) Построить детерминированный конечный автомат, распознающий язык L над алфавитом {a,b}, состоящий из цепочек следующего вида: если цепочка содержит два или более вхождений символа a, то она содержит четное число символов b, если одно вхождение a, то число вхождений b нечетное. Цепочки, которые не содержат а, не принадлежат языку. Например, цепочки ab^3, abab^3a, ab^2ababab^2 допускаются, а цепочки b^3, ab^2, a^2ba не допускаются. Пожалуйста помогите 0

@3D Homer $Эксперт по математике/физике$ 5014 / 3626 / 1163 Регистрация: 01.09.2014 Сообщений: 9,787
	18.01.2019, 23:01
	У вас должно быть три уровня по два состояния в каждом. На каждом уровне состояния соответствуют четности количества прочитанных символов b. При каждом прочитанном a вы переходите на следующий уровень, сохраняя номер состояния внутри уровня. Осталось только определить, какие состояния принимающие на каждом уровне. 1

@aire ara 0 / 0 / 0 Регистрация: 13.11.2018 Сообщений: 7
	19.01.2019, 18:25 [ТС]
	спасибо 0