109 urn:lsid:arphahub.com:pub:3dc5f44e-8666-58db-bc76-a455210e8891 JUCS - Journal of Universal Computer Science jucs 0948-695X 0948-6968 Journal of Universal Computer Science 10.3217/jucs-017-06-0874 29941 Research Article F.1.1 - Models of Computation F.1.2 - Modes of Computation Descriptional Complexity of Ambiguity in Symmetric Difference NFAs van Zijl Lynette lvzijl@sun.ac.za https://orcid.org/0000-0001-5735-0448 1 Geldenhuys Jaco Stellenbosch University, Stellenbosch, South Africa Stellenbosch University Stellenbosch South Africa , ,

Corresponding author: Lynette van Zijl (lvzijl@sun.ac.za).

Academic editor:

2011 28 03 2011 17 6 874 890 B199394E-8AB0-58D2-9028-CD7691EA0BED 7001633 Lynette van Zijl, Jaco Geldenhuys This article is freely available under the J.UCS Open Content License.

We investigate ambiguity for symmetric difference nondeterministic finite automata. We show the existence of unambiguous, finitely ambiguous, polynomially ambiguous and exponentially ambiguous symmetric difference nondeterministic finite automata. We show that, for each of these classes, there is a family of n-state nondeterministic finite automata such that the smallest equivalent deterministic finite automata have O(2n) states.