Reescrita de Expressões Regulares

Deve ser projetado um aplicativo que leia uma lista de regras de reescrita e, a partir de uma cadeia inicial dada, faça a simulação da aplicação dessas regras. A lista de regras é inerentemente não determinística, não havendo uma ordem específica para aplicação das regras. Assim, o programa deve gerar todas as possibilidades de cadeia final. O programa deve ter uma opção para mostrar passo a passo a execução das regras. Caberá ao grupo definir a linguagem precisa para explicitar as regras.