दो परिमित अवस्था मशीनों को समतुल्य कहा जाता है यदि:

संकल्पना:

परिमित अवस्था स्वचलप्ररूप एक मशीन है जिसका उपयोग कंप्यूटर क्रमादेश और अन्य अनुक्रमिक तर्कों को हल करने के लिए किया जा सकता है और एक निश्चित समय में अवस्थाओं की सीमित संख्या होती है। एक परिमित अवस्था मशीन में 6 टपल होते हैं।

व्याख्या:

दो परिमित अवस्था मशीनों को समतुल्य कहा जाता है यदि वे टोकन के एक ही समुच्चय को पहचानते हैं।

दो स्वचलप्ररूप M1 और M2 पर विचार कीजिए, इन्हें एक निवेश अनुक्रम के लिए समतुल्य कहा जाता है यदि वे समान निर्गम परिणाम उत्पन्न करते हैं।

उदहारण:

नियमित व्यंजक: baa*b

NFA: M1

NFA में अवस्थाओं की संख्या: 4

DFA: M2

DFA में अवस्थाओं की संख्या: 5

दो परिमित स्वचलप्ररूपों के ऊपर विभिन्न अवस्थाओं और किनारों की संख्या होती है, लेकिन वे समकक्ष होते हैं।

उन्हें समकक्ष तभी कहा जाता है जब वे एक ही नियमित भाषा (टोकन का एक ही समुच्चय) स्वीकार करते हैं, चाहे उनके पास अलग-अलग अवस्थाओं या किनारों की संख्या हो।