For larger alphabets, that problem is PSPACE-complete.
Για μεγαλύτερα αλφάβητα, το πρόβλημα γίνεται PSPACE-complete.