NAMs

def main():
    # Входной алфавит
    A = ('0', '1', '2', '3', '4', '5', '6', '7', '8', '9')
    # Список левых частей правил
    to_replace = ('*0', '*1', '*2', '*3', '*4', '*5', '*6', '*7', '*8', '*9',
                  '9!', '8!', '7!', '6!', '5!', '4!', '3!', '2!', '1!', '0!',
                  '9#', '8#', '7#', '6#', '5#', '4#', '3#', '2#', '1#', '0#',
                  '!3', '!4', '!5', '!6', '!7', '!8', '!9',
                  '_?0.', '?', '*', '#', '_.', '')
    # Список правых частей правил
    replacement = ('0*','1*','2*', '3*', '4*', '5*', '6*', '7*', '8*', '9*',
                   '8', '7', '6', '5', '4', '3', '2', '1', '?0', '!9',
                   '2','1','0','!9','!8','!7', '!6', '!5', '!4', '!3',
                   '', '', '', '', '', '', '',
                   '', '', '#', '', '', '_*')
    # Кол-во правил
    n = len(to_replace)
    # Символ для определения конечных замен
    end_symbol = '.'
    print("A =", A)
    print("Введите слово содержащее символы алфавита:")
    word = input()
    if (not set(word) - set(A)) == False:
        return
    if len(word) == 0:
        word = ' '
    is_end = False
    #print("Rules")
    #for i in range(n):
    #    print(to_replace[i], '->',replacement[i])
    print('Alg')
    while is_end == False:
        prev_word = word[::]
        for i in range(n):
            left_p = to_replace[i]
            right_p = replacement[i]
            if left_p.find(end_symbol) != -1:
                left_p = left_p.replace(end_symbol, '', 1)
                word = word.replace(left_p, right_p, 1)
                if word == prev_word:
                    continue
                is_end = True
                break
            word = word.replace(left_p, right_p, 1)
            if word != prev_word:
                break
        print("->", word)

if __name__ == '__main__':
    main()