क-Testable भाषाओं की सख्त परिभाषा का अनुमान और वाक्यात्मक पैटर्न पहचान में अनुप्रयोग

क-Testable भाषाओं की सख्त परिभाषा (k-TSSL) के वर्ग का आवधिक अनुमान पर विचार किया गया है। एक k-TSSL को मूल रूप से एक सीमित सेट के रूप में परिभाषित किया गया है जिसमें लंबाई k के उपस्ट्रिंग होते हैं जो भाषा की स्ट्रिंग में दिखाई देने की अनुमति है। अज्ञात भाषा की स्ट्रिंग्स का एक सकारात्मक नमूना R दिया गया है, जिससे R को शामिल करने वाले सबसे छोटे k-TSSL को पहचानने वाला एक निर्धारणात्मक सीमित-राज्य ऑटोमेशन प्राप्त होता है। प्राप्त ऑटोमेशन के लिए उपसर्गों की संख्या O(m) द्वारा सीमित होने का प्रमाण दिया गया है जहाँ m इस k-TSSL को परिभाषित करने वाले उपस्ट्रिंग्स की संख्या है, और अनुमान लगाना एल्गोरिदम O(kn log m) में कार्य करता है जहाँ n R में सभी स्ट्रिंग्स की लंबाई का योग है। प्रस्तावित विधियों को वाक्यात्मक पैटर्न पहचान प्रयोगों के माध्यम से दर्शाया गया है जिसमें दस दिए गए (स्रोत) non-k-TSSL व्याकरणों द्वारा उत्पन्न कई स्ट्रिंग्स का उपयोग करके दस k-TSSL स्टोकास्टिक ऑटोमेटा का अनुमान लगाया गया है, जो बाद में उसी स्रोत व्याकरणों द्वारा उत्पन्न नई स्ट्रिंग्स को वर्गीकृत करने के लिए उपयोग किया गया है। इन प्रयोगों के परिणाम सिद्धांत के अनुरूप हैं और (स्टोकास्टिक) k-TSSLs के अन्य नियमित भाषाओं के वर्गों के करीब आने की क्षमता को प्रदर्शित करते हैं।