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 है