2
$\begingroup$

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).

$\endgroup$

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.