Машина Тьюринга - заменить каждое вхождение символа

@Bonab · Регистрация: 14.10.2020

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

A={a,b}. Заменить в P каждое вхождение a на bb.

@kabenyuk · 10.02.2021, 19:28

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

вхождение

Алгоритм видится таким:
1) Двигаемся по слову слева направо в поисках символа а, если достигли конца слова, то процесс успешно завершился.
2) Встретили символ а, заменили его на b, немедленно вернулись к началу слова, приписали к нему b.
3) Идем на 1).

@Bonab · 17.02.2021, 08:24 **[ТС]**

kabenyuk, а можно скрин не особо понял

@Sindbad_M · 17.02.2021, 12:16

Bonab, вы думаете kabenyuk чтобы алгоритм из трех строчек написать эмулятор запускал?

По существу, что такое МТ понимаете? Тогда какой из трех пунктов не знаете как реализовать?

@Bonab · 17.02.2021, 13:17 **[ТС]**

Sindbad_M, в общем что-то сделал, но всё равно не правильно, надо чтобы оно заменяло "a" на "bb" , а у меня по тупому как-то "a" заменяет на "b" и всё дальше я хз как реализовать ( скажем не понял 2-ю строку)

@Sindbad_M · 17.02.2021, 14:13

Bonab, Ок. Что-то сделали.
К примеру, тривиальный случай, когда строка состоит только из символов "b", обрабатывается правильно (т.е. п.1 выполнен).

Пункт два описывает как МТ должна отработать, если встретится символ "a":

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

Встретили символ а, заменили его на b, немедленно вернулись к началу слова, приписали к нему b.

А у вас как работает? Опишите словами. Подробно.

@Bonab · 17.02.2021, 15:07 **[ТС]**

Sindbad_M, Просто если видит "a" то заменяет его на "b" вот так вот работает, но это [delete] не верно

@Sindbad_M · 17.02.2021, 16:25

Bonab,

Понял.
Вы уперлись в одну единственную входную строчку, не пытаетесь её менять и экспериментировать.
Опишите поведение МТ для строки "bbbab"

@golddmitry · 06.01.2023, 16:04

q₀, a -> q₁, b, вправо
q₀, b -> q₀, b, вправо
q₀, пусто -> конец

q₁, a -> q₂, пусто, вправо
q₁, b -> q₃, пусто, вправо
q₁, пусто -> q₀, пусто, на месте

q₂, a -> q₂, a, вправо
q₂, b -> q₃, a, вправо
q₂, пусто -> q₄, a, влево

q₃, a -> q₂, b, вправо
q₃, b -> q₃, b, вправо
q₃, пусто -> q₄, b, влево

q₄, a -> q₄, a, влево
q₄, b -> q₄, b, влево
q₄, пусто -> q₀, b, вправо

@Sindbad_M · 06.01.2023, 20:02

что-то не то. По крайней мере ситуация когда "а" самый правый символ не будет обработана корректно

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

q₁, пусто -> q₀, пусто, на месте

@golddmitry · 12.01.2023, 11:31

https://programforyou.ru/calcu... -emulator#

@tmash · 19.01.2023, 16:41

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

A={a,b}. Заменить в P каждое вхождение a на bb.

что должно получиться из строки aca?

@Sindbad_M · 19.01.2023, 17:16

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

что должно получиться из строки aca?

"А={a;b}" это входной алфавит. Строка "аса" не может быть начальной строкой.

@tmash · 19.01.2023, 17:19

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

"А={a;b}" это входной алфавит. Строка "аса" не может быть начальной строкой.

ок, что должно получиться из "aba"?
И что такое P?

@Sindbad_M · 19.01.2023, 17:26

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

И что такое P?

судя по контексту, Р - входная строка.

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

ок, что должно получиться из "aba"?

"bbbbb"

@Bonab -42 / 0 / 0 Регистрация: 14.10.2020 Сообщений: 287
		1
	Машина Тьюринга - заменить каждое вхождение символа 09.02.2021, 09:15. Показов 8293. Ответов 14 Метки нет (Все метки) A={a,b}. Заменить в P каждое вхождение a на bb. 0

@kabenyuk $Эксперт по математике/физике$ 4166 / 3038 / 914 Регистрация: 19.11.2012 Сообщений: 6,182
	10.02.2021, 19:28	2
	Сообщение от Bonab вхождение Алгоритм видится таким: 1) Двигаемся по слову слева направо в поисках символа а, если достигли конца слова, то процесс успешно завершился. 2) Встретили символ а, заменили его на b, немедленно вернулись к началу слова, приписали к нему b. 3) Идем на 1). 2

