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

@Andrey001 · Регистрация: 03.01.2021

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

Всем привет, есть такая задача:
Построить ДКА (Детерминированный конечный автомат), допускающий в алфавите {0, 1} все строки, в которых модуль разницы количества символов 0 и символов 1 нацело не делится на 5.

Делал в JFLAP-e ну никак не получается, я не могу хранить числа, так как это дка, а он как известно может находиться только в одном состоянии, и я не смогу реализовать операцию суммы, разности, модуль и тд.
Мне кажется это невозможно сделать, но и на этот случай сказано: примести доказательство невозможности.
Подскажите пожалуйста как привести доказательство невозможности построения такого ДКА.
Заранее спасибо

@Sindbad_M · 12.02.2021, 10:06

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

я не могу хранить числа, так как это дка,

Конечное множество чисел вы хранить можете.
Пусть состояние
Р₀ соответствует разности 0 и 1 равной нулю
Р₊₁ соответствует разности 0 и 1 равной одному (нолей на один больше)
Р₊₂ соответствует разности 0 и 1 равной двум (нолей на два больше)
...
Р₊₄ соответствует разности 0 и 1 равной двум (нолей на четыре больше)
Р_-1 соответствует разности 0 и 1 равной одному (нолей на один меньше чем единиц)
...
Р_-4 соответствует разности 0 и 1 равной пяти (нолей на четыре меньше чем единиц)

Начальное состояение Р₀, получив очередной символ переходим либо в Р₊₁, либо Р_-1 и т.д.
Если находимся в состоянии Р₊₄ и следующий символ "0", то перейти в состояние Р₀, т.е. каждую полную накопленную пятерку нолей откидываем.
Аналогично, если находимся в состоянии Р_-4 и следующий символ "1", то перейти в состояние Р₀

@3D Homer · 13.02.2021, 00:02

Думаю, можно обойтись состояниями P₀, ..., P₄. Если автомат находится в состоянии P₀ и читается 1, то автомат переходит в состояние P₄.

@Andrey001 1 / 1 / 1 Регистрация: 03.01.2021 Сообщений: 20
		1
	Построить детерминированный конечный автомат 12.02.2021, 05:35. Показов 2075. Ответов 2 Метки конечные автоматы, теория автоматов (Все метки) Всем привет, есть такая задача: Построить ДКА (Детерминированный конечный автомат), допускающий в алфавите {0, 1} все строки, в которых модуль разницы количества символов 0 и символов 1 нацело не делится на 5. Делал в JFLAP-e ну никак не получается, я не могу хранить числа, так как это дка, а он как известно может находиться только в одном состоянии, и я не смогу реализовать операцию суммы, разности, модуль и тд. Мне кажется это невозможно сделать, но и на этот случай сказано: примести доказательство невозможности. Подскажите пожалуйста как привести доказательство невозможности построения такого ДКА. Заранее спасибо 0

@Sindbad_M 456 / 385 / 117 Регистрация: 23.05.2016 Сообщений: 1,547
	12.02.2021, 10:06	2
	Сообщение от Andrey001 я не могу хранить числа, так как это дка, Конечное множество чисел вы хранить можете. Пусть состояние Р₀ соответствует разности 0 и 1 равной нулю Р₊₁ соответствует разности 0 и 1 равной одному (нолей на один больше) Р₊₂ соответствует разности 0 и 1 равной двум (нолей на два больше) ... Р₊₄ соответствует разности 0 и 1 равной двум (нолей на четыре больше) Р_-1 соответствует разности 0 и 1 равной одному (нолей на один меньше чем единиц) ... Р_-4 соответствует разности 0 и 1 равной пяти (нолей на четыре меньше чем единиц) Начальное состояение Р₀, получив очередной символ переходим либо в Р₊₁, либо Р_-1 и т.д. Если находимся в состоянии Р₊₄ и следующий символ "0", то перейти в состояние Р₀, т.е. каждую полную накопленную пятерку нолей откидываем. Аналогично, если находимся в состоянии Р_-4 и следующий символ "1", то перейти в состояние Р₀ 1

@3D Homer $Эксперт по математике/физике$ 4945 / 3564 / 1149 Регистрация: 01.09.2014 Сообщений: 9,647
	13.02.2021, 00:02	3
	Сообщение было отмечено Andrey001 как решение Решение Думаю, можно обойтись состояниями P₀, ..., P₄. Если автомат находится в состоянии P₀ и читается 1, то автомат переходит в состояние P₄. 1

Опции темы

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

Решение