৪৯তম বিসিএস ⎯ কম্পিউটার সায়েন্স (CSE) [৯৭১]

Answer: A) Machine code
A) Correct — compiler’s primary goal is to produce executable machine-level instructions (though some compilers target assembly or bytecode as intermediate).

B) — assembly is one possible output but not the only; many compilers produce machine code or intermediate representations.

C) — Source code is computer program that is created by a programmer which needs to be translated for execution

D) Partially correct in some contexts (e.g., Java compilers to bytecode) but not generally; compiler target varies

Answer: B) Deterministic context-free 
A) Ambiguous grammar makes compiling harder.
B) Correct: deterministic CFLs (LR, LL) have parsers that are efficient and predictable.
C) Not related.
D) High-level refers to abstraction, not parsing ease.

Answer: A
Explanation: 

Syntax Error:

·  A syntax error means the program does not follow the grammar of the programming language.
· The compiler can detect this during parsing (syntax analysis).
· So yes, the compiler always detects syntax errors before generating code.

Logical Error:

A logical error means the program compiles successfully but does not behave as intended

· The compiler has no way to know the programmer’s intention, so it cannot detect logical errors.
· These are usually found by testing/debugging

Runtime Error:

Runtime errors occur when the program is running, not at compile-time

Runtime errors are handled by the runtime system or OS, not by the compiler

Answer: B) Memory allocation for processes at runtime 

A) Lexical: Core duty.
B) OS/runtime handles process memory allocation at run time; compiler prepares memory layout but not allocate runtime process memory.
C) Code optimization: compiler responsibility.
D) Error reporting: compiler reports syntax/semantic errors.

Answer: A) Tokens 
Explanation:
Lexical analyzer: 
→ Lexical analysis = scanning.
→ Breaks the input program into tokens (keywords, identifiers, operators, literals).

Example:

       int x = 10 + 5;
Lexical analyzer produces tokens like:

   int → keyword

   x → identifier

   = → assignment operator

   10 → constant

   + → operator

   5 → constant

    B) Parse tree produced by parser.
    C) Symbol table maintained but scanner mainly produces tokens.
    D) Object code is later.

 Answer: C) Token patterns for lexical analysis
Explanation
Regular Expressions:
•    Regular expressions (REs) are formal notations used to describe regular languages (a subset of formal languages).
•    They can specify patterns of strings → which is exactly what we need for token definitions in the lexical analysis phase of a compiler.
For example:
•    Identifier in C: [a-zA-Z_][a-zA-Z0-9_]*
•    Integer literal: [0-9]+
•    Whitespace: [\t\n ]+
The lexical analyzer (scanner) uses these patterns to group characters into tokens like if, while, identifier, number.

Answer: D) DFA 
•    Lexical analyzers implement DFA for efficiency.
•    NFA → converted to DFA for fast scanning.
•    PDA → used for syntax analysis (parsing).
•    Turing machine → more powerful (not needed here).

Answer: B) Unrecognized symbol 
    Example: Using @ in C source code.
    A) Syntax error (parser).
    C) Semantic error (semantic analyzer).
    D) Ambiguity in parsing (parser’s job).

Answer: A) Is used to implement token recognition without backtracking
Explanation
 DFA in Lexical Analysis:

→ The lexical analyzer (scanner) uses DFA to recognize tokens efficiently.

→ DFA reads one character at a time, transitions deterministically, and does not require backtracking.

   That’s why compilers prefer DFA over NFA → speed.

Answer: B) Invalid character in source (e.g., control char in identifier)
   A) Syntax error — parser.
   B) Correct — scanner should report illegal token.
   C) Semantic error — semantic analyzer.
   D) Semantic/optimizing or warning

Answer: C) Convert RE → NFA → DFA → minimize DFA → table-driven scanner 
A) CFG conversion unnecessary.
B) Overkill.
C) Correct: standard pipeline ensures determinism and speed.
D) Semantic actions supplement recognition.

 Answer: a) Terminals, nonterminals, productions, start symbol
Explanation
 Context-Free Grammar (CFG):

