ऑटोमेटा सिद्धांत की नियमित भाषा परिभाषा। नियमित भाषाओं को निर्दिष्ट करने की विधियाँ। वर्णमाला, शब्द, भाषा

प्रयोगशाला कार्य क्रमांक 3

यदि नियमित भाषाओं और परिमित ऑटोमेटा के सिद्धांत का उपयोग किया जाता है तो एक शाब्दिक विश्लेषक का विकास काफी सरल है। इस सिद्धांत के ढांचे के भीतर, एक ही प्रकार के लेक्सेम के वर्गों को औपचारिक भाषा (पहचानकर्ताओं की भाषा, स्थिरांक की भाषा, आदि) के रूप में माना जाता है, जिसके वाक्यों के सेट को संबंधित जेनरेटिव व्याकरण का उपयोग करके वर्णित किया जाता है। इसके अलावा, ये भाषाएँ इतनी सरल हैं कि ये सबसे सरल व्याकरण - नियमित व्याकरण - द्वारा उत्पन्न होती हैं।

परिभाषा 1. उत्पादक व्याकरण जी = , जिसके नियमों का रूप है: A::=aB या C::=b, जहां A, B, C Є N; a, b Є Т को नियमित (स्वचालित) कहा जाता है।

ऑटोमेटन व्याकरण द्वारा उत्पन्न भाषा एल (जी) को ऑटोमेटन (नियमित) भाषा या राज्यों की सीमित संख्या वाली भाषा कहा जाता है।

उदाहरण 1. पहचानकर्ताओं का एक वर्ग, यदि पहचानकर्ता अक्षरों और संख्याओं से युक्त एक अनुक्रम है, और पहचानकर्ता का पहला अक्षर केवल एक अक्षर हो सकता है, तो निम्नलिखित जेनरेटिव नियमित व्याकरण जी = द्वारा वर्णित किया गया है , जिसमें

एन= (आई, के), टी = (बी, सी), एस=(आई),

