  In this paper, we develop a privacy implementation for symbolic control
systems. Such systems generate sequences of non-numerical data, and these
sequences can be represented by words or strings over a finite alphabet. This
work uses the framework of differential privacy, which is a statistical notion
of privacy that makes it unlikely that privatized data will reveal anything
meaningful about underlying sensitive data. To bring differential privacy to
symbolic control systems, we develop an exponential mechanism that approximates
a sensitive word using a randomly chosen word that is likely to be near it. The
notion of "near" is given by the Levenshtein distance, which counts the number
of operations required to change one string into another. We then develop a
Levenshtein automaton implementation of our exponential mechanism that
efficiently generates privatized output words. This automaton has letters as
its states, and this work develops transition probabilities among these states
that give overall output words obeying the distribution required by the
exponential mechanism. Numerical results are provided to demonstrate this
technique for both strings of English words and runs of a deterministic
transition system, demonstrating in both cases that privacy can be provided in
this setting while maintaining a reasonable degree of accuracy.
