2 / 2 / 0
Регистрация: 21.02.2019
Сообщений: 19
1

Построить автомат с магазинной памятью и кс-граматику, задающие язык, содержащий те и только те слова в алфавите

06.06.2020, 18:23. Показов 673. Ответов 2

Как построить автомат с магазинной памятью и кс-граматику, задающие язык, содержащий те и только те слова в алфавите {0, 1}, в которых число едениц равно числу нулей и которые содержат ровно одно вхождение подслова 100. помогите решить данную задачу, буду очень признателен.
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
06.06.2020, 18:23
Ответы с готовыми решениями:

Построить автомат с магазинной памятью
Помогите с заданием, пожалуйста Построить автомат с магазинной памятью (детерминированного типа),...

Построить автомат с магазинной памятью и кс-грамматику
Построить автомат с магазинной памятью и кс-грамматику, задающие язык, содержащий те и только те...

Построить автомат с магазинной памятью, распознающий множество
в данный момент сижу на экзамене, кто может чем помочь, помогите 1) построить автомат с...

Автомат с магазинной памятью
Построить автомат с магазинной памятью, допускающий множество: (Смотреть вложение)

2
Эксперт по математике/физике
4046 / 2916 / 941
Регистрация: 01.09.2014
Сообщений: 8,129
06.06.2020, 21:52 2
Без ограничения на подслово 100 можно взять такие грамматики:

S -> 1S0 | 0S1 | SS | пустое слово

или

S -> 1S0S | 0S1S | пустое слово

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

Может быть, есть более легкий способ, но пока он не приходит в голову.

См. также это сообщение.
0
2 / 2 / 0
Регистрация: 21.02.2019
Сообщений: 19
08.06.2020, 14:19  [ТС] 3
Большое спасибо, за наведение на правильную мысль)
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
08.06.2020, 14:19
Помогаю со студенческими работами здесь

Реализовать автомат с магазинной памятью
Для приведенной грамматики нужно реализовать автомат. Может ли кто-нибудь подсказать, где ошибка в...

Конечный автомат с магазинной памятью
Все привет. Как можно смоделировать работу конечного автомата с магазинной памятью в Haskell?

Построить автомат, распознающий все слова в алфавите (a,b,c) кроме слов bc, bac
Помогите решить задание: построить автомат распознающий все слова в алфавите (a,b,c) кроме слов bc,...

Построить конечный автомат, распознающий цепочки в алфавите
Понятия не имею, как решать, нужно как можно скорее Построить конечный автомат, распознающий...

Построить Конечный детерминированный автомат, распознающий непустые цепочки символов в алфавите
Построить Конечный детерминированный автомат, распознающий непустые цепочки символов в алфавите...

Построить автомат, не содержащий 0110
Помогите построить бесконечный автомат, не содержащий в себе 0110. Заранее спасибо!


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru