Объясните, пожалуйста, как сделать задание.

Пусть для слов в алфавите $%А=\{a,b,c\}$% заданы следующие подстановки: $$\ a) b \rightarrow a; \: b) c \rightarrow b; \\ c) ab \rightarrow bc; \; d) bc\rightarrow ca; \\ f) ca \rightarrow ab; \; g) abc\rightarrow \Lambda ; \\ h) bca\rightarrow \Lambda ; \; j) cab\rightarrow \Lambda ; \\ k) abca\rightarrow a; \; l) bcab\rightarrow \Lambda ; \\ m)a\rightarrow b.
$$

Примените каждую из них к предложенному слову максимально возможное число раз. $$\ abccbaabccba $$

задан 10 Июн '13 21:48

изменен 11 Июн '13 18:46

Deleted's gravatar image


126

10|600 символов нужно символов осталось
0

Я посмотрел все пункты -- ни в одном из них не возникает чего-то сложного (что в принципе может быть для других примеров этого типа).

Вот возьмём последний пункт. Ясно, что вхождений буквы $%a$% имеется четыре; при заменах $%a$% на $%b$% не возникает новых букв $%a$%, то есть каждую из букв $%a$% надо взять и заменить на $%b$% -- в любом порядке. То есть подстановку можно применить 4 раза, и это число максимально.

В пункте f) подстановку можно применить $%0$% раз, так как подслово $%ca$% в анализируемом слове отсутствует, и заменять нечего.

Какого-то внимания заслуживает разве что пункт c). Там первое вхождение подслова $%ab$% можно заменить на $%bc$%, и это будет один раз. Далее, в середине слова имеется вхождение $%aab$%, и там последовательно можно применить две подстановки: $%aab \to abc \to bcc$%. Всего получается три применения. Ясно, что больше сделать нельзя, так как букв $%a$% всего три, если не считать последней, которая в преобразованиях участвовать не может, и при каждой подстановке одна буква $%a$% исчезает.

В пункте g) два раза вычёркивается подслово $%abc$% (через $%\Lambda$% обозначено пустое слово), и далее уже ничего не преобразовать.

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

ссылка

отвечен 10 Июн '13 22:10

Ну как можно задавать более хитрые примеры студенту-заочнику, который не знает решения даже такой простой задачи? Если бы мы галопом по Европе не проходили в две-три пары логику, можно было бы и более хитрые задачи решать.

(10 Июн '13 22:21) AQZ
1

Я не говорил, что такие задачи нужно давать! Я говорил только о том, что можно. Это было сказано чисто для информации -- чтобы не создалось ощущения, что все задачи из этой области решаются примитивно.

(10 Июн '13 22:29) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×422
×120

задан
10 Июн '13 21:48

показан
503 раза

обновлен
10 Июн '13 22:29

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru