7.3 CFG PDA Turing Machine Chomsky Hierarchy Undecidability P NP PSC Computer Engineer परीक्षामा सीधा MCQ, short answer र long answer दुवै कोणबाट महत्त्वपूर्ण छ। यो नोटले पहिले शब्दको स्पष्ट परिभाषा दिन्छ, त्यसपछि exam-oriented तरिकाले concept, comparison, examples र revision points मिलाउँछ।

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

CFG PDA Turing Machine Chomsky Hierarchy Undecidability P NP

Standard definition: CFG PDA Turing Machine Chomsky Hierarchy Undecidability P NP is a core concept in the PSC Computer Engineer syllabus that explains principles, structures, processes, and practical use in computing systems.

सरल अर्थ: CFG PDA Turing Machine Chomsky Hierarchy Undecidability P NP भनेको कम्प्युटर इन्जिनियरले प्रणाली कसरी बनाउने, चलाउने, सुरक्षित राख्ने वा विश्लेषण गर्ने भन्ने बुझ्नुपर्ने आधारभूत विषय हो।

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।
  • CFG PDA Turing Machine Chomsky Hierarchy Undecidability P NP: 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.
  • CFG PDA Turing Machine Chomsky Hierarchy Undecidability P NP को 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

CFG PDA Turing Machine Chomsky Hierarchy Undecidability P NP बाट आउने प्रश्नमा definition, key features, working mechanism, merits/demerits र example जोडेर उत्तर बनाउनुहोस्। MCQ मा exact technical word र sequence सबैभन्दा धेरै सोधिन्छ।

Subjective Answer Framework

  • Start: CFG PDA Turing Machine Chomsky Hierarchy Undecidability P NP को 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

  • CFG PDA Turing Machine Chomsky Hierarchy Undecidability P NP को 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?
  • CFG PDA Turing Machine Chomsky Hierarchy Undecidability P NP को main purpose के हो?
  • CFG PDA Turing Machine Chomsky Hierarchy Undecidability P NP कुन layer/model/process/algorithm सँग सम्बन्धित छ?
  • CFG PDA Turing Machine Chomsky Hierarchy Undecidability P NP को एक प्रमुख advantage र limitation के हो?
  • Similar terms बीचको exact difference सम्झनुहोस्।