औपचारिक भाषा

This article is about a technical term in mathematics and computer science. For related studies about natural languages, see Formal semantics (natural language).

वाक्यात्मक रूप से अच्छी तरह से गठित संरचना, हालांकि निरर्थक, अंग्रेजी वाक्य, रंगहीन हरे रंग के विचार उग्र रूप से सोते हैं (रंगहीन हरे रंग के विचार नोम चौमस्की 1957 से उग्र रूप से सोते हैं)।

तर्क, गणित, कंप्यूटर विज्ञान और भाषा विज्ञान में, एक औपचारिक भाषा में स्ट्रिंग (कंप्यूटर विज्ञान) होता है, जिसका प्रतीक (औपचारिक) एक वर्णमाला (औपचारिक भाषा) से लिया जाता है और एक विशिष्ट सेट के अनुसार अच्छी तरह से गठित होता है। नियम।

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

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

'औपचारिक भाषा सिद्धांत' का क्षेत्र मुख्य रूप से ऐसी भाषाओं के विशुद्ध वाक्य-विन्यास पहलुओं का अध्ययन करता है- अर्थात, उनके आंतरिक संरचनात्मक पैटर्न। औपचारिक भाषा सिद्धांत प्राकृतिक भाषाओं की वाक्यात्मक नियमितताओं को समझने के एक तरीके के रूप में, भाषाविज्ञान से उत्पन्न हुआ।

इतिहास

17वीं शताब्दी में, गॉटफ्रीड लीबनिज ने चरित्र चित्रण की कल्पना की और उसका वर्णन किया, एक सार्वभौमिक और औपचारिक भाषा जिसमें चित्रलेखों का उपयोग किया गया था। इस अवधि के दौरान, कार्ल फ्रेडरिक गॉस ने गॉस संकेतन की समस्या की भी जांच की। भगवान फ्रीज का शुक्र है ने लीबनिज के विचारों को महसूस करने का प्रयास किया, पहली बार शब्द लेखन (1879) में उल्लिखित एक सांकेतिक प्रणाली के माध्यम से और अपने 2-वॉल्यूम ग्रंडगेसेट्ज़ डेर अरिथमेटिक (1893/1903) में पूरी तरह से विकसित। इसने शुद्ध भाषा की एक औपचारिक भाषा का वर्णन किया। 20वीं शताब्दी के पूर्वार्द्ध में, औपचारिक भाषाओं की प्रासंगिकता के साथ कई विकास किए गए। एक्सल थ्यू ने 1906 और 1914 के बीच शब्दों और भाषा से संबंधित चार पत्र प्रकाशित किए। इनमें से अंतिम ने वह पेश किया जिसे एमिल पोस्ट ने बाद में 'थ्यू सिस्टम्स' कहा, और एक अनिर्णीत समस्या का एक प्रारंभिक उदाहरण दिया। पोस्ट बाद में इस पेपर को 1947 के प्रमाण के आधार के रूप में उपयोग करेगा "कि सेमीग्रुप्स के लिए शब्द समस्या पुनरावर्ती रूप से अघुलनशील थी", और बाद में औपचारिक भाषाओं के निर्माण के लिए पोस्ट कैनोनिकल सिस्टम तैयार किया।

नोआम चॉम्स्की ने औपचारिक और प्राकृतिक भाषाओं का एक अमूर्त प्रतिनिधित्व तैयार किया, जिसे चॉम्स्की पदानुक्रम के रूप में जाना जाता है। 1959 में जॉन बैकस ने फोरट्रान के निर्माण में अपने काम के बाद उच्च स्तरीय प्रोग्रामिंग भाषा के सिंटैक्स का वर्णन करने के लिए बैकस-नौर फॉर्म विकसित किया। पीटर नौर ने 1960 में इसी तरह की योजना का आविष्कार किया था।

एक वर्णमाला पर शब्द