पी = ( 1. आई::= बी

यहाँ b, c क्रमशः अक्षरों और संख्याओं को निर्दिष्ट करने के लिए सामान्यीकृत टर्मिनल प्रतीक हैं।

पहचानकर्ता "बीबीसीबीसी" उत्पन्न करने की प्रक्रिया को प्रतिस्थापन के निम्नलिखित अनुक्रम द्वारा वर्णित किया गया है

मैं => बीबीसी => बीबीसी => बीबीसीके => बीबीसीबीके => बीबीसीबीसी

हालाँकि, LA का मुख्य कार्य शाब्दिक इकाइयों का निर्माण नहीं, बल्कि उनकी पहचान है। किसी नियमित भाषा को पहचानने की प्रक्रिया का गणितीय मॉडल एक कंप्यूटिंग डिवाइस है जिसे परिमित राज्य मशीन (एफए) कहा जाता है। शब्द "परिमित" इस बात पर जोर देता है कि कंप्यूटिंग डिवाइस में मेमोरी की एक निश्चित और सीमित मात्रा होती है और कुछ सीमित सेट से संबंधित इनपुट प्रतीकों के अनुक्रम को संसाधित करता है। केए विभिन्न प्रकार के होते हैं, यदि केए आउटपुट फ़ंक्शन (कार्य का परिणाम) केवल इस बात का संकेत है कि प्रतीकों का इनपुट अनुक्रम स्वीकार्य है या नहीं, तो ऐसे केए को कहा जाता है अंतिम समाधानकर्ता.

परिभाषा 2. निम्नलिखित पाँच को परिमित ऑटोमेटन कहा जाता है:

ए = , जहां वी = (ए 1 , ए 2 , …, ए एम ) - इनपुट वर्णमाला (प्रतीकों का सीमित सेट);

क्यू = (क्यू 0 , क्यू 1 , …, क्यू एन -1 ) - राज्यों की वर्णमाला (प्रतीकों का सीमित सेट);

δ: Q ×V →Q - संक्रमण फलन;

क्यू 0 Є क्यू - परिमित ऑटोमेटन की प्रारंभिक अवस्था;

एफ Є क्यू - अंतिम राज्यों का सेट।

अंतरिक्ष यान के संचालन की योजना.

एक अनंत टेप है, जो कोशिकाओं में विभाजित है, जिनमें से प्रत्येक में V से एक प्रतीक हो सकता है। श्रृंखला α Є V* टेप पर लिखी गई है। श्रृंखला के बायीं और दायीं ओर की कोशिकाएँ खाली हैं। रीडिंग हेड के साथ एक अंतिम नियंत्रण उपकरण (एफसीयू) है, जो टेप के साथ बाएं से दाएं चलते हुए, टेप से अक्षरों को क्रमिक रूप से पढ़ सकता है। इस स्थिति में, नियंत्रण इकाई Q से किसी भी एक अवस्था में हो सकती है। नियंत्रण इकाई हमेशा प्रारंभिक अवस्था q 0 में अपना काम शुरू करती है, और अंतिम अवस्था F में से एक में समाप्त होती है। हर बार, एक नए सेल में चलती है टेप, नियंत्रण इकाई फ़ंक्शन के अनुसार एक नई स्थिति में चली जाती है।

अंतरिक्ष यान संक्रमण फ़ंक्शन को निम्नलिखित तरीकों से दर्शाया जा सकता है:

· टीमों का एक सेट;

· राज्य आरेख;

· संक्रमण तालिका.

स्टेट मशीन कमांड इस प्रकार लिखा गया है:

(क्यू आई, ए जे) → क्यू के, जहां क्यू आई, क्यू के Є क्यू; ए जे Є वी.

इस आदेश का अर्थ है कि राज्य मशीन राज्य q i में है, टेप से प्रतीक a j को पढ़ती है और राज्य q k पर जाती है।

ग्राफ़िक रूप से, कमांड को शीर्ष q i से शीर्ष q k तक जाने वाले ग्राफ चाप के रूप में दर्शाया जाता है और इनपुट वर्णमाला के प्रतीक a j के साथ चिह्नित किया जाता है:

संपूर्ण मानचित्रण के चित्रमय प्रतिनिधित्व को परिमित राज्य मशीन का राज्य आरेख कहा जाता है।

यदि अंतरिक्ष यान स्वयं को ऐसी स्थिति (q i, a j) में पाता है, जो किसी भी आदेश का बाईं ओर नहीं है, तो वह रुक जाता है। यदि नियंत्रण इकाई टेप पर दर्ज श्रृंखला α के सभी प्रतीकों को गिनती है, और साथ ही अंतिम स्थिति q r Є F पर जाती है, तो वे कहते हैं कि श्रृंखला α को परिमित राज्य मशीन द्वारा अनुमति दी जाती है।

अंतरिक्ष यान संक्रमण तालिका का निर्माण निम्नानुसार किया गया है: मैट्रिक्स कॉलम इनपुट वर्णमाला के प्रतीकों के अनुरूप हैं, पंक्तियाँ राज्य वर्णमाला के प्रतीकों के अनुरूप हैं, और मैट्रिक्स तत्व उन राज्यों के अनुरूप हैं जिनमें अंतरिक्ष यान इनपुट प्रतीक के दिए गए संयोजन के लिए जाता है और राज्य चिन्ह.

मान लीजिए कि एक नियमित व्याकरण G = है , जिसके नियमों का रूप है: A i::= a j A k या A i::= a j, जहां A i, A k Є N और a j Є T.

फिर परिमित ऑटोमेटन ए = , उसी भाषा को स्वीकार करते हुए जिसे नियमित व्याकरण जी उत्पन्न करता है, इस प्रकार बनाई गई है:

2) क्यू = एन यू (जेड), जेड एन और जेड टी, जेड अंतरिक्ष यान की अंतिम स्थिति है;

5) मैपिंग δ का निर्माण इस प्रकार किया गया है:

· फॉर्म ए आई::= ए जे ए के व्याकरण जी में प्रत्येक प्रतिस्थापन नियम कमांड (ए आई, ए जे) → ए के से जुड़ा हुआ है;

· फॉर्म A i::= a j का प्रत्येक प्रतिस्थापन नियम कमांड (A i, a j) → Z से जुड़ा है;

उदाहरण 2.उदाहरण 1 से व्याकरण के लिए एक CA का निर्माण करें। हमारे पास A = है , कहाँ

1) वी = टी = (बी, सी)

2) क्यू = एन यू (जेड) = (आई, आर, जेड)

3) क्यू 0 = (एस) = (आई)

5) δ: ए) कमांड के एक सेट के रूप में:

बी) राज्य आरेख के रूप में

नियतात्मक और गैर-नियतात्मक परिमित राज्य मशीनें हैं। अंतरिक्ष यान कहा जाता है गैर नियतात्मककेए (एनकेए), यदि इसके राज्य आरेख में एक ही शीर्ष से समान चिह्न वाले कई चाप निकलते हैं। उदाहरण के लिए, उदाहरण 2 से केए एक एनकेए है।

व्यावहारिक उद्देश्यों के लिए, यह आवश्यक है कि अंतिम पहचानकर्ता स्वयं वर्णों के इनपुट अनुक्रम के अंत का क्षण निर्धारित करे और इनपुट अनुक्रम की शुद्धता या त्रुटि के बारे में एक संदेश जारी करे। इन उद्देश्यों के लिए, इनपुट श्रृंखला को अंतिम मार्कर ├ द्वारा दाईं ओर सीमित माना जाता है और व्याख्या किए गए राज्यों को अंतरिक्ष यान के राज्य आरेख में दर्ज किया जाता है:

