Let A be deterministic finite automata (DFA) with alphabet I (finite set of the input symbols). We say, that A is character universal iff exists word w ES* accepted by automata A such that, every character of the alphabet Soccures in w at least once. Formally written: Va D: #a(w) > 1). Prove that: UNIV-CHAR= {(A) A is character universal DFA } is NP-complete. Hint: Reduce from 3SAT. Show how to create such automata, that this equivalence will be true: formule has satisfiable assignment iff in automata exists accepting run so that each character occures in word at least once and. Let A be deterministic finite automata (DFA) with alphabet I (finite set of the input symbols). We say, that A is character universal iff exists word w ES* accepted by automata A such that, every character of the alphabet Soccures in w at least once. Formally written: Va D: #a(w) > 1). Prove that: UNIV-CHAR= {(A) A is character universal DFA } is NP-complete. Hint: Reduce from 3SAT. Show how to create such automata, that this equivalence will be true: formule has satisfiable assignment iff in automata exists accepting run so that each character occures in word at least once and