|
Объясните, пожалуйста, как сделать задание. Пусть для слов в алфавите $%А=\{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 
AQZ |
|
Я посмотрел все пункты -- ни в одном из них не возникает чего-то сложного (что в принципе может быть для других примеров этого типа). Вот возьмём последний пункт. Ясно, что вхождений буквы $%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 
falcao Ну как можно задавать более хитрые примеры студенту-заочнику, который не знает решения даже такой простой задачи? Если бы мы галопом по Европе не проходили в две-три пары логику, можно было бы и более хитрые задачи решать.
(10 Июн '13 22:21)
AQZ
1
Я не говорил, что такие задачи нужно давать! Я говорил только о том, что можно. Это было сказано чисто для информации -- чтобы не создалось ощущения, что все задачи из этой области решаются примитивно.
(10 Июн '13 22:29)
falcao
|