सीएफजी

Question

पर नियमित अभिव्यक्ति को परिवर्तित करें मैं कुछ नियमित भाषा को इसके समकक्ष संदर्भ मुक्त व्याकरण में कैसे परिवर्तित कर सकता हूं? क्या उस नियमित अभिव्यक्ति से संबंधित डीएफए बनाना आवश्यक है या ऐसे रूपांतरण के लिए कुछ नियम है?

उदाहरण के लिए, निम्नलिखित नियमित अभिव्यक्ति

01 + 10 (11) ^{पर विचार *}

मैं कैसे व्याकरण ऊपर आरई के लिए इसी का वर्णन कर सकते हैं?

Answer 1

• ए चेंज + बी

  G -> AB 
  

को

G -> (empty) 
G -> A G 

एबी बदलें करने के लिए व्याकरण के लिए

G -> A 
G -> B 

बदलें ए *

और ए और बी पर पुनरावर्ती रूप से आगे बढ़ें बेस केस खाली भाषा (कोई प्रस्तुतियां) नहीं हैं और एक ही प्रतीक हैं।

अपने मामले

A -> 01 
A -> 10B 
B -> (empty) 
B -> 11B 

में भाषा परिमित automaton द्वारा वर्णित किया गया है: टर्मिनल प्रतीकों में से सेट के रूप में nonterminal प्रतीक के रूप में

• उपयोग राज्यों
• उपयोग भाषा
• कोई संक्रमण जोड़ा पी -> किसी भी संक्रमण के लिए aq p>> मूल automaton
• में अक्षर पर q व्याकरण

Answer 2

मुझे लगता है कि आप इसे औपचारिक व्याकरण में रूपांतरित करते हैं, फॉर्म V-> w के नियमों के साथ, जहां वी एक nonterminal है और डब्ल्यू टर्मिनल/nonterminals की एक स्ट्रिंग है। प्रारंभ करने के लिए, तो आप बस कह सकते हैं (मिश्रण CFG और regex वाक्यविन्यास):

कहाँ एस शुरुआत प्रतीक है। अब यह थोड़ा तोड़ने के (और स्पष्टता के लिए खाली स्थान के जोड़ने) करते हैं:

S -> 0 A 1 0 B 
A -> 1+ 
B -> (11)* 

कुंजी * तों और + प्रत्यावर्तन के लिए तों कन्वर्ट करने के लिए है। सबसे पहले, हम एक मध्यवर्ती नियम है कि रिक्त स्ट्रिंग को स्वीकार करता है डालने से एक प्लस को क्लीन तारा बदल देंगे:

S -> 0 A 1 0 B 
A -> 1+ 
B -> (empty) 
B -> C 
C -> (11)+ 

अंत में, हम प्रत्यावर्तन के लिए + संकेतन बदल देंगे:

S -> 0 A 1 0 B 
A -> 1 
A -> A 1 
B -> (empty) 
B -> C 
C -> 11 
C -> C 11 

को संभालने के लिए x?, बस इसे खाली बनाने वाले नियम और एक्स बनाने वाले नियम में विभाजित करें।

Answer 3

वास्तव में, विभिन्न सीएफजी व्याकरण एक ही भाषा का उत्पादन कर सकते हैं प्रारंभिक स्थिति के रूप में प्रारंभिक स्थिति का उपयोग करें। इसलिए एक नियमित अभिव्यक्ति (नियमित भाषा) दी गई है, इसकी सीएपीजी वापस मैपिंग अद्वितीय नहीं है।

निश्चित रूप से, आप एक सीएफजी बना सकते हैं जिसके परिणामस्वरूप नियमित अभिव्यक्ति होती है। उपरोक्त उत्तरों ने इसे प्राप्त करने के कुछ तरीके दिखाए।

आशा है कि यह आपको उच्च स्तर का विचार देगा।