A CFG is a formal grammar that defines context-free languages (CFLs).

Introduced by Noam Chomsky, CFGs are used to describe the syntax of programming languages (in compiler design, used in parsing phase).

Formally, a CFG is a 4-tuple: G=(V,Σ,R,S)

Where:

V (Nonterminals): Variables representing syntactic categories (e.g., <expr>, <stmt>).

Σ (Terminals): Actual alphabet symbols (tokens) like if, +, id, ;.

R (Productions): Rules of the form A → α where A is a nonterminal and α is a string of terminals and nonterminals.

S (Start Symbol): One distinguished nonterminal from which derivations begin.

Answer: D) Grammar generates strings with multiple leftmost derivations 

Ambiguous grammar = at least one string with two or more parse trees.

Example: E → E + E | E * E | id.

String id + id * id has two parses (+ first or * first).

Answer: B) Top-down parsing

FIRST set → first possible terminal from a nonterminal.

FOLLOW set → terminals that can appear immediately after a nonterminal.

Used in LL(1) parser construction

Answer: C) Type checking, scope resolution, and building/enriching symbol table with attributes 
A) Lexical tokenization → Done by scanner.
B) Generating assembly code → Code generation later.
C) Correct: semantic phase enforces meaning.
D) Minimizing DFA →Lexical step.

Answer: C) Constant folding optimization in IR (though often in optimization phase) 

• A/B/D) Semantic duties.
• C) Optimization phase, although early compilers might do some folding earlier.

Answer: A) Stack of symbol tables (or hash table with scope links) 

  A) Correct: push new scope, pop on exit.
  B) Too simplistic.
  C/D) Irrelevant.

Answer: A) Static linking (linker resolves and produces executable)
 
    A) Correct: static linker resolves all at link time.
    B) Dynamic linking resolves at load/runtime via loader or dynamic linker.
   C) Lazy binding is dynamic technique for delaying resolution.
    D) Not correct.

Answer: D) Finite automata (DFA/NFA)

Explanation

Regular languages are the simplest class of languages in the Chomsky hierarchy.

They can be:
Described using regular expressions.

Recognized/accepted by finite automata (both Deterministic FA (DFA) and Nondeterministic FA (NFA)).

Example: Language of all strings over {0,1} ending with 01.

Regular expression: (0+1)*01

DFA can be constructed with states tracking whether we’ve seen "01" at the end.

Answer: C) Recursively enumerable languages (Type-0) 
A)  Regular languages → Weakest.
B) Context-free languages→ More powerful than regular, less than context-sensitive.
C) Recursively enumerable languages (Type-0) → Type-0 / RE are most general
D) Context-sensitive languages → More powerful than CFLs but less than Type-0.

Answer: A) Context-sensitive languages (CSLs)
Explanation

What is an LBA?

An LBA (Linear Bounded Automaton) is a type of Turing Machine (TM).

Restriction: The tape size is limited to a portion linearly bounded by the input size.

i.e., For input of length n, LBA can use at most O(n) tape cells.

Thus, it has limited memory, unlike unrestricted TM which has infinite tape.

 LBA in Chomsky Hierarchy:

Type-0 (Unrestricted Grammars): Recursively enumerable languages (recognized by Turing Machines).

Type-1 (Context-Sensitive Grammars): Context-Sensitive Languages (recognized by LBA).

Type-2 (Context-Free Grammars): Context-Free Languages (recognized by Pushdown Automata).

Type-3 (Regular Grammars): Regular Languages (recognized by Finite Automata).

So:
  LBA = Recognizer for Context-Sensitive Languages (Type-1).

 Answer: B) Some CFLs are inherently ambiguous (no unambiguous grammar exists for them)
Explanation:

 What is Ambiguity in CFG?

A CFG is ambiguous if there exists at least one string in the language that has more than one leftmost derivation, rightmost derivation, or parse tree.

Example (arithmetic grammar):

E → E + E | E * E | id

String: id + id * id

Can be parsed as (id + id) * id OR id + (id * id).

→ Ambiguous grammar.

Ambiguity in CFLs

