В какое состояние перейдет автомат?

@Вероника99 · Регистрация: 16.12.2013

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

Добрый день. Прошу помочь с решением следующей задачи: Задан У-детерминованный конечный автомат с пятью состояниями {Zi}={z0,z1,z2,z3,z4} (На изображении). В какое состояние перейдет автомат в четвертом такте, если начальное состояние z0 и последовательность вероятностей, за которыми происходят переходы в состояния на соответствующих тактах, такие: 0.65, 0.29, 0.85, 0.55
Варианты ответов: а) z0 b)z1 c)z2 d)z3 e)z4 Была бы очень благодарна за объяснение

@AdmiralHood · 18.07.2016, 09:52

Могу предположить, что делается это как-то так.

1) Первоначальное состояние - z0. Из этого состояния автомат с вероятностью 0,5 переходит в состояние z1 и с вероятностью 0,5 — в состояние z2. То есть если число, которое в условии имитирует вероятность, находится в пределах [0...0,5], то идёт переход в состояние z1, а если в пределах (0,5...1] — в состояние z2. Так как число равно 0,65, то идёт переход z0 -> z2.

2) Аналогично, по 0,29 из состояния z2 идёт переход z2 ->z1.

3) По 0,85 из состояния z1 идёт переход z1 ->z4.

4) По 0,55 из состояния z4 идёт переход z4 ->z3.

Ответ: z3

@Вероника99 · 18.07.2016, 14:36 **[ТС]**

Спасибо за ответ.
Не поняла один момент.Вы писали

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

То есть если число, которое в условии имитирует вероятность, находится в пределах [0...0,5], то идёт переход в состояние z1, а если в пределах (0,5...1] — в состояние z2.

По какому принципу здесь идет выбор между z3 и z4? Вы по матрице смотрите?

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

3) По 0,85 из состояния z1 идёт переход z1 ->z4.
4) По 0,55 из состояния z4 идёт переход z4 ->z3.

Ответь пожалуйста,очень надо

@3D Homer · 19.07.2016, 18:20

Предположительно правило перехода следующее. Пусть i-я строка таблицы ( $https://www.cyberforum.ru/cgi-bin/latex.cgi?0\le i\le 4$ ) есть $https://www.cyberforum.ru/cgi-bin/latex.cgi?(p_0,p_1,p_2,p_3,p_4)$ , причем $https://www.cyberforum.ru/cgi-bin/latex.cgi?p_0+p_1+p_2+p_3+p_4=1$ . Если автомат находится в состоянии $https://www.cyberforum.ru/cgi-bin/latex.cgi?z_i$ и вероятность в очередном такте есть q, то следующее состояние есть
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{cases}z_0,&q\le p_0\\z_1,&p_0<q\le p_0+p_1\\z_2,&p_0+p_1<q\le p_0+p_1+p_2\\ z_3,&p_0+p_1+p_2<q\le p_0+p_1+p_2+p_3\\z_4,&p_0+p_1+p_2+p_3<q\le 1\end{cases}$

@AdmiralHood · 20.07.2016, 11:33

Фишка вот в чём. Из состояния 0 автомат с равной вероятностью 0,5 переходит либо в состояние 1, либо в состояние 2. Когда у нас реальный, физический автомат, мы можем не знать, какие механизмы обеспечивают равную вероятность обоих переходов, автомат всё сам делает, мы только констатируем, что вероятность составляет 0,5+0,5.

Когда же мы имитируем автомат с помощью теоретической модели, мы можем, например, бросить монетку. Если орёл - переходим в состояние 1, если решка — то 2. Но это плохо, так как вероятность может отличаться от 0,5 (например, 0,3+0,7), поэтому целесообразно сгенерировать равномерно распределённое случайное число в интервале от 0 до 1 и условиться, что, например, если число меньше 0,5, то идёт переход в 1, если больше 0,5 — то в 2.

Это просто имитация случайных переходов с помощью случайного числа. Можно придумать какое-нибудь другое правило перехода, но наиболее естественное и широко распространённое правило я описал.

Из состояния z1 идёт переход в z3 или z4 с вероятностью 0,4 и 0,6 соответственно. Разбиваем интервал [0;1] на два подинтервала, длина которых равна этим вероятностям. То есть первый интервал [0;0,4], второй — (0,4;1]. В какой интервал попадёт случайное число, та вероятность и срабатывает. Число 0,85 попадает во второй интервал, значит по числу 0,85 переходим в состояние z4.

@tolkin · 29.07.2017, 15:54

как возможен переход из z4 ->z3. идем же же последовательно

@3D Homer · 29.07.2017, 23:07

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

идем же же последовательно

Что вы под этим имеете в виду?

@Вероника99 5 / 5 / 5 Регистрация: 16.12.2013 Сообщений: 463
		1
	В какое состояние перейдет автомат? 14.07.2016, 22:40. Показов 625. Ответов 6 Метки нет (Все метки) Добрый день. Прошу помочь с решением следующей задачи: Задан У-детерминованный конечный автомат с пятью состояниями {Zi}={z0,z1,z2,z3,z4} (На изображении). В какое состояние перейдет автомат в четвертом такте, если начальное состояние z0 и последовательность вероятностей, за которыми происходят переходы в состояния на соответствующих тактах, такие: 0.65, 0.29, 0.85, 0.55 Варианты ответов: а) z0 b)z1 c)z2 d)z3 e)z4 Была бы очень благодарна за объяснение Изображения 0

