Final Examination 2023 (11th Batch) — Full Solution

Eight questions across intelligent agents, propositional & first-order logic, NLP, Hill Climbing, expert systems, knowledge representation, fuzzy logic, neural networks and robotics. Answer any five (full marks 70).

---

Question 1 — Introduction to AI & Intelligent Agents

(a) [4] What is intelligence? What are the approaches to understanding and designing AI systems? State them concisely.

(b) [3] To what extent are the following computer systems instances of artificial intelligence: supermarket bar code scanners; voice-activated telephone menus; spelling and grammar correction in MS Word; internet routing algorithms that respond dynamically to network state.

(c) [3] There are well-known classes of problems that are intractably difficult for computers, and other classes that are provably undecidable. Does this mean that AI is impossible?

(d) [4] Describe the PEAS components for the task environment of shopping for used AI books on the Internet.

Concept Needed

Intelligence, the four classical approaches to AI (acting humanly, thinking humanly, thinking rationally, acting rationally), PEAS (Performance, Environment, Actuators, Sensors), and bounded rationality.

(a) Intelligence & the Four Approaches to AI

Intelligence is the ability of a system to perceive its environment, learn from experience, reason about what to do, and take actions that maximise the chance of achieving a goal. Human intelligence combines perception, memory, language, planning, problem solving and learning.

The four classical approaches to designing AI systems (Russell & Norvig):

(b) AI Assessment of the Four Systems

(c) Are Intractability and Undecidability Proof that AI is Impossible?

No. Three reasons:

In short, difficulty in the worst case does not preclude good performance in the average case, and AI does not require omniscient optimality.

(d) PEAS for "Shopping for Used AI Books on the Internet"

$$\text{PEAS} = \langle \text{Performance},\ \text{Environment},\ \text{Actuators},\ \text{Sensors}\rangle$$

---

Question 2 — Propositional & First-Order Logic

(a) [3] Differentiate between "Propositional Logic" and "First Order Predicate Logic" with appropriate examples.

(b) [2] Add parenthesis in the following formula so that its structure can be fully understood without any convention. $p \wedge \neg q \leftrightarrow \neg p \vee p \rightarrow q$

(c) [3] With $P$: "Annie has a stomachache", $Q$: "Annie misses the exam", $R$: "Annie receives a passing grade", translate: (i) $Q \rightarrow (\neg R)$; (ii) $(P \rightarrow (\neg R)) \vee (Q \rightarrow (\neg R))$; (iii) $(\neg Q) \leftrightarrow R$.

(d) [6] Transform into FOPL: (i) "Sally sells shells by the sea shore"; (ii) "Only one person is the president"; (iii) "Everyone with the same last name share an ancestor".

Concept Needed

Two-valued vs many-sorted logic, syntactic precedence, English paraphrasing of propositional formulas, FOPL translations with quantifiers.

(a) Propositional vs First-Order Predicate Logic

(b) Parenthesising the Formula

The standard precedence (highest → lowest) is $\neg,\ \wedge,\ \vee,\ \rightarrow,\ \leftrightarrow$. Applying it and grouping left-to-right for same-precedence operators:

$$\boxed{\;\bigl((p \wedge (\neg q)) \leftrightarrow ((\neg p) \vee p)\bigr) \rightarrow q\;}$$

Step-by-step grouping:

1. $\neg q$, $\neg p$ bind tightest: $p \wedge (\neg q)$ and $(\neg p) \vee p$.
2. $\leftrightarrow$ binds next: $(p \wedge \neg q) \leftrightarrow (\neg p \vee p)$.
3. $\rightarrow$ binds last: the biconditional is the antecedent, $q$ the consequent.

The inner sub-formula $(\neg p) \vee p$ is a tautology (always true), so the biconditional reduces to $p \wedge \neg q$ and the whole formula simplifies to $(p \wedge \neg q) \rightarrow q$.