Some context-free languages (CFLs) can be described by both ambiguous and unambiguous grammars.

E.g., Arithmetic expressions → ambiguous grammar above, but can be rewritten unambiguously with precedence rules:

E → E + T | T  
T → T * F | F  
F → id | (E)

But there exist inherently ambiguous CFLs:

Languages for which no unambiguous grammar exists at all.

Example:

L = { a^i b^j c^k | i = j or j = k }

 Answer: a) Q × Σ → Q
Explanation:

 Formal definition of DFA:

A DFA (Deterministic Finite Automaton) is a 5-tuple: M= (Q,Σ,δ,q0, F)

Where:

Q = finite set of states.

Σ = finite input alphabet.

δ = transition function.

q₀ ∈ Q = start state.

F ⊆ Q = set of accepting states.

DFA transition function δ: Q × Σ → Q

For each state and each input symbol, DFA specifies exactly one next state.

That’s why it is deterministic.

Example: DFA for strings over {0,1} ending in 1.

States: {q0 (start), q1 (accept)}

Transition function δ:

δ(q0,0) = q0

δ(q0,1) = q1

δ(q1,0) = q0

δ(q1,1) = q1

Here, δ maps from (state, symbol) → single next state.

Answer: A 
Explanation:
    AI is the field of computer science that focuses on creating machines capable of performing tasks that normally require human intelligence (reasoning, problem-solving, learning, understanding language, etc.).

Answer: C 
Explanation:
•    AI domains include ML, NLP, Computer Vision, Robotics, Expert Systems, Knowledge Representation, and Planning.

•    Data Structures is a programming concept, not a core domain of AI.

Answer: D 
Explanation:
 Core AI components:
    Learning (ML, Deep Learning)
    Reasoning (logic, inference)
    Perception (vision, speech recognition)
    Problem-solving, Planning, Knowledge Representation

    Disk Fragmentation → OS task, unrelated to AI

Answer: B 

Explanation:
The Turing Test is a benchmark for evaluating a machine's ability to exhibit human-like intelligence. Proposed by Alan Turing in 1950, the test involves a human judge engaging in a text-based conversation with both a human and a machine

Criteria for the Turing Test:
The Turing Test does not require the machine to be correct or logical in its responses but rather to be convincing in simulating human conversation. The key criteria include:
Natural Language Processing (NLP): The machine must understand and generate human language fluently.
Knowledge Representation: The machine needs to handle and manipulate knowledge to provide contextually relevant responses.
Reasoning: The machine should demonstrate some form of logical reasoning, even if flawed, to sustain a conversation.
Learning: Ideally, the machine should learn from the interaction, adapting its responses over time

Answer: A 
Explanation:
•    Computer vision → enabling machines to "see" and interpret images.
•    B & C → Natural Language Processing.
•    D → Knowledge-based reasoning

 Answer: (B) Facts and relationships about the world (what is), expressible in logic or semantic nets
Explanation
What is Declarative Knowledge?

Declarative knowledge = “know-what” type knowledge.

It describes facts, truths, and relationships about objects in the world.

Expressed using logic, semantic networks, frames, or ontologies.

Example:

“Paris is the capital of France.”

“All birds can fly (except some like penguins).”

This kind of knowledge does not tell you how to do something, it only tells you what is true.

 Procedural Knowledge vs Declarative Knowledge

Procedural Knowledge = “know-how” (skills, algorithms, procedures).

Example: "How to solve a Rubik’s cube," "Steps to drive a car."

Stored as production rules or algorithms.

Declarative Knowledge = “know-what” (facts, descriptions).

Example: "The cube has six faces," "A car has four wheels."

Quick Comparison Table

 Answer: (D) All of the above
 Explanation

Prolog (Programming in Logic) is a declarative, logic programming language based on first-order predicate logic.

Instead of writing how to solve a problem, you specify what is true (facts + rules).

The Prolog engine uses resolution and unification to answer queries.

Because of this reasoning ability, Prolog is widely used in AI domains.

? Option Analysis

(A) Automated reasoning 