@AdmiralHood 476 / 279 / 90 Регистрация: 15.11.2013 Сообщений: 530
	18.07.2016, 09:52	2
	Могу предположить, что делается это как-то так. 1) Первоначальное состояние - z0. Из этого состояния автомат с вероятностью 0,5 переходит в состояние z1 и с вероятностью 0,5 — в состояние z2. То есть если число, которое в условии имитирует вероятность, находится в пределах [0...0,5], то идёт переход в состояние z1, а если в пределах (0,5...1] — в состояние z2. Так как число равно 0,65, то идёт переход z0 -> z2. 2) Аналогично, по 0,29 из состояния z2 идёт переход z2 ->z1. 3) По 0,85 из состояния z1 идёт переход z1 ->z4. 4) По 0,55 из состояния z4 идёт переход z4 ->z3. Ответ: z3 2

@Вероника99 5 / 5 / 5 Регистрация: 16.12.2013 Сообщений: 463
	18.07.2016, 14:36 [ТС]	3
	Спасибо за ответ. Не поняла один момент.Вы писали Сообщение от AdmiralHood То есть если число, которое в условии имитирует вероятность, находится в пределах [0...0,5], то идёт переход в состояние z1, а если в пределах (0,5...1] — в состояние z2. По какому принципу здесь идет выбор между z3 и z4? Вы по матрице смотрите? Сообщение от AdmiralHood 3) По 0,85 из состояния z1 идёт переход z1 ->z4. 4) По 0,55 из состояния z4 идёт переход z4 ->z3. Ответь пожалуйста,очень надо 0

@3D Homer $Эксперт по математике/физике$ 4952 / 3570 / 1151 Регистрация: 01.09.2014 Сообщений: 9,661
	19.07.2016, 18:20	4
	Предположительно правило перехода следующее. Пусть i-я строка таблицы ( $https://www.cyberforum.ru/cgi-bin/latex.cgi?0\le i\le 4$ ) есть $https://www.cyberforum.ru/cgi-bin/latex.cgi?(p_0,p_1,p_2,p_3,p_4)$ , причем $https://www.cyberforum.ru/cgi-bin/latex.cgi?p_0+p_1+p_2+p_3+p_4=1$ . Если автомат находится в состоянии $https://www.cyberforum.ru/cgi-bin/latex.cgi?z_i$ и вероятность в очередном такте есть q, то следующее состояние есть $https://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{cases}z_0,&q\le p_0\\z_1,&p_0<q\le p_0+p_1\\z_2,&p_0+p_1<q\le p_0+p_1+p_2\\ z_3,&p_0+p_1+p_2<q\le p_0+p_1+p_2+p_3\\z_4,&p_0+p_1+p_2+p_3<q\le 1\end{cases}$ 0

@AdmiralHood 476 / 279 / 90 Регистрация: 15.11.2013 Сообщений: 530
	20.07.2016, 11:33	5
	Фишка вот в чём. Из состояния 0 автомат с равной вероятностью 0,5 переходит либо в состояние 1, либо в состояние 2. Когда у нас реальный, физический автомат, мы можем не знать, какие механизмы обеспечивают равную вероятность обоих переходов, автомат всё сам делает, мы только констатируем, что вероятность составляет 0,5+0,5. Когда же мы имитируем автомат с помощью теоретической модели, мы можем, например, бросить монетку. Если орёл - переходим в состояние 1, если решка — то 2. Но это плохо, так как вероятность может отличаться от 0,5 (например, 0,3+0,7), поэтому целесообразно сгенерировать равномерно распределённое случайное число в интервале от 0 до 1 и условиться, что, например, если число меньше 0,5, то идёт переход в 1, если больше 0,5 — то в 2. Это просто имитация случайных переходов с помощью случайного числа. Можно придумать какое-нибудь другое правило перехода, но наиболее естественное и широко распространённое правило я описал. Из состояния z1 идёт переход в z3 или z4 с вероятностью 0,4 и 0,6 соответственно. Разбиваем интервал [0;1] на два подинтервала, длина которых равна этим вероятностям. То есть первый интервал [0;0,4], второй — (0,4;1]. В какой интервал попадёт случайное число, та вероятность и срабатывает. Число 0,85 попадает во второй интервал, значит по числу 0,85 переходим в состояние z4. 0

@tolkin 0 / 0 / 0 Регистрация: 11.01.2014 Сообщений: 18
	29.07.2017, 15:54	6
	как возможен переход из z4 ->z3. идем же же последовательно 0

@3D Homer $Эксперт по математике/физике$ 4952 / 3570 / 1151 Регистрация: 01.09.2014 Сообщений: 9,661
	29.07.2017, 23:07	7
	Сообщение от tolkin идем же же последовательно Что вы под этим имеете в виду? 0