एक वर्णमाला, औपचारिक भाषाओं के संदर्भ में, कोई भी सेट (गणित) हो सकता है, हालांकि यह अक्सर शब्द के सामान्य अर्थों में वर्णमाला का उपयोग करने के लिए समझ में आता है, या आमतौर पर किसी भी परिमित वर्ण एन्कोडिंग जैसे ASCII या यूनिकोड। किसी वर्णमाला के तत्वों को उसके अक्षर कहते हैं। एक वर्णमाला में तत्वों की एक गणनीय सेट संख्या हो सकती है; हालाँकि, औपचारिक भाषा सिद्धांत में अधिकांश परिभाषाएँ तत्वों की एक सीमित संख्या के साथ अक्षर निर्दिष्ट करती हैं, और अधिकांश परिणाम केवल उन्हीं पर लागू होते हैं।

एक अक्षर पर एक शब्द अक्षरों का कोई भी परिमित अनुक्रम (यानी, स्ट्रिंग (कंप्यूटर विज्ञान)) हो सकता है। वर्णमाला Σ पर सभी शब्दों का सेट आमतौर पर Σ द्वारा दर्शाया जाता है^* (क्लेन स्टार का उपयोग करके)। किसी शब्द की लंबाई उन अक्षरों की संख्या है जिनसे वह बना है। किसी भी वर्णमाला के लिए लंबाई 0 का केवल एक शब्द होता है, खाली शब्द, जिसे अक्सर ई, ε, λ या यहां तक ​​कि Λ द्वारा दर्शाया जाता है। संयोजन द्वारा कोई दो शब्दों को जोड़कर एक नया शब्द बना सकता है, जिसकी लंबाई मूल शब्दों की लंबाई का योग है। किसी शब्द को रिक्त शब्द से जोड़ने का परिणाम मूल शब्द होता है।

कुछ अनुप्रयोगों में, विशेष रूप से तर्कशास्त्र में, वर्णमाला को शब्दावली के रूप में भी जाना जाता है और शब्दों को सूत्र या वाक्य के रूप में जाना जाता है; यह अक्षर/शब्द रूपक को तोड़ता है और इसे शब्द/वाक्य रूपक से बदल देता है।

परिभाषा

वर्णमाला Σ पर एक औपचारिक भाषा L Σ का उपसमुच्चय है^*, यानी उस वर्णमाला पर शब्दों का समूह। कभी-कभी शब्दों के समुच्चय को भावों में समूहीकृत किया जाता है, जबकि 'सुगठित भाव' के निर्माण के लिए नियम और प्रतिबंध बनाए जा सकते हैं।

कंप्यूटर विज्ञान और गणित में, जो आमतौर पर प्राकृतिक भाषाओं से संबंधित नहीं होते हैं, विशेषण औपचारिक अक्सर अनावश्यक के रूप में छोड़े जाते हैं।

जबकि औपचारिक भाषा सिद्धांत आमतौर पर औपचारिक भाषाओं के साथ खुद को चिंतित करता है जो कुछ वाक्यात्मक नियमों द्वारा वर्णित हैं, औपचारिक भाषा की अवधारणा की वास्तविक परिभाषा केवल ऊपर दी गई है: एक (संभवतः अनंत) एक दिए गए वर्णमाला से बना परिमित-लंबाई के तार का सेट, और नहीं और कम नहीं। व्यवहार में, ऐसी कई भाषाएँ हैं जिन्हें नियमों द्वारा वर्णित किया जा सकता है, जैसे नियमित भाषाएँ या संदर्भ-मुक्त भाषाएँ। एक औपचारिक व्याकरण की धारणा एक भाषा की सहज अवधारणा के करीब हो सकती है, जिसे वाक्यात्मक नियमों द्वारा वर्णित किया गया है। परिभाषा के दुरुपयोग से, एक विशेष औपचारिक भाषा को अक्सर औपचारिक व्याकरण से सुसज्जित माना जाता है जो इसका वर्णन करता है।

उदाहरण

निम्नलिखित नियम एक औपचारिक भाषा का वर्णन करते हैंL वर्णमाला पर Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, =}:

