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
हालाँकि, यह जो language generates करता है, वह Natural रूप से ambiguous नहीं है; निम्नलिखित एक ही language का निर्माण करने वाला एक non-ambiguous grammar है
Related Post
- What is Automata machine in hindi | Examples of automata machines
- Finite Automata as a language acceptor and translator | Deterministic Finite Automata (DFA) | Nondeterministic Finite Automata(NFA) in Hindi
- What is Moore machines and mealy machines in Hindi
- What is Turing machine (composite machine) in toc in hindi
- Conversion from Mealy to Moore and vice versa in Hindi
- Non Deterministic Finite Automata in Hindi (NDFA)
- Deterministic Finite Automaton in Hindi (DFA) | Deterministic Finite-State Machine (DFSM)
- Conversion of NDFA to DFA in Hindi
- Arden's Theorem in TOC in Hindi
- Minimization of DFA in Hindi (Minimization of Automata Machines)
- Regular Expression in TOC in Hindi
- Union process in DFA | What is Union process in TOC
- Intersection of Finite Automata in Hindi
- Properties of Context Free Languages Hindi
- Two-way Deterministic Finite Automaton (2DFA) in Hindi
- Types of Grammar in TOC in Hindi | Chomsky Hierarchy in Theory of Computation
- Derivation Tree in TOC in Hindi
- Ambiguity in Grammar in TOC in Hindi
- Simplification of context free grammar in Hindi
- Conversion of grammar to automata machine and vice versa in Hindi
- Chomsky normal form and Greibach normal form in hindi
- What is Pushdown Automata in TOC in Hindi
- Example of PDA in Hindi | Example of Pushdown Automata in Hindi
- Deterministic pushdown automaton And Non-Deterministic pushdown automaton in Hindi
- Conversion of PDA Into Context Free Grammar and Vice Versa | PDA in TOC in hindi | Push Down Automata in Hindi | Context Free Grammar in Hindi
- CFG equivalent to PDA in hindi | context free grammar equivalent to push down automata in hindi | toc tutorial in hindi | theory of computation in hindi