ऑटोमेटा सिद्धांत

यह ऐसी मशीन की कल्पना को जीवंत करती है जो एक समय में एक खास स्थान-पोज़ीशन में ही रहती है। किसी इनपुट के आने इसकी पोजीशन बदलती है। किसी और इनपुट के आने के बाद इनकी पोज़ीशन फ़िर बदलती है। इस प्रकार कई इनपुट के आने पर ये वापिस अपनी शुरुआती स्थिति में पहुँच सकती है।

इसका इस्तेमाल पैटर्न मैचिंग में इस प्रकार होता है कि पैटर्न को देखकर एक ऑटोमेटा मशीन की कल्पना (सृजन) की जाती है। जिस text में इसका मिलान करना हो उसके एक-एक अक्षर को देखते हुए match हुई स्थितियों को गिना जाता है। अगर pattern के सभी अक्षरों के बराबर अक्षर मिल गए हों तो मिलान पूरा समझा जाता है।