(c) English Translations

1. $Q \rightarrow (\neg R)$: "If Annie misses the exam, then she does not receive a passing grade from the subject."
2. $(P \rightarrow (\neg R)) \vee (Q \rightarrow (\neg R))$: "Either if Annie has a stomachache then she does not receive a passing grade, or if she misses the exam then she does not receive a passing grade." Equivalently: "Annie does not receive a passing grade if she has a stomachache or if she misses the exam."
3. $(\neg Q) \leftrightarrow R$: "Annie does not miss the exam if and only if she receives a passing grade from the subject." In words: she gets a pass exactly when she does not miss the exam.

(d) FOPL Translations

(d-i) "Sally sells shells by the sea shore."

Let $Sells(x,y)$ = "$x$ sells $y$" and $By(x,y)$ = "$x$ is by $y$".

$$\boxed{\;Sells(\text{Sally},\ \text{Shells}) \wedge By(\text{Shells},\ \text{SeaShore})\;}$$

(d-ii) "Only one person is the president."

Let $President(x)$ = "$x$ is the president", $Person(x)$ = "$x$ is a person". "Only one" = there exists a president and no two distinct persons are both presidents:

$$\boxed{\;\exists x\bigl(Person(x) \wedge President(x)\bigr) \;\wedge\; \forall x\,\forall y\bigl((President(x) \wedge President(y)) \rightarrow x = y\bigr)\;}$$

(d-iii) "Everyone with the same last name share an ancestor."

Let $Person(x)$ = "$x$ is a person", $LastName(x,y)$ = "$y$ is $x$'s last name", $Ancestor(z,x)$ = "$z$ is an ancestor of $x$".

$$\boxed{\;\forall x\,\forall y\,\forall w\bigl((Person(x) \wedge Person(y) \wedge \exists n\,(LastName(x,n) \wedge LastName(y,n))) \rightarrow \exists z\,(Person(z) \wedge Ancestor(z,x) \wedge Ancestor(z,y)))\bigr)\;}$$

---

Question 3 — NLP & Chomsky Hierarchy

(a) [4] Define "Natural Language Processing". Differentiate between syntactic analysis and semantic analysis with appropriate examples.

(b) [6] Describe different levels of Chomsky Hierarchy.

(c) [4] Using the given CFG, create two parse trees for the sentence "He drove down the street in the car".

Concept Needed

NLP pipeline, syntactic vs semantic analysis, the Chomsky hierarchy (regular, context-free, context-sensitive, unrestricted), and attachment ambiguity.

(a) NLP, Syntactic vs Semantic Analysis

A sentence can be syntactically perfect yet semantically nonsense — hence the two analyses are separate stages of the NLP pipeline.

(b) The Chomsky Hierarchy

Type-3 — Regular grammars. Productions of the form $A \rightarrow aB$ (right-linear) or $A \rightarrow Ba$ (left-linear). Cannot generate nested structures like matched parentheses. Recognised by a finite-state automaton with no memory. Example: $a^n b^n$ is not regular.

Type-2 — Context-free grammars. Productions $A \rightarrow \beta$ where $\beta$ is any string of terminals and non-terminals. CFGs capture nested structure (matched brackets, recursive noun phrases). Recognised by a push-down automaton. Used for most programming languages and natural-language phrase structure.

Type-1 — Context-sensitive grammars. Productions $\alpha A \beta \rightarrow \alpha \gamma \beta$ with $|\gamma| \ge 1$: $A$ can be rewritten only in the context $\alpha\,\cdot\,\beta$. Captures cross-serial dependencies such as Swiss-German nested agreement. Recognised by a linear-bounded automaton. Example: $a^n b^n c^n$ is context-sensitive but not context-free.

Type-0 — Unrestricted grammars. Productions $\alpha \rightarrow \beta$ with no restriction except that $\alpha$ is non-empty. Generate exactly the recursively enumerable languages, i.e. those decidable by some Turing machine. Includes every other level and many more.