• हर गैर-खाली स्ट्रिंग जिसमें + या = नहीं है और 0 से शुरू नहीं होता हैL.
• स्ट्रिंग 0 अंदर हैL.
• एक स्ट्रिंग युक्त = अंदर हैL अगर और केवल अगर बिल्कुल एक = है, और यह दो वैध तारों को अलग करता हैL.
• एक स्ट्रिंग जिसमें + है लेकिन = नहीं हैL यदि और केवल यदि प्रत्येक + स्ट्रिंग में दो मान्य स्ट्रिंग्स को अलग करता हैL.
• कोई स्ट्रिंग नहीं हैL पिछले नियमों द्वारा निहित के अलावा।

इन नियमों के तहत, स्ट्रिंग 23+4=555 अंदर हैL, लेकिन स्ट्रिंग =234=+ नहीं है। यह औपचारिक भाषा प्राकृतिक संख्या, अच्छी तरह से गठित जोड़ और अच्छी तरह से बनाई गई अतिरिक्त समानता को व्यक्त करती है, लेकिन यह केवल वही व्यक्त करती है जो वे दिखते हैं (उनके वाक्य-विन्यास), न कि उनका क्या मतलब है (शब्दार्थ)। उदाहरण के लिए, इन नियमों में कहीं भी ऐसा कोई संकेत नहीं है कि 0 का मतलब शून्य है, + का मतलब जोड़ है, 23+4=555 गलत है, आदि।

निर्माण

परिमित भाषाओं के लिए, सभी सुगठित शब्दों को स्पष्ट रूप से सूचीबद्ध किया जा सकता है। उदाहरण के लिए, हम एक भाषा का वर्णन कर सकते हैंL अभी अभी L= {ए,-बी,-एबी,-सीबीए}। इस निर्माण का पतन (गणित) मामला खाली भाषा है, जिसमें कोई भी शब्द नहीं है (L= ∅)।

हालांकि, Σ={a, b} जैसे परिमित (गैर-खाली) वर्णमाला पर भी परिमित-लंबाई वाले शब्दों की एक अनंत संख्या होती है जिन्हें संभावित रूप से व्यक्त किया जा सकता है: a , abb , aababba , aaababbbbaab , .... इसलिए , औपचारिक भाषाएं आम तौर पर अनंत होती हैं, और एक अनंत औपचारिक भाषा का वर्णन करना उतना आसान नहीं है जितना कि L = {a, b, ab, cba} लिखना। यहाँ औपचारिक भाषाओं के कुछ उदाहरण दिए गए हैं:

• L = एस^*, Σ पर सभी शब्दों का सेट;
• L = {ए}^* = {एⁿ}, जहां n प्राकृत संख्याओं के ऊपर है और aⁿ का अर्थ है बार-बार n बार (यह शब्दों का समूह है जिसमें केवल प्रतीक a );
• किसी दी गई प्रोग्रामिंग भाषा में वाक्यात्मक रूप से सही प्रोग्राम का सेट (जिसका सिंटैक्स आमतौर पर एक संदर्भ-मुक्त व्याकरण द्वारा परिभाषित किया जाता है);
• इनपुट का सेट जिस पर एक निश्चित ट्यूरिंग मशीन रुकती है; या
• इस रेखा पर अल्फ़ान्यूमेरिक ASCII वर्णों की अधिकतम स्ट्रिंग का सेट, यानी,
  सेट {the, set, of, maximal, string, alphanumeric, ASCII, characters, on, this, line, i, e}।

भाषा-विशिष्ट औपचारिकताएँ

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

• कुछ औपचारिक व्याकरण द्वारा उत्पन्न वे तार;
• वे तार जो किसी विशेष नियमित अभिव्यक्ति द्वारा वर्णित या मेल खाते हैं;
• वे तार कुछ ऑटोमेटा सिद्धांत द्वारा स्वीकार किए जाते हैं, जैसे कि ट्यूरिंग मशीन या परिमित-राज्य मशीन | परिमित-राज्य ऑटोमेटन;
• वे तार जिनके लिए कुछ निर्णय समस्या (एक कलन विधि जो संबंधित हाँ/नहीं प्रश्नों का अनुक्रम पूछता है) उत्तर हाँ उत्पन्न करता है।

ऐसी औपचारिकताओं के बारे में पूछे जाने वाले विशिष्ट प्रश्नों में शामिल हैं:

