TOC की Grammar

Grammar की परिभाषा

• एक सेट होता है production rules का, जो language की strings generate करने के लिए उपयोग होते हैं।
• English language जैसे grammar का उपयोग करके sentences बनाते हैं, इसी प्रकार machines (जैसे finite automata) languages accept करती हैं।
• Grammar को language generator कहा जाता है और finite automata को language acceptor कहा जाता है।

Language

• Language: Set of strings generated by any grammar.
• Grammar strings को generate करती है और finite automata उन्हें accept करती है।

Grammar के तत्व

• Production Rules: जिनके माध्यम से language की strings generate की जाती हैं।
• Example:
  • S → AB
  • A → a
  • B → b

Example

• Grammar:
  • S → AB
  • A → a
  • B → b
• यह grammar string "ab" generate करती है।
• Non-deterministic Finite Automata (NFA) बनाए:
  • Q0 (initial state) से Q1 पर A transition
  • Q1 से Q2 पर B transition
  • Q2 को final state बनाते हैं।

Formal Definition of Grammar

• Grammar एक four-tuple (V, T, P, S) है:
  1. V (Variables): सेट of variables (non-terminals)
  2. T (Terminals): सेट of terminals
  3. P (Production Rules): सेट of production rules
  4. S (Starting Symbol): grammar का starting symbol

Production Rules के स्वरूप

• Left hand side: कम से कम एक non-terminal होना चाहिए।
• Right hand side: epsilon या variables और terminals का कोई भी combination हो सकता है।

Grammar Elements

• Terminals: छोटे अक्षरों में, जो part of strings होते हैं।
• Non-terminals: बड़े अक्षरों में, जो variables होते हैं, strings generate करने के लिए।

Example of Grammar

• G = (V, T, P, S)
  • V: Non-terminals, जैसे कि S
  • T: Terminals, जैसे कि a, b
  • P: Production rules
    • S → aSbS
    • S → bSaS
    • S → ε
  • S: Starting symbol, जैसे की S

Additional Example

• Grammar के productions:
  • V → aVb
  • S → ε
• Variables: V, B, S
• Terminals: a, b
• Starting Symbol: S

यह notes TOC की grammar की बुनियादी समझ प्रदान करते हैं।