Nesting relation:

$$\text{Regular} \subsetneq \text{Context-free} \subsetneq \text{Context-sensitive} \subsetneq \text{Recursively enumerable}$$

(c) Two Parse Trees — Attachment Ambiguity

The sentence "He drove down the street in the car" is ambiguous because the PP "in the car" can attach either to the verb drove or to the NP the street.

Grammar (given): $S \rightarrow NP\ VP \mid Aux\ NP\ VP \mid VP$; $NP \rightarrow Det\ Nom \mid proper\text{-}N$; $Nom \rightarrow Noun\ Nom \mid N$; $VP \rightarrow V \mid V\ NP \mid V\ PP$; $PP \rightarrow Prep\ NP$; $Det \rightarrow a \mid an \mid the$; $N \rightarrow book \mid flight \mid meal \mid car \mid street \mid bus \mid cycle$; $V \rightarrow book \mid include \mid prefer \mid drove \mid eat \mid play$; $Prep \rightarrow from \mid to \mid on \mid up \mid down \mid in$; $Pro \rightarrow I \mid He \mid She$.

Parse 1 — PP attaches to VP. He drove [down the street] [in the car]; the car is the vehicle he drove.

text

Copy

Parse 2 — PP attaches to the inner NP. He drove down [the street in the car]; the car physically is on the street (a noun-modifier PP).

text

Copy

(The simplified tree above shows the second PP nested inside the inner $Nom$, illustrating noun attachment. Different grammars render it differently — the structural fact is just that some subtree hangs off the noun phrase rather than the verb.)

---

Question 4 — Search, Hill Climbing & Backward Chaining

(a) [2] What information does the "Search Space" contain?

(b) [4] Explain different properties of "Hill Climbing" search algorithm.

(c) [4] Using state-space diagram describe different regions of "Hill Climbing" search algorithm.

(d) [4] Rules: R1 IF priority THEN discount 20 %; R2 IF purchase > $200 THEN priority; R3 IF fan-club-member THEN priority. Fact: purchase >$200. Goal: will the customer get 20 % discount? Use Backward Chaining.

Concept Needed

State-space search, hill climbing, local maxima / plateaus / ridges, and backward-chaining inference.

(a) What the Search Space Contains

The search space (state space) contains the five items that completely describe any search problem:

$$\langle S,\ A,\ s_0,\ Goal,\ Cost \rangle$$

