якщо існує нескінченний автомат, що розпізнає цю мову

якщо існує скінченний автомат, в якого всі стани заключні

якщо існує скінченний автомат, що розпізнає цю мову

якщо не існує формальна граматика, що має таку ж мову