We have introduced the concept of nondeterministic fuzzy finite automata under max-* compositional inference for some t-norm *. In order to compare the behaviors of nondeterministic fuzzy finite automata, two ε-language approximations are given using some real number ε in [0, 1]. Then we discuss the relationship of two ε-language approximations, and prove that nondeterministic fuzzy finite automata and fuzzy finite automata are 0-language approximated, that is to say they can accept same fuzzy language. In addition, some algebraic properties of two ε-language approximations are studied. In particular, we obtain that properties of them under union operation, *operation, and concatenation operation. Finally, the robustness of ε-language approximations is analyzed.