Graduate student Kayleigh Hyde will present her Master’s project on Monday April 22, 10:30am, in Shidler College of Business Room E201.

Let $M$ be a nondeterministic finite automaton, having $q$ states and no $\epsilon$-transitions. If there is exactly one path through $M$ of length $n$ leading to an accept state, and $x$ is the string read along that path, then we say that $A_N(x)\le q$ (the NFS complexity of $x$ is at most $q$).

S0111V0 S0111V1 0 1 S0101V0 S0101V1 0 1 S0001V0 0 S0001V1 1 S0000V0 0