I am looking for the right transducer which allows to translate a sequence of literals into a sequence of same literals (or a subset of them) in arbitrary order. For example: ABC => CAB, which, with simple production rules: A->a, B->b, C->c, results into output: cab.

I am not sure if the pushdown automata is enough to resolve such problem.

Note: My question corresponds to understand which automaton model lies under the implementation of the widely used regex replacement strategy in common libraries such as: back reference in java(link) or replacement part in sed of bash (link).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.