Z - "इनपुट श्रृंखला की अनुमति दें";

ओ - "इनपुट श्रृंखला में एक त्रुटि याद आ गई थी";

ई - "इनपुट श्रृंखला को अस्वीकार करें"।

राज्य Z और E अंतिम हैं, और अंतरिक्ष यान एक सही या गलत इनपुट श्रृंखला को संसाधित करने के बाद क्रमशः अंतिम मार्कर ├ को पढ़ते समय उनके पास जाता है। स्थिति O मध्यवर्ती है, जब इनपुट श्रृंखला में कोई त्रुटि पाई जाती है तो अंतरिक्ष यान अंतरिक्ष यान की किसी भी वैध स्थिति से इसमें चला जाता है और अंतिम मार्कर ├ आने तक वहीं रहता है, जिसके बाद यह स्थिति E में परिवर्तित हो जाता है - "इनपुट श्रृंखला को अस्वीकार करें। ”

माना कि L 1 और L 2 वर्णमाला की भाषाएँ हैं

फिर, यानी भाषा संयोजनइसमें पहली भाषा के सभी शब्दों का दूसरी भाषा के सभी शब्दों के साथ संयोजन शामिल है। विशेष रूप से, यदि , तब , और यदि , तब .

आइए हम भाषा एल की "डिग्री" के लिए संकेतन का परिचय दें:

इस प्रकार, L i में वे सभी शब्द शामिल हैं जिन्हें L से लगातार i शब्दों में विभाजित किया जा सकता है।

भाषा L का पुनरावृत्ति (L)* उन सभी शब्दों से बनता है जिन्हें L से लगातार कई शब्दों में विभाजित किया जा सकता है:

इसे डिग्री का उपयोग करके दर्शाया जा सकता है:

भाषा के "काटे गए" पुनरावृत्ति पर विचार करना अक्सर सुविधाजनक होता है, जिसमें खाली शब्द नहीं होता है यदि वह भाषा में मौजूद नहीं है: . यह कोई नया ऑपरेशन नहीं है, बल्कि अभिव्यक्ति के लिए बस एक सुविधाजनक शॉर्टहैंड है।

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

निम्नलिखित तालिका एक औपचारिक आगमनात्मक परिभाषा प्रदान करती है नियमित अभिव्यक्तिवर्णमाला और जिन भाषाओं का वे प्रतिनिधित्व करते हैं, उन पर।

अभिव्यक्ति आर	भाषा एल आर
	एल ए =(ए)
मान लीजिए r 1 और r 2 हैं	एल आर1 और एल आर2 -प्रतिनिधित्व योग्य
नियमित अभिव्यक्ति.	उन्हें भाषाएँ.
फिर निम्नलिखित भाव
नियमित हैं	और भाषाओं का प्रतिनिधित्व करते हैं:
आर=(आर 1 +आर 2)
आर=(आर 1 चक्र 2)
आर=(आर 1) *	एल आर =एल आर1 *

रिकॉर्डिंग करते समय नियमित अभिव्यक्तिहम संयोजन चिन्ह को छोड़ देंगे और मान लेंगे कि * ऑपरेशन की प्राथमिकता संयोजन और + से अधिक है, और संयोजन की प्राथमिकता + से अधिक है। इससे कई कोष्ठक छूट जाएंगे। उदाहरण के लिए, 10(1 * + 0) के रूप में लिखा जा सकता है।

परिभाषा 5.1. दो नियमित अभिव्यक्ति r और p को समतुल्य कहा जाता है यदि वे जिन भाषाओं का प्रतिनिधित्व करते हैं वे समान हैं, अर्थात। एल आर = एल पी . इस स्थिति में हम r = p लिखते हैं।

उदाहरण के लिए, निम्नलिखित की जाँच करना आसान है नियमित के गुणसंचालन:

• आर + पी= पी+ आर (संघ की क्रमपरिवर्तनशीलता),
• (आर+पी) +क्यू = आर + (पी+क्यू) (संघ की सहयोगीता),
• (आर पी) क्यू = आर (पी क्यू) (संयोजन की संबद्धता),
• (आर *) * = आर * (पुनरावृत्ति निष्क्रियता),
• (आर +पी) क्यू = आरक्यू + पी क्यू(वितरणशीलता)।

उदाहरण 5.1. आइए, उदाहरण के तौर पर, इतनी स्पष्ट समानता साबित न करें: (आर + पी) * = (आर * पी *) *।