1. Initial state $s_0$ — where the agent starts.
2. Set of states $S$ — every configuration the world can be in.
3. Successor function $Actions(s) \rightarrow S$ — legal moves and what state each move produces.
4. Goal test — a predicate that tells whether a state is a goal (or how far it is from one).
5. Path cost $c(s, a, s')$ — the numeric cost of applying action $a$ in state $s$ to reach $s'$.

(b) Properties of Hill Climbing

(c) Regions of the State-Space Landscape

(d) Backward Chaining — Discount Example

Backward chaining starts from the goal and reasons backward to the known fact(s).

Rules

• R1: IF $priority$ THEN $discount(20\%)$
• R2: IF purchase > \200$THEN$priority$
• R3: IF $fan\text{-}club\text{-}member$ THEN $priority$

Fact: purchase > \200$· **Goal:**$discount(20%)$.

Conclusion: Yes, the customer gets a 20 % discount.

---

Question 5 — Knowledge Representation, Normal Forms & Reasoning

(a) [3] Express "Car, bicycle and Truck are Vehicles. Toyota Corolla is a model of the Car. Both Toyota Corolla and Truck has wheels. Truck can transport a Bicycle." as an associative network.

(b) [2] With an example, show how property can be inheritance in an associative network.

(c) [3] Convert to DNF: $\neg(\neg P \vee Q) \vee (R \rightarrow \neg S)$ (no truth table).

(d) [3] Convert to CNF: $(\neg P \vee \neg Q) \rightarrow (P \leftrightarrow \neg Q)$.

(e) [3] Name the reasoning type of: (i) "If you are carrying a container that's open on one side, you should carry it with open end up." (ii) "I heard scratching sounds and saw droppings — must be a mice infestation." (iii) "Water on a lit stove boils; turn off the flame and it cools."

Concept Needed

Semantic networks, property inheritance, DNF/CNF conversion, and the three forms of reasoning.

(a) Associative Network

Nodes are concepts / instances; arcs are labelled relations.

In tabular form (only labels matter; picture above):

(b) Property Inheritance

Suppose we add the property Vehicle has-part wheels. Through the is-a chain, Truck inherits has-part wheels from Vehicle even though we never explicitly attached it to Truck.

text

Copy

The same inheritance gives the property to Car and Bicycle for free. This is the attribute inheritance rule of semantic networks: an instance inherits every attribute of every class on its is-a chain unless overridden.

(c) DNF Conversion

$$\neg(\neg P \vee Q) \vee (R \rightarrow \neg S)$$

Step 1. Eliminate $\rightarrow$: $R \rightarrow \neg S \equiv \neg R \vee \neg S$. Formula becomes $\neg(\neg P \vee Q) \vee (\neg R \vee \neg S)$.

Step 2. Push $\neg$ inside using De Morgan: $\neg(\neg P \vee Q) \equiv P \wedge \neg Q$. Formula becomes $(P \wedge \neg Q) \vee \neg R \vee \neg S$.

Step 3. Distribute $\vee$ over $\wedge$: $(P \wedge \neg Q) \vee \neg R \vee \neg S$ is already a disjunction of conjunctions.

$$\boxed{\;(P \wedge \neg Q)\ \vee\ \neg R\ \vee\ \neg S\;}$$

(d) CNF Conversion

$$(\neg P \vee \neg Q) \rightarrow (P \leftrightarrow \neg Q)$$

Step 1. Eliminate $\rightarrow$ and $\leftrightarrow$:

• $P \leftrightarrow \neg Q \equiv (P \rightarrow \neg Q) \wedge (\neg Q \rightarrow P) \equiv (\neg P \vee \neg Q) \wedge (Q \vee P)$.
• Outer $\rightarrow$: $A \rightarrow B \equiv \neg A \vee B$.

Formula becomes $\neg(\neg P \vee \neg Q) \vee [(\neg P \vee \neg Q) \wedge (Q \vee P)]$.

Step 2. Push $\neg$ inside: $\neg(\neg P \vee \neg Q) \equiv P \wedge Q$.

Formula becomes $(P \wedge Q) \vee [(\neg P \vee \neg Q) \wedge (Q \vee P)]$.

Step 3. Distribute $\vee$ over $\wedge$:

$$\bigl[(P \wedge Q) \vee (\neg P \vee \neg Q)\bigr] \;\wedge\; \bigl[(P \wedge Q) \vee (Q \vee P)\bigr] \equiv \bigl[(P \wedge Q) \vee (\neg P \vee \neg Q)\bigr] \;\wedge\; (Q \vee P)$$

Step 4. Distribute the left conjunct:

$$(P \wedge Q) \vee (\neg P \vee \neg Q) \equiv (P \vee \neg P \vee \neg Q) \wedge (Q \vee \neg P \vee \neg Q) \equiv (Q \vee \neg P \vee \neg Q)$$

(since $P \vee \neg P$ is a tautology).

Step 5. Combine.

$$\boxed{\;(Q \vee \neg P \vee \neg Q)\ \wedge\ (Q \vee P)\;}$$

Both disjunctions are CNF clauses; the formula is in CNF.

(e) Reasoning Types

---

Question 6 — Fuzzy Logic and Fuzzy Set Operations

(a) [3] Differentiate between "Boolean Logic" and "Fuzzy Logic".

(b) [5] Briefly explain the architecture of a Fuzzy Logic System.

(c) [2] With $A = \{(0.7,2),(0.2,3),(0.9,4)\}$, $B = \{(0.6,2),(1.0,3),(0.5,4)\}$, evaluate (i) $\overline{A \cup B}$ and (ii) $\overline{A} \cup \overline{B}$.

(d) [4] With $A = \{0.1/1, 0.8/2, 0.3/3, 0/4, 1/5\}$, find the fuzzy sets for: (i) "ANYTHING BUT (A)", (ii) "SOMEWHAT OF (A)", (iii) "VERY OF (A)", (iv) "EXTREMELY OF (A)".

Concept Needed

Two-valued vs many-valued logic, FIS architecture (fuzzifier → knowledge base → inference engine → defuzzifier), Zadeh's connectives, and the four standard linguistic hedges.

(a) Boolean vs Fuzzy Logic

(b) Architecture of a Fuzzy Logic System

(c) Fuzzy Set Operations

Given

$$A = \{(0.7,2),\,(0.2,3),\,(0.9,4)\},\quad B = \{(0.6,2),\,(1.0,3),\,(0.5,4)\}.$$

Step 1 — Union. Point-wise maximum:

$$A \cup B = \{(\max(0.7,0.6),2),\,(\max(0.2,1.0),3),\,(\max(0.9,0.5),4)\} = \{(0.7,2),\,(1.0,3),\,(0.9,4)\}.$$

Step 2 — Complement $\overline{A \cup B}$. Point-wise $\mu \mapsto 1 - \mu$:

$$\boxed{\;\overline{A \cup B} = \{(0.3,2),\ (0.0,3),\ (0.1,4)\}\;}$$

Step 3 — $\overline{A}$ and $\overline{B}$:

$$\overline{A} = \{(0.3,2),\ (0.8,3),\ (0.1,4)\},\quad \overline{B} = \{(0.4,2),\ (0.0,3),\ (0.5,4)\}.$$

Step 4 — Union of complements:

$$\boxed{\;\overline{A} \cup \overline{B} = \{(\max(0.3,0.4),2),\,(\max(0.8,0.0),3),\,(\max(0.1,0.5),4)\} = \{(0.4,2),\ (0.8,3),\ (0.5,4)\}\;}$$

Observation. $\overline{A \cup B} \neq \overline{A} \cup \overline{B}$. This is the Zadeh De Morgan identity:

$$\overline{A \cup B} = \overline{A} \cap \overline{B}.$$

(d) Linguistic Hedges

Given $A = \{0.1/1,\, 0.8/2,\, 0.3/3,\, 0/4,\, 1/5\}$. The standard Zadeh hedges apply a power $\mu \mapsto \mu^{\alpha}$ to each membership:

(i) ANYTHING BUT = $\overline{A}$:

$$\boxed{\;\{0.9/1,\ 0.2/2,\ 0.7/3,\ 1/4,\ 0/5\}\;}$$

(ii) SOMEWHAT OF = $A^{0.5}$ (square roots):

$$\boxed{\;\{\sqrt{0.1}/1,\ \sqrt{0.8}/2,\ \sqrt{0.3}/3,\ 0/4,\ 1/5\} = \{0.316/1,\ 0.894/2,\ 0.548/3,\ 0/4,\ 1/5\}\;}$$

(iii) VERY OF = $A^{2}$:

$$\boxed{\;\{0.01/1,\ 0.64/2,\ 0.09/3,\ 0/4,\ 1/5\}\;}$$

(iv) EXTREMELY OF = $A^{3}$:

$$\boxed{\;\{0.001/1,\ 0.512/2,\ 0.027/3,\ 0/4,\ 1/5\}\;}$$

---

Question 7 — Neural Networks & Machine Learning Overview

(a) [4] What is a neural network? Design a fully-connected feedforward neural network for 4 input neurons, one hidden layer with 3 neurons and one output neuron, with activation.

(b) [6] Forward pass the 3-4-2 network with the given weights, biases and inputs using sigmoid.

(c) [4] Brief overview of various machine learning techniques.

Concept Needed

Feedforward neural networks, weighted-sum + activation forward pass, and the three-way classification of ML techniques.

(a) Neural Network Definition and 4-3-1 Architecture

4-3-1 architecture — four inputs, one hidden layer of three neurons, one output neuron.

The hidden layer activations and the output are computed as

$$z_j = \sum_{i=1}^{4} w_{ij} x_i + b_j,\quad h_j = f(z_j),\quad y = f\!\Bigl(\sum_{j=1}^{3} v_j h_j + c\Bigr).$$

Total trainable parameters: $4 \times 3$ (input→hidden weights) + $3$ (hidden biases) + $3 \times 1$ (hidden→output weights) + $1$ (output bias) = $19$ parameters.

(b) Forward Pass through the 3-4-2 Network

Given:

• $\mathbf{x} = (0.5, 0.6, 0.7)$
• $W = \begin{bmatrix}0.1&0.2&0.3&0.4\\0.5&0.6&0.7&0.8\\0.9&0.10&0.11&0.12\end{bmatrix}$, $\mathbf{b} = (0.21, 0.22, 0.23, 0.24)$.
• $V = \begin{bmatrix}0.13&0.14\\0.15&0.16\\0.17&0.18\\0.19&0.20\end{bmatrix}$, $\mathbf{c} = (0.25, 0.26)$.
• $\sigma(t) = \dfrac{1}{1 + e^{-t}}$.

Step 1 — hidden pre-activations $\mathbf{z} = W^{\top}\mathbf{x} + \mathbf{b}$:

Step 2 — hidden activations $h_j = \sigma(z_j)$:

So $\mathbf{h} = (0.7668,\ 0.6792,\ 0.7064,\ 0.7320)$.

Step 3 — output pre-activations $o_k = \sum_j v_{jk} h_j + c_k$:

• $o_1 = 0.13(0.7668) + 0.15(0.6792) + 0.17(0.7064) + 0.19(0.7320) + 0.25 = 0.7107$
• $o_2 = 0.14(0.7668) + 0.16(0.6792) + 0.18(0.7064) + 0.20(0.7320) + 0.26 = 0.7496$

Step 4 — output activations $y_k = \sigma(o_k)$:

• $y_1 = \sigma(0.7107) = 0.6704$
• $y_2 = \sigma(0.7496) = 0.6790$

$$\boxed{\;\mathbf{y} = (0.6704,\ 0.6790)\;}$$

(c) Overview of Machine Learning Techniques

---

Question 8 — Robotics

(a) [4] Define a "Robot". What are the basic characteristics of a robot?

(b) [3] Write down the laws of robotics published in Runaround by Isaac Asimov.

(c) [7] Briefly explain the basic components of a robot.

Concept Needed

Robot definition, Asimov's three laws, robot subsystem decomposition.

(a) Definition and Characteristics of a Robot

(b) Asimov's Three Laws of Robotics

First formulated in Asimov's 1942 short story Runaround; later collected in I, Robot (1950).

1. First Law. A robot may not injure a human being or, through inaction, allow a human being to come to harm.

2. Second Law. A robot must obey the orders given to it by human beings, except where such orders would conflict with the First Law.

3. Third Law. A robot must protect its own existence, as long as such protection does not conflict with the First or Second Law.

(Later, the Zeroth Law was added: "A robot may not harm humanity, or through inaction allow humanity to come to harm.")

(c) Basic Components of a Robot

End-effectors / tools (gripper, welding torch, drill, paint nozzle, surgical instrument, etc.) are sometimes listed separately or as part of the mechanical structure; they are task-specific and easily swapped.

---

Interview Corner