Составить автоматную грамматику, порождающую язык, в словах которого не повторяются буквы

[Tamada]

Здравствуйте! Нужно составить грамматику, которая порождает цепочки цифр, в которых ни одна цифра не повторяется. Цепочки могут быть любой длины, то есть от 1 до 10.
У меня есть грамматика для трёх цифр, но для всех 10 я никак не могу составить грамматику:
S->1A|2B|3C
A->2D|3E|εD|εE
B->1D|3G|εD|εG
C->1E|2G|εE|εG
D->3|ε
E->2|ε
G->1|ε

Пример:
Подходит:
1234567890 1235678 09841 154 и тд
Не подходит:
1231 09877 11544 и тд

[BDA]

Не уверен на 100%, но если сделать аналогичную грамматику для 10 цифр, то получится 1023 правила (во вложении из-за размера). Код для генерации грамматики получился чуток громоздким, но лень упрощать:

from itertools import count

def new_nonterminal():
    for i in count(1):
        for j in range(ord('A'), ord('Z') + 1):
            yield chr(j) + "'" * i

new_n = new_nonterminal()
t2n_cache = {}
n2t_cache = {}

def t2n(ts):
    if ts in t2n_cache:
        return t2n_cache[ts]
    else:
       n = next(new_n)
       t2n_cache[ts] = n
       n2t_cache[n] = ts
       return n

def n2t(n):
    if n in n2t_cache:
        return n2t_cache[n]
    else:
        raise RuntimeError("Unknown n")

ts = tuple(str(i) for i in range(10))

t2n_cache[ts] = "S"
n2t_cache["S"] = ts
ns = ["S"]
eps = False
printed_n = set()

while ns:
    n = ns.pop(0)
    if n in printed_n:
        continue
    printed_n.add(n)
    ts = n2t(n)
    if len(ts) > 1:
        new_ns = []
        for i, t in enumerate(ts):
            new_ts = tuple(ts[:i] + ts[i + 1:])
            new_ns.append(t2n(new_ts))
        if eps:
            print("%s -> %s|%s" % (n, "|".join(v[0] + v[1] for v in zip(ts, new_ns)), "|".join("e" + v for v in new_ns)))
        else:
            print("%s -> %s" % (n, "|".join(v[0] + v[1] for v in zip(ts, new_ns))))
            eps = True
        ns.extend(new_ns)
    else:
        print("%s -> %s|e" % (n, ts[0]))

Для 4 цифр выглядит правдоподобно:

S -> 0A'|1B'|2C'|3D'
A' -> 1E'|2F'|3G'|eE'|eF'|eG'
B' -> 0E'|2H'|3I'|eE'|eH'|eI'
C' -> 0F'|1H'|3J'|eF'|eH'|eJ'
D' -> 0G'|1I'|2J'|eG'|eI'|eJ'
E' -> 2K'|3L'|eK'|eL'
F' -> 1K'|3M'|eK'|eM'
G' -> 1L'|2M'|eL'|eM'
H' -> 0K'|3N'|eK'|eN'
I' -> 0L'|2N'|eL'|eN'
J' -> 0M'|1N'|eM'|eN'
K' -> 3|e
L' -> 2|e
M' -> 1|e
N' -> 0|e

[Tamada]

BDA,
У нас задание - составить грамматику и написать что-то типа такой функции:

/*
Состояния автомата
*/
enum AState { S, A, E, F };
/*
Контейнер лексемы
*/
struct Lex {
bool valid; // флаг корректности лексемы (соответствия заданию)
char* str; // текст лексемы
};
/*
Функция лексического анализа
*/
vector<Lex> LexAnalysis(char* str)
{
vector<Lex> result;
int position = 0; // текущая позиция в строке
AState state = AState::S; // текущее состояние
Lex lexema; // текущая лексема
int firstPos; // позиция начала лексемы
while (str[position] != '\0')
{
char currentChar = str[position];
// Инициализация лексемы при обнаружении непробельного символа
if (state == AState::S && currentChar != ' ')
{
firstPos = position;
lexema.valid = true;
}
// Переход по матрице состояний
switch (currentChar) {
case '0':
if (state == AState::S) state = AState::A;
if (state == AState::A) state = AState::A;
if (state == AState::E) state = AState::E;
break;
case '1':
if (state == AState::S) state = AState::A;
if (state == AState::A) state = AState::A;
if (state == AState::E) state = AState::E;
break;

case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
if (state == AState::S) state = AState::E;
if (state == AState::A) state = AState::E;
if (state == AState::E) state = AState::E;
break;
case ' ':
if (state == AState::S) state = AState::F;
if (state == AState::A) state = AState::F;
if (state == AState::E) state = AState::F;
break;

}
// Определение соответствия лексемы заданию
if (state == AState::E)
lexema.valid = false;
// Запись текущей лексемы в выходной список и инициализация новой лексемы
if (state == AState::F)
{
int length = position - firstPos;
lexema.str = new char[length + 1];
// Вычленение подстроки и запись в лексему
strncpy(&lexema.str[0], &str[0] + firstPos, length);
// Постановка финализирующего 0
lexema.str[length] = '\0';
// Запись лексемы в список
result.push_back(lexema);
state = AState::S;
}
position++;
}
return result;
}

Но!Можно сделать через буферные переменные, дабы запоминать то, что было до текущего символа. Если все эти цифры взять за одно состояние, то это же упростит жизнь?