• उनकी अभिव्यक्ति शक्ति क्या है? (क्या औपचारिकता एक्स प्रत्येक भाषा का वर्णन कर सकती है जो औपचारिकता वाई वर्णन कर सकती है? क्या यह अन्य भाषाओं का वर्णन कर सकती है?)
• उनकी पहचान क्या है? (यह तय करना कितना मुश्किल है कि दिया गया शब्द औपचारिकता एक्स द्वारा वर्णित भाषा से संबंधित है या नहीं?)
• उनकी तुलना क्या है? (यह तय करना कितना मुश्किल है कि क्या दो भाषाएं, औपचारिकता एक्स में वर्णित एक और औपचारिकता वाई में वर्णित है, या फिर एक्स में, वास्तव में एक ही भाषा हैं?)

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

भाषाओं पर संचालन

भाषाओं पर कुछ ऑपरेशन आम हैं। इसमें मानक सेट ऑपरेशन शामिल हैं, जैसे कि संघ, चौराहा और पूरक। ऑपरेशन का एक अन्य वर्ग स्ट्रिंग ऑपरेशंस का तत्व-वार अनुप्रयोग है।

उदाहरण: मान लीजिए $L_{1}$ और $L_{2}$ कुछ सामान्य वर्णमाला पर भाषाएँ हैं $\Sigma$.

• संधि $L_{1}\cdot L_{2}$ प्रपत्र के सभी तार शामिल हैं $vw$ कहाँ $v$ से एक स्ट्रिंग है $L_{1}$ और $w$ से एक स्ट्रिंग है $L_{2}$.
• चौराहा $L_{1}\cap L_{2}$ का $L_{1}$ और $L_{2}$ दोनों भाषाओं में निहित सभी तार शामिल हैं
• पूरक $\neg L_{1}$ का $L_{1}$ इसके संबंध में $\Sigma$ सभी तार खत्म होते हैं $\Sigma$ जो अंदर नहीं हैं $L_{1}$.
• क्लेन स्टार: भाषा में सभी शब्द शामिल हैं जो मूल भाषा में शून्य या अधिक शब्दों के संयोजन हैं;
• उलट:
  • चलो ε तब खाली शब्द हो $\varepsilon ^{R}=\varepsilon$, और
  • प्रत्येक गैर-खाली शब्द के लिए $w=\sigma _{1}\cdots \sigma _{n}$ (कहाँ $\sigma _{1},\ldots ,\sigma _{n}$कुछ वर्णमाला के तत्व हैं), चलो $w^{R}=\sigma _{n}\cdots \sigma _{1}$,
  • फिर एक औपचारिक भाषा के लिए $L$, $L^{R}=\{w^{R}\mid w\in L\}$.
• स्ट्रिंग समरूपता

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

Closure properties of language families ($L_{1}$ Op $L_{2}$ where both $L_{1}$ and $L_{2}$ are in the language family given by the column). After Hopcroft and Ullman.

Operation		Regular	DCFL	CFL	IND	CSL	recursive	RE
Union	$L_{1}\cup L_{2}=\{w\mid w\in L_{1}\lor w\in L_{2}\}$	Yes	No	Yes	Yes	Yes	Yes	Yes
Intersection	$L_{1}\cap L_{2}=\{w\mid w\in L_{1}\land w\in L_{2}\}$	Yes	No	No	No	Yes	Yes	Yes
Complement	$\neg L_{1}=\{w\mid w\not \in L_{1}\}$	Yes	Yes	No	No	Yes	Yes	No
Concatenation	$L_{1}\cdot L_{2}=\{wz\mid w\in L_{1}\land z\in L_{2}\}$	Yes	No	Yes	Yes	Yes	Yes	Yes
Kleene star	$L_{1}^{*}=\{\varepsilon \}\cup \{wz\mid w\in L_{1}\land z\in L_{1}^{*}\}$	Yes	No	Yes	Yes	Yes	Yes	Yes
(String) homomorphism $h$	$h(L_{1})=\{h(w)\mid w\in L_{1}\}$	Yes	No	Yes	Yes	No	No	Yes
ε-free (string) homomorphism $h$	$h(L_{1})=\{h(w)\mid w\in L_{1}\}$	Yes	No	Yes	Yes	Yes	Yes	Yes
Substitution $\varphi$	$\varphi (L_{1})=\bigcup _{\sigma _{1}\cdots \sigma _{n}\in L_{1}}\varphi (\sigma _{1})\cdot \ldots \cdot \varphi (\sigma _{n})$	Yes	No	Yes	Yes	Yes	No	Yes
Inverse homomorphism $h^{-1}$	$h^{-1}(L_{1})=\bigcup _{w\in L_{1}}h^{-1}(w)$	Yes	Yes	Yes	Yes	Yes	Yes	Yes
Reverse	$L^{R}=\{w^{R}\mid w\in L\}$	Yes	No	Yes	Yes	Yes	Yes	Yes
Intersection with a regular language $R$	$L\cap R=\{w\mid w\in L\land w\in R\}$	Yes	Yes	Yes	Yes	Yes	Yes	Yes

