Ambiguity in Grammar in TOC in Hindi

Unit 3

Grammars

Topic 2 : Ambiguity in Grammar in TOC in Hindi

Computer Science में, एक ambiguous grammar एक context-free grammar है, जिसके लिए एक String exists करती है जिसमें एक से अधिक leftmost derivation या parse tree हो सकते हैं, जबकि एक unambiguous grammar एक context-free grammar है जिसके लिए प्रत्येक valid string है। एक unique leftmost derivation या parse tree। कई language ambiguous और unambiguous grammars दोनों को accept करती हैं, जबकि कुछ language केवल unambiguous grammars को accept करती हैं। कोई भी non-empty language unambiguous grammar को ले कर unambiguous grammar को accept करती है और duplicate rule या synonym को represent करती है । एक language जो केवल unambiguous grammar को accept करती है, उसे स्वाभाविक रूप से unambiguous language कहा जाता है, और स्वाभाविक रूप से unambiguous context-free languages होती हैं। Deterministic context-free grammars हमेशा unambiguous होते हैं, और unambiguous grammar के एक महत्वपूर्ण subclass होते हैं; हालाँकि, non-deterministic unambiguous grammar नहीं हैं।

Examples :

Trivial language :

सबसे simplest example trivial language के लिए निम्नलिखित ambiguous grammar है, जिसमें केवल Empty String है :

A → A | ε

इस Language में भी unambiguous grammar है, जिसमें single production rule शामिल हैं:

A → ε

Unary string :

किसी दिए गए character के unary strings की regular language, 'a' (regular expression a *) unambiguous grammar है:

A → aA | ε

Addition and subtraction :

context free grammar

A → A + A | A − A | a

ambiguous है क्योंकि String के लिए दो leftmost derivations हैं a + a a:

A	→ A + A	A	→ A + A
	→ a + A		→ A + A + A
	→ a + A + A		→ a + A + A
	→ a + a + A		→ a + a + A
	→ a + a + a		→ a + a + a

एक another example के रूप में, grammar ambiguous है क्योंकि String के लिए दो parse tree हैं a + a: a

Ambiguity in Grammar in TOC in Hindi

हालाँकि, यह जो language generates करता है, वह Natural रूप से ambiguous नहीं है; निम्नलिखित एक ही language का निर्माण करने वाला एक non-ambiguous grammar है

NP Complete Problem in Hindi

NP-Complete problems एक महत्वपूर्ण वर्ग हैं जो computational complexity the...

Multihead Turing Machine और Multidimensional Turing Machine की विशेषताएँ और अंतर

Multihead Turing Machine एक प्रकार की Turing Machine है जिसमें एक से अ�...

Universal Turing Machine and Multitape in Hindi

Universal Turing Machine (UTM) एक ऐसी ट्यूरिंग मशीन है, जो किसी भ...

Techniques for Turing Machine Construction in Hindi

Turing Machine कंप्यूटर विज्ञान में एक theoretical model है, जो क�...

Petri Net Model in Hindi | Theory of Computation (TOC) Explained

Petri Net एक mathematical model है जो systems के behavior को graphically represent करने �...

Ambiguity in Grammar in TOC in Hindi