Prolog was originally designed for automated theorem proving and logical inference.

Example: Proving statements like

Fact: mortal(X) :- human(X).

Query: ?- mortal(socrates).

Answer: Yes, since socrates is a human.

Prolog is excellent for rule-based expert systems and knowledge-based reasoning.

(B) Machine learning 

While modern ML uses Python/R, Prolog is used in symbolic AI and Inductive Logic Programming (ILP).

ILP combines machine learning with logic programming → learning general rules from examples.

Example: Given facts about family trees, Prolog can learn rules like "grandparent(X,Y) :- parent(X,Z), parent(Z,Y)."

(C) Robot planning 

Robots require planning, reasoning, and decision-making.

Prolog excels at search strategies, planning problems, and pathfinding (like STRIPS-based planning).

Example: A robot in a grid environment can use Prolog to infer the sequence of actions: move → pick → place.

Answer: (C) Depth-first search with backtracking
Explanation

 How Prolog Executes Queries:

Prolog uses SLD-resolution (Selective Linear Definite clause resolution) to answer queries.

It always works top-down and left-to-right through goals in the rule body.

The search strategy is:

Pick the first rule (clause) that matches the goal.

Try to satisfy it.

If it fails, backtrack to the last choice point, try the next rule.

This continues until either:

A solution is found.

Or all possibilities are exhausted (query fails).

This is basically depth-first search (DFS) with backtracking.

answer: (D) Pointers

Explanation

Features Prolog does have

A) Pattern Matching 

Prolog is built on unification, which is a more powerful form of pattern matching.

Example:

likes(john,X).
?- likes(john,mary).
Here X = mary is found through unification (pattern matching).

B) Recursion

Since Prolog doesn’t have loops (for, while), recursion is the natural way to express repetition.

Example:
factorial(0,1).
factorial(N,F) :- N > 0, N1 is N-1, factorial(N1,F1), F is N*F1.

Query ?- factorial(5,F). → returns F = 120.

C) Non-determinism 

Prolog doesn’t commit to just one solution; it can explore multiple possible answers using backtracking.

Example:

color(red).
color(blue).
color(green).

Query:

?- color(X).

Prolog answers:
X = red ; X = blue ; X = green. (all possible solutions, non-determinism).

Pointers (D) 

Pointers are a feature of imperative languages like C, C++.

Answer: C) Inferential knowledge
Explanation:
Inferential knowledge refers to the set of mechanisms or rules that produce new information from existing facts — e.g., logical inference rules, production rules, or transformation operators. It’s literally the “how to derive” knowledge.
Example: Modus ponens: from P and P → Q infer Q. That inference rule is inferential knowledge: it generates Q from given information.

Other options:
A) Inheritable knowledge — typically refers to properties inherited through hierarchical structures (like class inheritance in frames/ontologies). It passes down existing properties but doesn’t in itself derive brand-new facts beyond inheritance semantics.

B) Relational knowledge — describes relationships between entities (parent(A,B), located_in(city,country)). It is descriptive; it doesn’t by itself perform inference (though relational facts can be inputs to inference).

D) Procedural knowledge — is how-to knowledge (algorithms, recipes). It tells you how to perform tasks; it can lead to new outcomes when executed, but in KR taxonomy the phrase “generates new information from given information” more precisely matches inferential knowledge (rules/inference engines).

Answer: B) Relational

Explanation:

Relational knowledge encodes relationships among entities — comparisons are a special case of relations (e.g., greater than(a,b), similar_to(x,y), near(city1,city2)). When you compare two objects, you are expressing a relation between them.
Example comparisons: Alice > Bob (score), color_of(obj1) = red vs color_of(obj2) = blue — these are relational facts

Inferential Adequacy = ability to derive new knowledge from old.
Inferential Knowledge = the rules/mechanisms that generate new information.
Procedural Knowledge = programs/directions/recipes (how-to).
Relational Knowledge = comparisons / relations between objects.

Answer: (A) To perform tasks on behalf of a user
Explanation:
      Intelligent agents act autonomously to accomplish tasks, often in complex environments.
     Example: A personal assistant AI (like Siri) schedules meetings for you.
