Kan die 0^n1^n (gebalanseerde hakies) probleem in lineêre tyd O(n) met 'n multibandtoestandmasjien besluit word?
Woensdag 18 Oktober 2023
by Ihor Halanyuk
Die probleem 0^n1^n, ook bekend as die gebalanseerde hakies probleem, verwys na die taak om te bepaal of 'n gegewe string bestaan uit 'n gelyke aantal 0'e gevolg deur 'n gelyke aantal 1'e. In die konteks van berekeningskompleksiteitsteorie is die vraag of hierdie probleem in lineêre tyd O(n) besluit kan word deur gebruik te maak van