7.2 Theory of Computation Grammar DFA NFA Regular Expression Pumping Lemma PSC Computer Engineer परीक्षामा सीधा MCQ, short answer र long answer दुवै कोणबाट महत्त्वपूर्ण छ। यो नोटले पहिले शब्दको स्पष्ट परिभाषा दिन्छ, त्यसपछि exam-oriented तरिकाले concept, comparison, examples र revision points मिलाउँछ।

मुख्य परिभाषा

Theory of Computation Grammar DFA NFA Regular Expression Pumping Lemma

Standard definition: Theory of Computation Grammar DFA NFA Regular Expression Pumping Lemma is a core concept in the PSC Computer Engineer syllabus that explains principles, structures, processes, and practical use in computing systems.

सरल अर्थ: Theory of Computation Grammar DFA NFA Regular Expression Pumping Lemma भनेको कम्प्युटर इन्जिनियरले प्रणाली कसरी बनाउने, चलाउने, सुरक्षित राख्ने वा विश्लेषण गर्ने भन्ने बुझ्नुपर्ने आधारभूत विषय हो।

AI

Standard definition: AI studies systems that perform tasks requiring learning, reasoning, perception or planning.

सरल अर्थ: Machine लाई search, learning, reasoning, language, vision जस्ता काम गर्न बनाउने क्षेत्र।

Formal Language

Standard definition: A formal language is a set of strings defined over an alphabet using formal rules.

सरल अर्थ: नियमले define गरिएको symbol/string set।

सरल व्याख्या

Advanced CS मा theory र application दुवै चाहिन्छ। AI मा search/learning/reasoning, TOC मा automata/grammar/computability, compiler मा code translation phases, graphics मा geometry/raster/rendering, security मा confidentiality-integrity-authentication बुझ्नुहोस्।

How To Study This Topic

  • AI search tree trace गर्नुहोस्।
  • DFA/NFA/CFG/PDA/Turing comparison table बनाउनुहोस्।
  • Compiler phases क्रमबद्ध याद गर्नुहोस्।
  • Graphics pipeline flow बनाउनुहोस्।

Detailed Topic Breakdown

  • AI: search, NLP, learning, planning, vision।
  • TOC: language, grammar, automata, decidability।
  • Compiler: lexical, syntax, semantic, IR, optimization।
  • Graphics: primitive, transform, projection, rendering।
  • Security: cryptography, authentication, network protection।
  • Theory of Computation Grammar DFA NFA Regular Expression Pumping Lemma: definition, purpose, working process, important terms, advantages, limitations and one practical example तयार गर्नुहोस्।
  • Diagram/table practice: यो topic मा model, flow, layer, tree, state diagram, architecture वा algorithm भए सफा diagram बनाउने अभ्यास गर्नुहोस्।
  • PSC answer link: objective मा keyword सम्झने, subjective मा structured paragraph + comparison + conclusion लेख्ने।

परीक्षाका लागि पढ्नुपर्ने मुख्य कुरा

  • DFA has exactly one transition for each symbol/state.
  • NFA can have multiple transitions.
  • Lexical analyzer produces tokens.
  • Compiler translates high-level code to target code.
  • Cryptography supports confidentiality/integrity.
  • Theory of Computation Grammar DFA NFA Regular Expression Pumping Lemma को standard definition र purpose छुट्याएर सम्झनुहोस्।
  • Architecture, algorithm, protocol, model, process वा technique मध्ये यो कुन प्रकारको concept हो भनेर पहिचान गर्नुहोस्।
  • Advantages र limitations कम्तीमा ३/३ बुँदामा लेख्न सक्ने गरी तयार हुनुहोस्।
  • PSC subjective उत्तरमा diagram, table, steps र examples प्रयोग गर्दा उत्तर बलियो देखिन्छ।
  • MCQ का लागि full form, layer, sequence, formula, notation, command वा keyword गलत नहोस्।
  • यो topic लाई syllabus को exact wording सँग मिलाएर revision गर्नुहोस् ताकि प्रश्न आएपछि कुन heading बाट उत्तर सुरु गर्ने भन्ने तुरुन्त थाहा होस्।
Concept Exam focus Remember
DFA Deterministic One next state
NFA Nondeterministic Multiple choices
Compiler Whole program translation Optimization
Interpreter Statement execution Easier debugging

Exam point

Theory of Computation Grammar DFA NFA Regular Expression Pumping Lemma बाट आउने प्रश्नमा definition, key features, working mechanism, merits/demerits र example जोडेर उत्तर बनाउनुहोस्। MCQ मा exact technical word र sequence सबैभन्दा धेरै सोधिन्छ।

Subjective Answer Framework

  • Start: Theory of Computation Grammar DFA NFA Regular Expression Pumping Lemma को one-line definition लेख्नुहोस्।
  • Body: main components, working process, diagram/table and technical keywords मिलाउनुहोस्।
  • Comparison: मिल्दोजुल्दो concept सँग ३-४ फरक point राख्नुहोस्।
  • Evaluation: advantages, limitations and real application लेख्नुहोस्।
  • Close: Computer Engineer role वा public-sector system मा यसको relevance जोडेर निष्कर्ष दिनुहोस्।

Worked Answer Pattern

Compiler phase answer: source -> lexical tokens -> syntax tree -> semantic checks -> intermediate code -> optimization -> target code.

छोटो उदाहरण

“int x = 5;” मा lexical analyzer ले keyword/type, identifier, operator, literal, semicolon token बनाउँछ।

Common Mistakes

  • DFA/NFA transition rule confuse गर्नु।
  • Compiler/interpreter एउटै भन्नु।
  • AI लाई केवल machine learning मान्नु।

Summary

  • Theory of Computation Grammar DFA NFA Regular Expression Pumping Lemma को meaning, use र limitation छुट्याएर पढ्नुहोस्।
  • Objective paper का लागि keyword, full form, order र formula revision गर्नुहोस्।
  • Subjective paper का लागि structure: definition, diagram/table, explanation, merits, limitations, conclusion।

MCQ / Revision Points

  • Lexical analyzer output?
  • DFA vs NFA?
  • Turing machine importance?
  • Public key crypto keys?
  • Theory of Computation Grammar DFA NFA Regular Expression Pumping Lemma को main purpose के हो?
  • Theory of Computation Grammar DFA NFA Regular Expression Pumping Lemma कुन layer/model/process/algorithm सँग सम्बन्धित छ?
  • Theory of Computation Grammar DFA NFA Regular Expression Pumping Lemma को एक प्रमुख advantage र limitation के हो?
  • Similar terms बीचको exact difference सम्झनुहोस्।