Others option:
    Data storage (b): Storage isn’t their purpose, though they may use memory.
    Hardware (c): Improving hardware isn’t the job of agents.
    Security (d): Some agents may do security tasks, but that’s just one application.

 Answer: (B) Autonomy
Explanation:
    Intelligent agents must be autonomous: able to make decisions and act without constant human intervention.
    Example: A vacuum-cleaning robot that senses dirt and cleans rooms without being micromanaged.
   
Others option:
    Redundancy: Not a core characteristic — may be desirable in systems for fault-tolerance, but not defining for agents.
   Complexity: Agents can be complex, but complexity itself isn’t the defining feature.
   Inflexibility: Opposite of what we want! Intelligent agents must adapt, not be rigid.

 Answer: (B) Cognitive modeling
   Explanation:
    Cognitive modeling simulates or mimics human thought processes.
   Involves building agents that learn tasks by observing humans and replicating their reasoning/behavior.
   Example: AI systems that learn to solve problems the way psychologists' model human cognition.

Others option:
    Supervised learning (a): Learns from labeled data, not directly from human behavior.
    Neural networking (c): A model type, not specifically about mimicking humans.
Reinforcement learning (d): Improves by trial and error via rewards/punishments, not by direct imitation

Answer: (A) Analyzing and understanding human languages

Explanation:
Natural Language Processing (NLP) is a branch of artificial intelligence that enables computers to understand, interpret, and generate human language, facilitating seamless interaction between humans and machines.

Key Applications:
NLP is widely used in various applications, including:
Chatbots and Virtual Assistants: Tools like Amazon's Alexa and Apple's Siri utilize NLP to understand and respond to user queries. 
Text Translation: Services like Google Translate use NLP to convert text from one language to another. 
Sentiment Analysis: Businesses use NLP to analyze customer feedback and social media interactions to gauge public sentiment. 
Speech Recognition: NLP enables voice-operated systems to convert spoken language into text, facilitating hands-free operation. 
Document Summarization: NLP techniques can automatically summarize long documents, making it easier for users to digest information quickly.

Answer: (B) Removing affixes from words to get the root form
    Explanation:
    Stemming reduces words to their base stem by chopping off prefixes/suffixes.
    Example:
    “playing” → “play”
    “studies” → “studi” (not always a valid word, just a stem).
    Stemming helps treat words with the same meaning as one.
Others option:
    (a) Visualization is data analysis, not stemming.
    (c) Encryption is cryptography, not NLP.
    (d) Synthetic speech → that’s speech generation (Text-to-Speech).

 Answer: C) Simulate conversational interaction with humans
    Explanation:
    Chatbots use NLP to understand queries and generate responses that mimic human conversation.
    Example: Siri, Alexa, ChatGPT.
    Why others are wrong:
    (a) Storage/retrieval is database work, not chatbot’s purpose.
    (c) Translating programming languages is compiler theory.
    (d) Image recognition is computer vision, not NLP

Answer: (C) Reducing words to their base or dictionary form
Explanation:
    Lemmatization uses vocabulary + grammar to return the dictionary (lemma) form of a word.
    Example:
    “running” → “run”
    “better” → “good” (uses dictionary knowledge).
    More accurate than stemming (which just chops endings).\

Why others are wrong:
    (a) Encryption ≠ lemmatization.
    (b) Grouping is clustering, not lemmatization.
    (d) Extracting entities is Named Entity Recognition (NER).

Answer: (A) Recognize and interpret human speech
Explanation:
    Speech recognition = Speech-to-Text (STT): converting spoken words into text for processing.
    Example: Dictating to Google Docs → it converts voice into written words.
Why others are wrong:
    (b) Improving audio quality = signal processing.
    (c) Translating speech into another language = speech translation, a higher-level task that uses recognition but is not identical.
    (d) Generating human-like speech = Text-to-Speech (TTS), not recognition

