Алгорифм готов.
![$\\
\mbox{Шаг 2. Замена на близнецовый алфавит} \\
\ast| \to \ast L \\
L| \to LL \\
\\
\mbox{Шаг 3. Перевод из унарной системы обратно в восьмеричную, финал} \\
\ast L^8 \to L \ast \\
L+ \to +L \\
\\
L\ast L^7 \to +L 7 \\
L\ast L^6 \to +L 6 \\
L\ast L^5 \to +L 5 \\
L\ast L^4 \to +L 4 \\
L\ast L^3 \to +L 3 \\
L\ast L^2 \to +L 2 \\
L\ast L\phantom{^1} \to +L 1 \\
L\ast \phantom{L^0} \to +L 0 \\
\\
\ast L^7 \mapsto 7 \\
\ast L^6 \mapsto 6 \\
\ast L^5 \mapsto 5 \\
\ast L^4 \mapsto 4 \\
\ast L^3 \mapsto 3 \\
\ast L^2 \mapsto 2 \\
\ast L\phantom{^1} \mapsto 1 \\
\ast \phantom{L^0} \mapsto 0 \\
\\
+ \to \ast \\
\\
\mbox{Шаг 1. Перевод числа } x \mbox{ в восьмеричной системе в число } y = 7x+2 \mbox{ в унарной системе} \\
|0 \to 0|^8 \\
1 \to 0|^{1 \cdot 7} \\
2 \to 0|^{2 \cdot 7} \\
3 \to 0|^{3 \cdot 7} \\
4 \to 0|^{4 \cdot 7} \\
5 \to 0|^{5 \cdot 7} \\
6 \to 0|^{6 \cdot 7} \\
7 \to 0|^{7 \cdot 7} \\
0 \to \\
\# \to \ast|| \\
\phantom{\#} \rightarrow \#
$ $\\
\mbox{Шаг 2. Замена на близнецовый алфавит} \\
\ast| \to \ast L \\
L| \to LL \\
\\
\mbox{Шаг 3. Перевод из унарной системы обратно в восьмеричную, финал} \\
\ast L^8 \to L \ast \\
L+ \to +L \\
\\
L\ast L^7 \to +L 7 \\
L\ast L^6 \to +L 6 \\
L\ast L^5 \to +L 5 \\
L\ast L^4 \to +L 4 \\
L\ast L^3 \to +L 3 \\
L\ast L^2 \to +L 2 \\
L\ast L\phantom{^1} \to +L 1 \\
L\ast \phantom{L^0} \to +L 0 \\
\\
\ast L^7 \mapsto 7 \\
\ast L^6 \mapsto 6 \\
\ast L^5 \mapsto 5 \\
\ast L^4 \mapsto 4 \\
\ast L^3 \mapsto 3 \\
\ast L^2 \mapsto 2 \\
\ast L\phantom{^1} \mapsto 1 \\
\ast \phantom{L^0} \mapsto 0 \\
\\
+ \to \ast \\
\\
\mbox{Шаг 1. Перевод числа } x \mbox{ в восьмеричной системе в число } y = 7x+2 \mbox{ в унарной системе} \\
|0 \to 0|^8 \\
1 \to 0|^{1 \cdot 7} \\
2 \to 0|^{2 \cdot 7} \\
3 \to 0|^{3 \cdot 7} \\
4 \to 0|^{4 \cdot 7} \\
5 \to 0|^{5 \cdot 7} \\
6 \to 0|^{6 \cdot 7} \\
7 \to 0|^{7 \cdot 7} \\
0 \to \\
\# \to \ast|| \\
\phantom{\#} \rightarrow \#
$](https://dxdy-01.korotkov.co.uk/f/0/a/3/0a3c0dfc34061e1c9bf56a70aeb7062982.png)
Нашёл в литературе алгоритм композиции НАМов, делал по нему. Однако ввиду специфики задачи и ещё того, что выходной алфавит первого шага состоит из одного символа
![$\{|\}$ $\{|\}$](https://dxdy-04.korotkov.co.uk/f/b/e/b/beb2a95331e9dece0695a834d0600c6c82.png)
, удалось избавиться от тонны вспомогательных правил. В том числе от целой группы правил перевода строки из близнецового алфавита обратно в родной, количество которых равно трижды квадрату мощности расширенного алфавита:
![$3 \cdot |V \cup V'|^2$ $3 \cdot |V \cup V'|^2$](https://dxdy-04.korotkov.co.uk/f/3/f/5/3f5ecf498f70ae1682ef9d230ac8f0b382.png)
, т. е. 300 штук для моего случая :).
Проблема, однако, возникла с тем, что финальный алгоритм перевода обратно в восьмеричную систему многократно использует правило с ПЛЧ, поэтому вашим,
arseniiv, методом воспользоваться не удалось. На этот раз проблему решил уже сам, введя новый маркер
![$+$ $+$](https://dxdy-02.korotkov.co.uk/f/d/f/3/df33724455416439909c33a7db76b2bc82.png)
, который я вставляю вместо
![$\ast$ $\ast$](https://dxdy-01.korotkov.co.uk/f/4/5/7/457fa9db3eb0739310d5ed0f01f8d65d82.png)
, когда тот уничтожается на НЕтерминальных правилах, а потом гоню плюс обратно в начало строки, где он сбрасывает личину и перевоплощается обратно в
![$\ast$ $\ast$](https://dxdy-01.korotkov.co.uk/f/4/5/7/457fa9db3eb0739310d5ed0f01f8d65d82.png)
. Кажется, я понемногу научиваюсь думать нормальными алгорифмами )
arseniiv, задача решена, огромное спасибо за помощь!!
![Very Happy :D](./images/smilies/icon_biggrin.gif)