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

@Exczeet · Регистрация: 21.02.2019

Как построить автомат с магазинной памятью и кс-граматику, задающие язык, содержащий те и только те слова в алфавите {0, 1}, в которых число едениц равно числу нулей и которые содержат ровно одно вхождение подслова 100. помогите решить данную задачу, буду очень признателен.

@3D Homer · 06.06.2020, 21:52

Без ограничения на подслово 100 можно взять такие грамматики:

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

или

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

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

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

См. также это сообщение.

@Exczeet · 08.06.2020, 14:19 **[ТС]**

Большое спасибо, за наведение на правильную мысль)

@Exczeet 2 / 2 / 0 Регистрация: 21.02.2019 Сообщений: 19
		1
	Построить автомат с магазинной памятью и кс-граматику, задающие язык, содержащий те и только те слова в алфавите 06.06.2020, 18:23. Показов 673. Ответов 2 Метки теория автоматов (Все метки) Как построить автомат с магазинной памятью и кс-граматику, задающие язык, содержащий те и только те слова в алфавите {0, 1}, в которых число едениц равно числу нулей и которые содержат ровно одно вхождение подслова 100. помогите решить данную задачу, буду очень признателен. __________________ Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь 0

@3D Homer $Эксперт по математике/физике$ 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

@Exczeet 2 / 2 / 0 Регистрация: 21.02.2019 Сообщений: 19
	08.06.2020, 14:19 [ТС]	3
	Большое спасибо, за наведение на правильную мысль) 0

Опции темы