अनुप्रयोग

प्रोग्रामिंग लैंग्वेज

Main articles: Syntax (programming languages) and Compiler-compiler

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

बेशक, कंपाइलर स्रोत कोड को पार्स करने से ज्यादा कुछ करते हैं - वे आमतौर पर इसे कुछ निष्पादन योग्य प्रारूप में अनुवादित करते हैं। इस वजह से, एक पार्सर आमतौर पर हां/नहीं उत्तर से अधिक आउटपुट देता है, आमतौर पर एक सार सिंटैक्स ट्री। इसका उपयोग कंपाइलर के बाद के चरणों द्वारा अंततः एक निष्पादन योग्य मशीन कोड उत्पन्न करने के लिए किया जाता है जो सीधे हार्डवेयर पर चलता है, या कुछ मध्यवर्ती कोड जिन्हें निष्पादित करने के लिए आभासी मशीन की आवश्यकता होती है।

औपचारिक सिद्धांत, प्रणालियाँ और प्रमाण

Main articles: Theory (mathematical logic) and Formal system

यह आरेख एक औपचारिक प्रणाली के भीतर सिंटेक्स (तर्क)तर्क) विभाजन दिखाता है। स्ट्रिंग (कंप्यूटर विज्ञान) को मोटे तौर पर बकवास और सुगठित सूत्रों में विभाजित किया जा सकता है। सुगठित सूत्रों के समुच्चय को प्रमेयों और गैर-प्रमेयों में विभाजित किया गया है।

गणितीय तर्क में, एक औपचारिक सिद्धांत एक औपचारिक भाषा में व्यक्त वाक्य (गणितीय तर्क) का एक सेट है।