@Bonab -42 / 0 / 0 Регистрация: 14.10.2020 Сообщений: 287
	17.02.2021, 08:24 [ТС]	3
	kabenyuk, а можно скрин не особо понял 0

@Sindbad_M 457 / 386 / 118 Регистрация: 23.05.2016 Сообщений: 1,549
	17.02.2021, 12:16	4
	Bonab, вы думаете kabenyuk чтобы алгоритм из трех строчек написать эмулятор запускал? По существу, что такое МТ понимаете? Тогда какой из трех пунктов не знаете как реализовать? 0

@Bonab -42 / 0 / 0 Регистрация: 14.10.2020 Сообщений: 287
	17.02.2021, 13:17 [ТС]	5
	Sindbad_M, в общем что-то сделал, но всё равно не правильно, надо чтобы оно заменяло "a" на "bb" , а у меня по тупому как-то "a" заменяет на "b" и всё дальше я хз как реализовать ( скажем не понял 2-ю строку) Миниатюры 0

@Sindbad_M 457 / 386 / 118 Регистрация: 23.05.2016 Сообщений: 1,549
	17.02.2021, 14:13	6
	Bonab, Ок. Что-то сделали. К примеру, тривиальный случай, когда строка состоит только из символов "b", обрабатывается правильно (т.е. п.1 выполнен). Пункт два описывает как МТ должна отработать, если встретится символ "a": Сообщение от kabenyuk Встретили символ а, заменили его на b, немедленно вернулись к началу слова, приписали к нему b. А у вас как работает? Опишите словами. Подробно. 0

@Bonab -42 / 0 / 0 Регистрация: 14.10.2020 Сообщений: 287
	17.02.2021, 15:07 [ТС]	7
	Sindbad_M, Просто если видит "a" то заменяет его на "b" вот так вот работает, но это [delete] не верно 0

@Sindbad_M 457 / 386 / 118 Регистрация: 23.05.2016 Сообщений: 1,549
	17.02.2021, 16:25	8
	Bonab, Понял. Вы уперлись в одну единственную входную строчку, не пытаетесь её менять и экспериментировать. Опишите поведение МТ для строки "bbbab" 0

@golddmitry 0 / 10 / 0 Регистрация: 08.12.2018 Сообщений: 15
	06.01.2023, 16:04	9
	q₀, a -> q₁, b, вправо q₀, b -> q₀, b, вправо q₀, пусто -> конец q₁, a -> q₂, пусто, вправо q₁, b -> q₃, пусто, вправо q₁, пусто -> q₀, пусто, на месте q₂, a -> q₂, a, вправо q₂, b -> q₃, a, вправо q₂, пусто -> q₄, a, влево q₃, a -> q₂, b, вправо q₃, b -> q₃, b, вправо q₃, пусто -> q₄, b, влево q₄, a -> q₄, a, влево q₄, b -> q₄, b, влево q₄, пусто -> q₀, b, вправо 0

@Sindbad_M 457 / 386 / 118 Регистрация: 23.05.2016 Сообщений: 1,549
	06.01.2023, 20:02	10
	что-то не то. По крайней мере ситуация когда "а" самый правый символ не будет обработана корректно Сообщение от golddmitry q₁, пусто -> q₀, пусто, на месте 0

	19.01.2023, 17:26

@golddmitry 0 / 10 / 0 Регистрация: 08.12.2018 Сообщений: 15
	12.01.2023, 11:31	11
	https://programforyou.ru/calcu... -emulator# 0

@tmash 35 / 30 / 6 Регистрация: 21.08.2015 Сообщений: 121
	19.01.2023, 16:41	12
	Сообщение от Bonab A={a,b}. Заменить в P каждое вхождение a на bb. что должно получиться из строки aca? 0

@Sindbad_M 457 / 386 / 118 Регистрация: 23.05.2016 Сообщений: 1,549
	19.01.2023, 17:16	13
	Сообщение от tmash что должно получиться из строки aca? "А={a;b}" это входной алфавит. Строка "аса" не может быть начальной строкой. 0

@tmash 35 / 30 / 6 Регистрация: 21.08.2015 Сообщений: 121
	19.01.2023, 17:19	14
	Сообщение от Sindbad_M "А={a;b}" это входной алфавит. Строка "аса" не может быть начальной строкой. ок, что должно получиться из "aba"? И что такое P? 0

@Sindbad_M 457 / 386 / 118 Регистрация: 23.05.2016 Сообщений: 1,549
	19.01.2023, 17:26	15
	Сообщение от tmash И что такое P? судя по контексту, Р - входная строка. Сообщение от tmash ок, что должно получиться из "aba"? "bbbbb" 0