Clearly C is contained in NL, since: If the string is not in the language, both reject along all computation paths.
בבירור C מוכל ב-NL, מאחר ש: אם המחרוזת לא בשפה, שניהם דוחים בכל מסלול חישוב.