एक औपचारिक प्रणाली (जिसे लॉजिकल कैलकुलस या लॉजिकल सिस्टम भी कहा जाता है) में एक औपचारिक भाषा होती है, जिसमें एक डिडक्टिव उपकरण (जिसे एक डिडक्टिव सिस्टम भी कहा जाता है) होता है। कटौतीत्मक तंत्र में परिवर्तन नियमों का एक सेट शामिल हो सकता है, जिसे अनुमान के वैध नियमों या स्वयंसिद्धों के एक सेट के रूप में व्याख्या किया जा सकता है, या दोनों हो सकते हैं। एक औपचारिक प्रणाली का उपयोग सिद्धांत को एक या एक से अधिक अन्य अभिव्यक्तियों से एक अभिव्यक्ति के लिए किया जाता है। यद्यपि एक औपचारिक भाषा को उसके सूत्रों से पहचाना जा सकता है, एक औपचारिक प्रणाली को उसके प्रमेयों द्वारा नहीं पहचाना जा सकता है। दो औपचारिक प्रणालियाँ ${\mathcal {FS}}$ और ${\mathcal {FS'}}$ सभी समान प्रमेय हो सकते हैं और फिर भी कुछ महत्वपूर्ण प्रमाण-सैद्धांतिक तरीके से भिन्न हो सकते हैं (एक सूत्र A एक सूत्र B का एक वाक्यात्मक परिणाम हो सकता है लेकिन उदाहरण के लिए दूसरा नहीं)।

एक औपचारिक प्रमाण या व्युत्पत्ति अच्छी तरह से निर्मित सूत्रों का एक परिमित अनुक्रम है (जो वाक्यों या प्रस्तावों के रूप में व्याख्या की जा सकती है) जिनमें से प्रत्येक एक स्वयंसिद्ध है या अनुमान के नियम द्वारा अनुक्रम में पूर्ववर्ती सूत्रों से अनुसरण करता है। अनुक्रम में अंतिम वाक्य एक औपचारिक प्रणाली का प्रमेय है। औपचारिक प्रमाण उपयोगी होते हैं क्योंकि उनके प्रमेयों की व्याख्या सच्चे प्रस्तावों के रूप में की जा सकती है।

व्याख्याएं और मॉडल

Main articles: Formal semantics (logic), Interpretation (logic), and Model theory

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

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

यह भी देखें

• शब्दों पर कॉम्बिनेटरिक्स
• मुक्त मोनोइड
• औपचारिक विधि
• व्याकरण की रूपरेखा
• गणितीय संकेतन
• सहयोगी सरणी
• स्ट्रिंग (कंप्यूटर विज्ञान)

संदर्भ

स्रोत

उद्धृत कार्य

• Hopcroft, John E.; Ullman, Jeffrey D. (1979). ऑटोमेटा सिद्धांत, भाषा और संगणना का परिचय. Reading, Massachusetts: Addison-Wesley Publishing. ISBN 81-7808-347-7.

सामान्य संदर्भ

• एजी हैमिल्टन, गणितज्ञों के लिए तर्क, कैम्ब्रिज यूनिवर्सिटी प्रेस, 1978, ISBN 0-521-21838-1.
• सीमोर गिन्सबर्ग, औपचारिक भाषाओं के बीजगणितीय और ऑटोमेटा सैद्धांतिक गुण, नॉर्थ-हॉलैंड, 1975, ISBN 0-7204-2506-9.
• माइकल ए. हैरिसन, इंट्रोडक्शन टू फॉर्मल लैंग्वेज थ्योरी, एडिसन-वेस्ले, 1978।
• Rautenberg, Wolfgang (2010). गणितीय तर्क का एक संक्षिप्त परिचय (3rd ed.). New York: Springer Science+Business Media. doi:10.1007/978-1-4419-1221-3. ISBN 978-1-4419-1220-6.
• ग्रेज़गोर्ज़ रोज़ेनबर्ग, अर्तो सलोमा, हैंडबुक ऑफ़ फॉर्मल लैंग्वेजेस: वॉल्यूम I-III, स्प्रिंगर, 1997, ISBN 3-540-61486-9.
• पैट्रिक सपेस, इंट्रोडक्शन टू लॉजिक, डी. वैन नोस्ट्रैंड, 1957, ISBN 0-442-08072-7.

बाहरी संबंध

• "Formal language", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• University of Maryland, Formal Language Definitions
• James Power, "Notes on Formal Language Theory and Parsing" Archived 21 November 2007 at the Wayback Machine, 29 November 2002.
• Drafts of some chapters in the "Handbook of Formal Language Theory", Vol. 1–3, G. Rozenberg and A. Salomaa (eds.), Springer Verlag, (1997):
  • Alexandru Mateescu and Arto Salomaa, "Preface" in Vol.1, pp. v–viii, and "Formal Languages: An Introduction and a Synopsis", Chapter 1 in Vol. 1, pp.1–39
  • Sheng Yu, "Regular Languages", Chapter 2 in Vol. 1
  • Jean-Michel Autebert, Jean Berstel, Luc Boasson, "Context-Free Languages and Push-Down Automata", Chapter 3 in Vol. 1
  • Christian Choffrut and Juhani Karhumäki, "Combinatorics of Words", Chapter 6 in Vol. 1
  • Tero Harju and Juhani Karhumäki, "Morphisms", Chapter 7 in Vol. 1, pp. 439–510
  • Jean-Eric Pin, "Syntactic semigroups", Chapter 10 in Vol. 1, pp. 679–746
  • M. Crochemore and C. Hancart, "Automata for matching patterns", Chapter 9 in Vol. 2
  • Dora Giammarresi, Antonio Restivo, "Two-dimensional Languages", Chapter 4 in Vol. 3, pp. 215–267