Answer: C) A system designed to emulate human expert decision-making 
T
An Expert System is a branch of AI designed to mimic the decision-making ability of a human expert in a specific domain (e.g., medicine, engineering, troubleshooting).

It consists of:

Knowledge Base → Contains facts and rules of the domain.
Inference Engine → Applies reasoning to draw conclusions from the knowledge base.
User Interface → Allows users to interact with the system.
Example: MYCIN (medical diagnosis), DENDRAL (chemical analysis).
These systems are used when human expertise is scarce or expensive.

Answer: B) Inference Engine 

The Inference Engine is the “brain” of the Expert System.
It applies logical reasoning techniques (like forward chaining or backward chaining) to the Knowledge Base in order to draw conclusions.
Functions of an inference engine:
→ Match facts with rules in the knowledge base.
→ Deduce new facts or make decisions.
→ Resolve conflicts when multiple rules are applicable (rule conflict resolution).
Example: In the medical Expert System MYCIN, the inference engine uses medical rules to suggest possible diagnoses and treatments.

(a) Database Manager
A Database Manager is responsible for handling storage, retrieval, and updating of large datasets.
It is part of a DBMS (Database Management System), not an Expert System.
While an Expert System might access databases, the Database Manager doesn’t perform reasoning or decision-making.
 
(c) Network Coordinator
A Network Coordinator would handle tasks like communication, routing, or synchronization in a distributed system or computer network.
It has nothing to do with Expert System reasoning.
Networking and Expert Systems are different domains of computer science.

 (d) Data Encryption Tool
A Data Encryption Tool secures information using cryptographic techniques.
Example: AES, RSA, or SSL protocols.
While encryption ensures data privacy, it does not help in drawing conclusions or reasoning in an Expert System.

 Answer: C) A system designed to emulate human expert decision-making 

An Expert System is a branch of AI designed to mimic the decision-making ability of a human expert in a specific domain (e.g., medicine, engineering, troubleshooting).
It consists of:

Knowledge Base → Contains facts and rules of the domain.
Inference Engine → Applies reasoning to draw conclusions from the knowledge base.
User Interface → Allows users to interact with the system.
Example: MYCIN (medical diagnosis), DENDRAL (chemical analysis).
These systems are used when human expertise is scarce or expensive.

(a) A system that enhances internet speeds
Enhancing internet speeds is related to network optimization and communication protocols (e.g., TCP/IP tuning, congestion control), not Expert Systems.
Expert Systems deal with reasoning and decision-making, not with bandwidth management or network throughput.
 
(b) A system that manages large databases
Managing large databases is the role of Database Management Systems (DBMS) like Oracle, MySQL, or MongoDB.
While an Expert System may use a database to store facts, it is not primarily concerned with database storage, retrieval, or query optimization.
Its main focus is on knowledge representation and inference, not raw data management.
 
 (d) A system used for computer hardware improvement
Hardware improvement is part of computer engineering (like making faster CPUs, GPUs, memory, etc.).
Expert Systems focus on knowledge-based reasoning, not on designing or optimizing hardware circuits.

Answer: (B) Enabling machines to interpret and analyze visual information from the world
Explanation:
          Computer Vision (CV) is a branch of Artificial Intelligence (AI) that Enabling machines to interpret and analyze visual information from the world much like humans. This tutorial is designed for both beginners and experienced professionals and covers key concepts such as Image Processing, Feature Extraction, Object Detection, Image Segmentation and other core techniques in CV.
 
 A) Making computers understand human languages is →Natural Language Processing (NLP).
 C) is networking, not CV.
 D) relates to cryptography/security, not CV.

Answer: A) Convolutional Neural Networks (CNNs)
Explanation:
A Convolutional Neural Network (CNN) is a specialized type of artificial neural network designed to process and analyze data with a grid-like structure, such as images. CNNs are widely used in computer vision tasks like image classification, object detection, and facial recognition due to their ability to automatically extract hierarchical features from raw data

B) Fourier Transform → Used in signal/image frequency analysis, but not the modern backbone of CV.
C) RSA → Encryption algorithm, unrelated.
D) Bubble Sort → Sorting algorithm, not CV.