स्थानीय भाषा (औपचारिक भाषा)

गणित में, एक स्थानीय भाषा एक औपचारिक भाषा होती है जिसके लिए शब्द के पहले और अंतिम प्रतीक और प्रत्येक दो-प्रतीक सबस्ट्रिंग को देखकर भाषा में एक शब्द की सदस्यता निर्धारित की जा सकती है। समतुल्य रूप से, यह एक स्थानीय automaton द्वारा मान्यता प्राप्त भाषा है, एक विशेष प्रकार का नियतात्मक परिमित automaton ।

औपचारिक रूप से, एक अक्षर A पर एक भाषा L को स्थानीय के रूप में परिभाषित किया जाता है यदि A के उपसमुच्चय R और S हैं और A × A का एक उपसमुच्चय F ऐसा है कि एक शब्द w L में है यदि और केवल अगर w का पहला अक्षर है आर, डब्ल्यू का अंतिम अक्षर एस में है और डब्ल्यू में लंबाई 2 का कोई कारक एफ में नहीं है। यह नियमित अभिव्यक्ति के अनुरूप है

$(RA^{*}\cap A^{*}S)\setminus A^{*}FA^{*}\ .$

अधिक आम तौर पर, एक k- परीक्षण योग्य भाषा L वह है जिसके लिए L में शब्द w की सदस्यता केवल उपसर्ग, प्रत्यय पर निर्भर करती है और लंबाई k के w के कारकों का सेट; एक भाषा स्थानीय रूप से परीक्षण योग्य है अगर यह कुछ k के लिए k -testable है। एक स्थानीय भाषा 2-परीक्षण योग्य है।