मान लीजिए कि L 1 इसके बाईं ओर प्रदर्शित भाषा है, और L 2 इसके दाईं ओर प्रदर्शित भाषा है। खाली शब्द दोनों भाषाओं का है। यदि शब्द गैर-रिक्त है, तो पुनरावृत्ति की परिभाषा के अनुसार इसे भाषा से संबंधित उपशब्दों के संयोजन के रूप में दर्शाया जा सकता है। लेकिन यह भाषा भाषा L"=L r * L p * (क्यों?) का एक उपसमुच्चय है। इसलिए . इसके विपरीत, यदि कोई शब्द है, तो यह भाषा एल से संबंधित उपशब्दों के संयोजन के रूप में प्रतिनिधित्व योग्य है। ऐसे प्रत्येक उपशब्द v रूप में प्रतिनिधित्व योग्य है वी = वी 1 1 ... वी के 1 वी 1 2 ... वी एल 2, जहां सभी i=1, ... के लिए, k एक उपशब्द है और सभी j=1, ... के लिए, l एक उपशब्द है (यह संभव है कि k या l 0 के बराबर है)। लेकिन इसका मतलब यह है कि w उपशब्दों का एक संयोजन है, जिनमें से प्रत्येक और, इसलिए, से संबंधित है।

नियमित भाषा

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

नियमित सेट की परिभाषा

मान लीजिए Σ एक परिमित वर्णमाला है। नियमित सेटवर्णमाला Σ में R(Σ) को निम्नलिखित पुनरावर्ती गुणों द्वारा परिभाषित किया गया है:

यह सभी देखें

• ऑटोमेटा दृष्टिकोण के आधार पर एक पार्सर का निर्माण

विकिमीडिया फ़ाउंडेशन. 2010.

देखें अन्य शब्दकोशों में "नियमित भाषा" क्या है:

नियमित भाषा- - दूरसंचार विषय, बुनियादी अवधारणाएँ EN नियमित भाषा... तकनीकी अनुवादक मार्गदर्शिका

- (लैटिन रेगुलरियस, रेगुला नियम से)। सही, सही ढंग से व्यवस्थित, बनाया हुआ। मशीन को नियमित रूप से चलाना। यहां तक ​​कि स्ट्रोक भी. नियमित जीवन. सही, सभ्य, नीरस जीवन. रूसी भाषा में शामिल विदेशी शब्दों का शब्दकोश.... ... रूसी भाषा के विदेशी शब्दों का शब्दकोश

सेमी … पर्यायवाची शब्दकोष

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

इस शब्द के अन्य अर्थ हैं, क्वेशुआ देखें। क्वेशुआ स्व-नाम: किछ्वा सिमी, रूना सिमी देश ... विकिपीडिया

एक ही आकार के चरण के आधार पर स्तंभों या खंभों के ग्रिड के साथ एक इमारत का फ्रेम (बल्गेरियाई; Български) एकसमान कंकाल (चेक; Čeština) प्राविडेलनी कंकाल (जर्मन; Deutsch) रेगेलमासिज स्केलेट (हंगेरियन; मग्यार) szabályos... ... निर्माण शब्दकोश

- [फ़्रेंच पार्क] एक पार्क जिसमें ज्यामितीय रूप से नियमित लेआउट होता है, आमतौर पर एक अक्षीय लेआउट (बल्गेरियाई; Български) फ़्रेंस्की पार्क (चेक; Čeština) फ़्रैंकोज़्स्की पार्क (जर्मन; Deutsch) रेगेल्माइगर पार्क; फ्रांज़ोसिशर पार्क… … निर्माण शब्दकोश

क्वेशुआ स्व-नाम: किछवा सिमी, रूना सिमी देश: अर्जेंटीना, बोलीविया, कोलंबिया, पेरू, चिली, इक्वाडोर क्षेत्र: एंडीज आधिकारिक स्थिति: पेरू ... विकिपीडिया

तागालोग भाषा- (टैगल, टैगाला, टैगलो; टैगलॉग) फिलीपीन भाषाओं में से एक। प्रारंभिक वितरण का क्षेत्र फिलीपींस गणराज्य के सबसे राजनीतिक, आर्थिक और सांस्कृतिक रूप से महत्वपूर्ण क्षेत्र में है - द्वीप के मध्य और दक्षिणी भाग... ... भाषाई विश्वकोश शब्दकोश

पुस्तकें

• व्युत्पन्न क्रियाएँ. फिनिश व्याकरण का रहस्य. पाठ्यपुस्तक, सफ़रोनोव वी.डी.... मैनुअल रूसी भाषा के शैक्षिक साहित्य में फिनिश व्याकरण के सबसे दिलचस्प और अपर्याप्त रूप से प्रस्तुत अनुभागों में से एक - व्युत्पन्न क्रियाओं के लिए समर्पित है। इनका निर्माण क्रियाओं और नामों से होता है...