آلة الحالة المحدودة غير الدورية

الآلة ذات الحالة المحدودة غير الدورية (وتسمى أيضًا الآلة الخالية من العدادات ) هي آلة ذات حالة محدودة يكون أحادي الانتقال الخاص بها غير دوري .

تكون اللغة المنتظمة خالية من النجوم إذا وفقط إذا كانت مقبولة بواسطة آلة ذات مجموعة انتقالية محدودة وغير دورية . تُعزى هذه النتيجة في نظرية الآلات الجبرية إلى مارسيل-بول شوتزنبرغر . ^{[ 1 ]} على وجه الخصوص، تكون الآلة الدنيا للغة الخالية من النجوم خالية دائمًا من العدادات (مع ذلك، قد تتعرف آلات أخرى غير دورية على اللغة الخالية من النجوم).

اللغة الخالية من العدادات هي لغة منتظمة يوجد فيها عدد صحيح n بحيث يكون لكل الكلمات x و y و z ، ولكل عدد صحيح m ≥ n، يكون xy = ^m z في L إذا وفقط إذا كان xy ^{= n} z في L. بالنسبة لهذه اللغات، عندما تحتوي سلسلة ما على عدد كافٍ من تكرارات أي سلسلة فرعية (على الأقل n تكرارًا)، فإن تغيير عدد التكرارات إلى عدد آخر لا يقل عن n لا يُغير انتماء السلسلة الفرعية إلى اللغة. (هذا صحيح تلقائيًا عندما تكون y سلسلة فارغة ، ولكنه يصبح شرطًا غير بديهي عندما تكون y غير فارغة). ويمكن صياغة نظرية شوتزنبرغر بطريقة أخرى، وهي أن اللغات الخالية من النجوم واللغات الخالية من العدادات هما الشيء نفسه.

تحقق الآلة غير الدورية حدسية تشيرني . ^{[ 2 ]}

• ماكناوتون، روبرت؛ بابيرت، سيمور (1971). الأوتوماتا الخالية من العدادات . دراسة بحثية. المجلد  65. مع ملحق بقلم ويليام هينمان. مطبعة معهد ماساتشوستس للتكنولوجيا. ISBN 0-262-13076-9. Zbl 0232.94024 . 
• سونال براتيك باتيل (2010). دراسة عن الأوتوماتا الخالية من العدادات (ملف PDF) (رسالة ماجستير). جامعة ولاية سان دييغو.— دراسة مكثفة لكتاب ماكناوتون، بابيرت (1971).
• توماس كولكومبيت (2011). “علاقات جرين واستخدامها في نظرية الأتمتة”. في ديديو، أدريان هوريا؛ إنيناجا، شونسوكي؛ مارتن فيدي، كارلوس (محرران). بروك. نظرية وتطبيقات اللغة والأتمتة (LATA) (PDF) . LNCS. المجلد.  6638. سبرينغر. ص 1 – 21. رقم ISBN  978-3-642-21253-6.— يستخدم علاقات غرين لإثبات نظرية شوتزنبرغر وغيرها من النظريات.