A partial function $F:\Sigma^{\ast}\rightarrow\Omega^{\ast}$ is
called a {\em simple} function if $F(w)\in \Omega^*$ is the output
produced in the generation of a word $w\in \Sigma^*$ from a
nonterminal of a simple context free grammar $G$ with output
alphabet $\Omega$. In this paper we present an efficient algorithm
for testing equivalence of simple functions. Such functions
correspond also to one-state deterministic pushdown transducers. Our
algorithm works in time polynomial with respect to $|G|+ v(G)$,
where $|G|$ is the size of the textual description of $G$, and
$v(G)$ is the maximum of the shortest lengths of words generated by
nonterminals of $G$.
Key Words: Sequential transducer, Simple language, Simple function, Deterministic Push-Down Transducer, Context-Free Grammar
