Deterministički konačni automat: razlika između inačica

 

U drugu ruku, DKAi su strogo ograničene moći nad jezicima koje mogu prepoznati — mnogi jednostavni jezici, uključujući bilo koji problem čije rješenje zahtijeva više nego konstantan prostor, ne mogu biti prepoznati od strane DKA. Kanonski primjer jezika kojeg nijedan DKA ne može prepoznati jest jezik koji se sastoji od nizova znakova oblika ''aⁿbⁿ'' — konačan broj znakova a nakon kojeg slijedi jednaki broj znakova b. Može se pokazati da nijedan DKA ne može imati dovoljan broj stanja da prepozna takav jezik.

 

{{Formalni jezici i gramatike}}