Microprocessor and Interfacing (IT-503 (B)) Unit 5 Notes

UNIT 5: THEORY OF COMPUTATION & OBJECT-ORIENTED ANALYSIS AND DESIGN

⚠️ CRITICAL NOTE: The provided historical questions belong to Theory of Computation and Object-Oriented Analysis and Design (OOAD), NOT to a standard "Microprocessor and Interfacing" syllabus. These notes are generated solely from the given past paper context for exam preparation.

I. THEORY OF COMPUTATION (Automata & Formal Languages)

A. Finite Automata (FA) & Regular Expressions

1. Conversion: DFA ↔ Regular Expression

Arden's Theorem: Used to solve state equations for regular expressions. For a state q, if q = q·R + S, then q = S·R*.
- Steps: Write equations for each state (excluding start/accepting as needed), solve using Arden's.
State Elimination Method:
1. Add a new start state with ε-transition to old start.
2. Add a new final state with ε-transitions from old finals.
3. Eliminate states one by one (except new start/final), updating edge labels with regex.
4. Final regex is the label on the direct edge from new start to new final.
\[!TIP\] Eliminate states in order of connectivity; handle self-loops correctly (e.g., R becomes R*).

2. DFA Design with Overlap (e.g., "1100")

Key Concept: Overlap means the suffix of a string can be a prefix of the pattern.
Design Steps:
1. Build states for each prefix of the pattern: "", "1", "11", "110", "1100" (accept).
2. On failure, use the longest prefix that is also a suffix of the current string.
3. For "1100": failure from "11" on 0 goes to "110", not start. From "110" on 1 goes to "1" (overlap).
\[!TIP\] Always draw the transition table first, then the state diagram. Test with strings like "11001100".

3. NFA Design for Constraints (e.g., Divisible by 4)

Alphabet Σ = {0,1,2} (base-3 digits). Decimal equivalent divisible by 4.
Method: States represent remainder mod 4 (0,1,2,3). Start at 0 (empty string = 0).
- Transition: From state r on digit d, go to state (3*r + d) mod 4.
- Accept state: 0.
- NFA vs DFA: This construction yields a DFA. For an NFA, you can have ε-transitions or multiple transitions for same symbol.
\[!TIP\] For "divisible by k", always use k states representing remainders 0 to k-1.

4. NFA to Equivalent DFA (Subset Construction)

Algorithm:
1. DFA start state = ε-closure(NFA start state).
2. For each DFA state S (set of NFA states) and symbol a:
  - T = ∪ { move(s, a) for all s in S }
  - DFA_state = ε-closure(T)
3. DFA accept state if it contains any NFA accept state.
Key: DFA states are subsets of NFA states. Maximum 2^n states for n NFA states.

\[!TIP\] Always compute ε-closure first. Draw the DFA transition table clearly.

B. Regular Grammars & Languages

1. Constructing Regular Grammars

Language: Strings over {a,b} with at most one 'a' and more than two 'b's.
Right-Linear Grammar (RLG):
- S → B | A
- A → aB | a (handles the single 'a' followed by b's)
- B → bB | bbb (ensures at least 3 b's, but bbb is terminal; better: B → bB | b and enforce length via structure)
- Correction: Need to generate b^+ with at least 3 b's. Use:
  - S → X | Y
  - X → bX | bbb (strings with no 'a', ≥3 b's)
  - Y → aZ
  - Z → bZ | bbb (strings with one 'a' followed by ≥3 b's)
\[!TIP\] Regular grammars are either right-linear (A→aB|a) or left-linear. Ensure no mixing.

2. Identifying Language from Grammar

Given: G = ({S,A,B}, {a,b}, P, S)
- S → AaA
- A → aA | a
- B → bBb | bb
Analysis:
- A generates a^+ (one or more a).
- B generates b^{2n} (even number ≥2 of b).
- S forces structure: (a^+) a (a^+) = a^m a a^n = a^{m+n+1}. No b appears in S productions.
Language: L(G) = { a^k | k ≥ 2 } (since m,n ≥ 1, min k=1+1+1=3? Wait: A→a gives a, so S→ a a a = aaa. Actually A can be a, so S→ a a a = a^3. But A→aA→aa gives S→ aa a aa = a^4. So k ≥ 3? Let's compute min: A→a (1 a), so S→ (a) a (a) = a^3. Yes, L = {a^k | k ≥ 3}.

\[!TIP\] Check if non-terminals from different parts interact. Here B is unreachable from S, so ignored.

C. Context-Free Grammars (CFG) & Languages

1. CFG for Dependent Counts: aⁿbᵐcᵐd²ⁿ

Strategy: Generate a and d in pairs (a with dd), and b with c independently.
Grammar:
```
S → a S d d | T

T → b T c | ε
```
- S generates a^n (dd)^n = a^n d^{2n}.
- T generates b^m c^m.
- Combined: a^n (b^m c^m) d^{2n}.
Verification: For n=2,m=1: S→ aSdd→ aTdd→ abTcdd→ abcdd. Correct.

2. Ambiguity in CFG

Given Ambiguous Grammar:


S → Ab | aaB

A → a | Aa

B → b

i) String with Two Leftmost Derivations:
- String s = "aab".
- Derivation 1: S → aaB → aab
- Derivation 2: S → Ab → aAb → aaB → aab (Wait, A→a gives a, so Ab→ab, not aab. Let's find correct string.)
- Actually, A generates a^+. So Ab generates a^+b. aaB generates aab. Overlap at aab? Ab with A→a gives ab. A→Aa→aa gives aab. Yes:
  - S → Ab → Aa b? No, Ab means A then b. A→a gives ab. A→Aa→aa gives aab.
  - S → aaB → aab.
  - So s="aab" has two leftmost derivations:
    1. S ⇒ aaB ⇒ aab
    2. S ⇒ Ab ⇒ Aa b? Wait, A→a gives ab. To get aab, need A→Aa→aa. So:
      
      S ⇒ Ab ⇒ Aa b? Actually Ab is one symbol A then b. After A→Aa, we have Aab. Then A→a gives aab. Yes.
      
      S ⇒ Ab ⇒ Aab ⇒ aab.
- Correct derivations for "aab":
  - S → aaB → aab
  - S → Ab → Aab → aab (with A→a in second step).
ii) Derivation Trees:
- Tree 1: Root S with children a, a, B; B→b.
- Tree 2: Root S with children A, b; A has children a (from A→a) and b? Wait, A→a gives terminal a. So tree: S→A and b; A→a. That yields ab. To get aab, need A→Aa. So:
  - S→A (first child), b (second).
  - A→A (left), a (right).
  - Left A→a.
  - So leaves: a (from leftmost A), a (from A→a), b. Order: a a b.
iii) Equivalent Unambiguous CFG:
- Problem: S can produce a^+b via Ab or aaB. Overlap at aab.
- Fix: Make Ab generate only ab? But A generates a^+. So restrict A to single a.
- Unambiguous Grammar:
```
S → a A b | a a B

A → a A | ε   (generates a*)

B → b
```
  But then S→ a A b with A→ε gives ab. S→ a a B gives aab. No overlap. But original language? Original: Ab gives a^+b (≥1 a), aaB gives aab. So union is {ab, aab, aaab, ...}? Actually Ab with A→a gives ab; A→aa gives aab; etc. So language is {a^+b}? But aaB is also aab. So language is a^+b? But aaB is subset of a^+b. So original language is a^+b? But aaB produces only aab, not aaab. Wait, A can generate any number of a, so Ab generates all a^+b. aaB generates only aab. So language is a^+b (since aab already in a^+b). So grammar is ambiguous for aab because two ways.
- Unambiguous: Just S → a S b | ab? That gives a^n b^{n+1}? No.
- Actually language is a^+b. Simple unambiguous: S → a S | a B; B→b. Or S → a^+ b via S → a S | a b.
- But original grammar also has aaB which is redundant. So unambiguous:
```
S → a S | a b
```
  Or more explicitly:
```
S → A b

A → a A | a
```
  That's unambiguous for a^+b.
- But the question asks for equivalent unambiguous grammar for the same language. Original language is a^+b? Check: Ab with A→a gives ab; A→aa gives aab; A→aaa gives aaab; etc. aaB gives aab (already covered). So yes, L = {a^+b}.
- So unambiguous: S → a S | a b (left-recursive) or S → A b; A → a A | a.
iv) Unique Leftmost Derivation & Tree for "aab" from unambiguous grammar:
- Using S → A b; A → a A | a:
  - S ⇒ A b ⇒ a A b ⇒ a a b (with A→a at second step).
- Tree: S with children A, b; A with children a, A; inner A→a.

D. Pushdown Automata (PDA)

1. NPDA for {w | w starts and ends with same symbol} over {0,1}

Idea: Push first symbol onto stack. For each subsequent symbol, push. When see a symbol that matches top of stack (possible end), non-deterministically guess it's the last symbol and pop to check if stack becomes empty at end.
Formal NPDA (M = (Q, Σ, Γ, δ, q0, Z0, F)):
- Q = {q0, q1, q2}
- Σ = {0,1}
- Γ = {0,1, Z0}
- q0 start, Z0 bottom.
- F = {q2} (accept by final state)
- Transitions:
  1. δ(q0, ε, Z0) = {(q1, Z0)} (move to q1 without reading)
  2. δ(q1, 0, Z0) = {(q1, 0Z0)} (push 0)
    
    δ(q1, 1, Z0) = {(q1, 1Z0)}
    
    δ(q1, 0, 0) = {(q1, 00)}
    
    δ(q1, 1, 0) = {(q1, 10)} etc. (push any symbol)
  3. Non-deterministic pop: δ(q1, 0, 0) = {(q2, ε)} (if see 0 and top is 0, pop and go to q2)
    
    δ(q1, 1, 1) = {(q2, ε)}
  4. In q2, consume rest: δ(q2, 0, 0) = {(q2, ε)}, δ(q2, 1, 1) = {(q2, ε)}, δ(q2, ε, Z0) = {(q2, Z0)}? Actually need to empty stack. Better: accept by empty stack? Or final state with empty stack? Usually for this language, accept by final state after popping to bottom.
- Simpler: Use accept by empty stack. Then:
  - Push first symbol.
  - Push others.
  - Non-deterministically, when top matches current symbol, pop.
  - Accept if stack empty at end.
- Standard NPDA:
```
δ(q0, ε, Z0) = {(q0, 0Z0), (q0, 1Z0), (q0, Z0)}  // guess first symbol or start popping?
```
  Actually better:
  - δ(q0, 0, Z0) = {(q1, 0Z0)}
  - δ(q0, 1, Z0) = {(q1, 1Z0)}
  - In q1: push on any symbol: δ(q1, a, b) = {(q1, ab)} for a,b∈{0,1}.
  - Non-deterministic pop: δ(q1, a, a) = {(q2, ε)} for a∈{0,1}.
  - In q2: pop matching: δ(q2, a, a) = {(q2, ε)} and δ(q2, ε, Z0) = {(q2, ε)}? Actually after popping to Z0, need to accept. So δ(q2, ε, Z0) = {(q_accept, ε)}.
\[!TIP\] For "starts and ends with same symbol", you must remember the first symbol on stack and match it at the end. Non-determinism is used to guess when the end begins.

2. DPDA for {aⁿbᵐ | m ≥ 2n+2}

Constraint: For every a, need at least 2 bs, plus extra 2 bs.
DPDA Strategy: While reading as, push a symbol (say A) per a. When first b seen, start popping one A per two bs. After all as popped, need at least 2 more bs.
Formal DPDA (accept by final state):
- Q = {q0, q1, q2, q3}
- Σ = {a,b}
- Γ = {A, Z0}
- q0 start, Z0 bottom.
- F = {q3}
- Transitions:
  1. δ(q0, a, Z0) = {(q0, AZ0)}
    
    δ(q0, a, A) = {(q0, AA)}
  2. On first b: δ(q0, b, A) = {(q1, A)} (don't pop yet, just change state to start counting)
    
    δ(q0, b, Z0) = {(q1, Z0)} (if no a's, n=0, need m≥2)
  3. In q1: read bs, pop every second b? Actually need to pop one A per two bs. So we need to count bs in pairs.
    - Use two states: q1 (after odd number of b's), q2 (after even).
    - δ(q1, b, A) = {(q2, A)} (read one b, stay on A)
    - δ(q1, b, Z0) = {(q2, Z0)} (no A left, just count)
    - δ(q2, b, A) = {(q1, A)} (read second b, pop A? Actually we want to pop on the second b. So modify:
      - In q1 (odd count), on b with A on top: don't pop, just move to q2.
      - In q2 (even count), on b with A on top: pop and stay in q2? Or move to q1? Let's design:
        
        q0: reading as, push A.
        
        On first b: go to q1.
        
        q1: read b, if A on top, pop and go to q2? But then we pop on first b? That would be one b per a. Need two b per a.
        
        Better: Use stack to count as. For each a, we need 2 bs. So we can push two symbols per a? Or push one and pop on every second b.
        
        Common method: Push A for each a. Then for each a, we need to see two bs. So we can pop one A for every two bs. So we need to count bs modulo 2.
        
        States: q0 (reading a's), q1 (reading b's, odd count), q2 (reading b's, even count).
        
        Transitions:
        
        δ(q0, a, Z0) = (q0, AZ0), δ(q0, a, A) = (q0, AA)
        
        δ(q0, b, A) = (q1, A) (first b after a's, odd count, don't pop yet)
        
        δ(q0, b, Z0) = (q1, Z0) (if no a's)
        
        δ(q1, b, A) = (q2, A) (second b, still don't pop? Actually we want to pop after two b's. So on second b, pop one A. So:
        
        δ(q1, b, A) = (q2, A)? That doesn't pop. We need to pop on the transition from q1 to q2 when seeing b with A. So:
        
        δ(q1, b, A) = (q2, ε) (pop A)
        
        But then after popping, we are in q2 with one less A. Then next b (third overall, first of next pair) should go to q1 without popping.
        
        So:
        
        δ(q1, b, A) = (q2, ε) // pop on second b of pair
        
        δ(q1, b, Z0) = (q2, Z0) // no A to pop, just change state
        
        δ(q2, b, A) = (q1, A) // first b of next pair, don't pop
        
        δ(q2, b, Z0) = (q1, Z0)
        
        After all as popped (stack has only Z0), we need at least 2 more bs. So from state where stack is Z0 (could be q1 or q2), read two bs and go to accept.
        
        Add:
        
        δ(q1, b, Z0) = (q3, Z0) (first extra b)
        
        δ(q3, b, Z0) = (q_accept, Z0) (second extra b)
        
        But also if we are in q2 with Z0: δ(q2, b, Z0) = (q3, Z0).
        
        Accept state: q_accept.
- Simpler: Push AA for each a? Then pop one A per b. But then need exactly 2n bs for as, plus 2 extra. So:
  - Push AA per a.
  - On b, pop A.
  - After all as popped, need 2 more bs.
  - But then stack has As only from as. Popping one per b gives m = n? Not 2n. So push two As per a? Then popping one per b gives m = 2n if we pop all. But we need m ≥ 2n+2. So after popping all As, need 2 more bs.
  - So:
    - δ(q0, a, Z0) = (q0, AAZ0), δ(q0, a, A) = (q0, AAA)? Actually if stack top is A, push two more? That would be A becomes AAA? Not correct.
    - Better: For each a, push two As. So initial: on a with Z0, push AAZ0. On a with A, push AA? That would double count. Actually we want to push exactly two As per a. So:
      - δ(q0, a, Z0) = (q0, AAZ0)
      - δ(q0, a, A) = (q0, AA)? But then stack becomes ...A AA, so total As increase by 2 per a. Correct.
    - Then on b: δ(q0, b, A) = (q1, ε) (start popping after a's? But we might still have a's? Actually we read all a's first? Language is a^n b^m, so all a's then b's. So we can assume a's then b's. So after last a, we are in q0 with stack having 2n As. Then on first b, go to q1 and start popping.
    - δ(q1, b, A) = (q1, ε) (pop one A per b)
    - When stack becomes Z0, we have popped 2n As, so read 2n bs. Need 2 more bs.
    - δ(q1, b, Z0) = (q2, Z0) (first extra b)
    - δ(q2, b, Z0) = (q_accept, Z0) (second extra b)
    - Also if n=0, stack starts with Z0. Then on first b from q0: δ(q0, b, Z0) = (q2, Z0)? But then need two b's. So:
      - δ(q0, b, Z0) = (q2, Z0) (first b)
      - δ(q2, b, Z0) = (q_accept, Z0) (second b)
    - But if n>0, after popping all As, we are in q1 with Z0. Then δ(q1, b, Z0) = (q2, Z0).
- This DPDA works because language is deterministic (prefix property).

3. Simulating CFG with NPDA (Standard Construction)

Given CFG G, construct NPDA M that accepts L(G) by empty stack.
Steps:
1. M starts with stack containing start symbol S of G.
2. For each production A → α in G, add transition: δ(q, ε, A) ⊃ (q, α) (push α).
3. For each terminal a in Σ, add: δ(q, a, a) ⊃ (q, ε) (pop matching terminal).
4. M accepts by empty stack.
Intuition: NPDA simulates leftmost derivation: at each step, either replace a non-terminal (push RHS) or match a terminal (pop).

4. Constructing CFG from NPDA

Reverse process: For each state transition in NPDA, create a production.
General method: For NPDA M = (Q, Σ, Γ, δ, q0, Z0, F), create CFG with variables A_{pq} for each pair of states p,q, representing strings that take M from state p with stack symbol X to state q with X popped? Actually standard construction is complex.
Simpler for given NPDA: Often the NPDA is designed from a CFG, so reverse is straightforward by reading transitions.
Example: If NPDA has δ(q, a, A) = (r, BC) and δ(r, ε, C) = (s, D), then productions: A_{qs} → a A_{rb} B_{?} etc. Not trivial.
For exam: Usually given NPDA is simple, with transitions that directly correspond to productions. Look for:
- δ(q, ε, A) = (r, BC) → A → BC
- δ(q, a, a) = (r, ε) → A → a if A is terminal.
- δ(q, ε, A) = (r, ε) → A → ε
- Also need to handle stack symbols as variables.

E. Turing Machines (TM) & Undecidability

1. TM for L = {0ⁿ1²ⁿ2ⁿ | n ≥ 0}

Strategy: Match each 0 with two 1s and one 2. Use tape marks (e.g., X for matched 0, Y for matched 1, Z for matched 2).
High-Level Algorithm:
1. If first symbol is X (all matched), check rest blank → accept.
2. Find first 0, change to X.
3. Find first 1 to the right, change to Y.
4. Find next 1, change to Y (so two 1s per 0).
5. Find first 2, change to Z.
6. Go back to beginning (leftmost) and repeat.
7. If at step 3 or 4 or 5 no symbol found → reject.
State Diagram Sketch:
- q0: start, if X go to q_accept, else if 0 → q1 (mark 0 as X and go right).
- q1: move right to first 1, mark Y, go to q2.
- q2: move right to next 1, mark Y, go to q3.
- q3: move right to first 2, mark Z, go to q4.
- q4: move left to beginning (to X or start), go to q0.
Reject states: If in q1 no 1, reject; in q2 no second 1, reject; in q3 no 2, reject.

2. Undecidability: Halting Problem (Existence of Accepting Input)

Problem: Given a TM M, does there exist any input string w such that M accepts w?
Proof by Reduction from Acceptance Problem (A_TM):
- A_TM: Given <M, w>, does M accept w? (Undecidable)
- Construction: Given <M, w>, construct a new TM M' such that:
  - M' on any input x: ignores x, simulates M on w.
  - If M accepts w, then M' accepts all x (so exists accepting input).
  - If M does not accept w (rejects or loops), then M' rejects all x (no accepting input).
- Then: <M, w> ∈ A_TM iff <M'> has an accepting input.
- If we could decide the "existence" problem, we could decide A_TM. Contradiction. Hence undecidable.
\[!TIP\] Key is to reduce from a known undecidable problem. Here we transform an instance of A_TM into an instance of the "existence" problem.

3. Closure Properties: Recursive Languages

Recursive (Decidable) Languages are closed under:
- Union: Given deciders M1, M2 for L1, L2, construct M that on input w runs M1 and M2 in parallel (dovetailing). Accept if either accepts. Since both halt, M halts.
- Intersection: Run M1 and M2 in parallel; accept if both accept.
- Complement: Given decider M for L, construct M' that does exactly opposite: accept if M rejects, reject if M accepts. Since M always halts, M' always halts.
Proof Sketch: Use the fact that recursive languages have total computable characteristic functions.

\[!TIP\] Recursively Enumerable (RE) languages are closed under union and intersection, but NOT under complement. Recursive languages are closed under all three because they are decidable.

II. OBJECT-ORIENTED ANALYSIS AND DESIGN (OOAD)

A. Fundamentals of Modeling & OO Approach

1. What is a Model? Purposes of Modeling

Model: Abstraction of a system, capturing essential aspects while hiding unnecessary details.
Purposes:
1. Visualization: Provide common visual vocabulary.
2. Complexity Management: Divide system into manageable pieces.
3. Communication: Facilitate stakeholder understanding.
4. Specification: Define system structure/behavior precisely.
5. Documentation: Record design decisions.
6. Analysis: Check consistency, completeness, feasibility.
7. Implementation Guidance: Blueprint for coding.
8. Maintenance: Understand existing system.

2. Object-Oriented Approach: Four Aspects

Object: Runtime entity with state (attributes) and behavior (operations). Instances of classes.
Class: Blueprint/template for objects. Defines attributes and operations.
Inheritance: Mechanism for defining new classes (subclasses) from existing ones (superclasses), promoting reuse.
Polymorphism: Ability of different classes to respond to same message (operation call) in different ways (e.g., overriding, overloading).

3. Role of UML & Types of Models

UML (Unified Modeling Language): Standard graphical language for visualizing, specifying, constructing, documenting software artifacts.
Model Types:
- Structural Models: Static aspects (classes, objects, components, deployment). Diagrams: Class, Object, Component, Deployment.
- Behavioral Models: Dynamic aspects (interactions, state changes). Diagrams: Sequence, Collaboration, Activity, State Machine.
- Architectural Models: High-level organization (components, nodes). Diagrams: Component, Deployment.

B. Use Case Modeling

1. Identifying Actors & Use Cases

Actor: Role played by a user or external system interacting with the system.
- Types: Primary (initiates use case), Secondary (participates), Active (operates system), Passive (receives).
Use Case: Discrete piece of functionality that delivers value to an actor. Describes a sequence of actions.
Identification: From problem statement, list all external entities (people, systems) → actors. For each actor, list their goals → use cases.

2. Use Case Diagram Notation

Elements:
- System Boundary: Box around use cases.
- Actors: Stick figures outside box.
- Use Cases: Ovals inside box.
- Associations: Lines connecting actors to use cases.
- Relationships:
  - Include: Dashed arrow with <<include>> from base to common subfunction (mandatory).
  - Extend: Dashed arrow with <<extend>> from extension to base (optional, conditional).
  - Generalization: Solid line with hollow arrowhead (actor or use case inheritance).
Example: Online Shopping
- Actors: Customer, Seller, Payment Gateway, Shipping Service.
- Use Cases: Browse Catalog, Add to Cart, Checkout, Process Payment, Ship Order, Track Order.
- Relationships: Checkout includes Process Payment; Track Order extends Ship Order (optional).

C. Domain Modeling & Class Identification

1. Identifying Classes (Noun Identification)

Step 1: Extract nouns/noun phrases from problem statement.
Step 2: Filter out:
- Implementation classes: (e.g., Array, Database).
- Redundant/Similar classes: (e.g., Book and Publication if same).
- Outside scope: (e.g., Customer if system is internal).
- Attributes: (e.g., name, price should be attributes, not classes).
- Roles: (e.g., manager might be a role of Employee).
Step 3: Use CRC (Class-Responsibility-Collaboration) cards to refine.

2. Identifying Associations

Source: Verbs/verb phrases linking classes.
Multiplicity: Specify cardinality (1, 0..1, 1..*, *, etc.).
Example: Library System:
- Library has Books → Association Library—Book with multiplicity 1 (library) to * (books).
- Member borrows Book → Association Member—Book with * to * (but typically 0..* to 0..* with dates).
- Book written by Author → * to * (many-to-many).

3. Identifying Super-Subclass (Generalization)

Basis: "is-a" relationship or shared attributes/operations.
Example: Vehicle superclass, Car, Bike subclasses.
Check: Subclass should have all attributes/operations of superclass plus more specific ones.
Avoid: Deep inheritance hierarchies (>2 levels) if not necessary.

4. Focus on Data Type Attributes in Domain Model

Domain Model: Conceptual view, not implementation.
Attribute Types:
- Primitive: int, string, date.
- Data Type: Composite value objects (e.g., Address with street, city, zip; Money with amount, currency).
- Why focus on Data Types? They encapsulate related primitive attributes, reduce clutter, and model real-world concepts accurately.
- Example: Instead of customer.street, customer.city, customer.zip as separate attributes, define Address as a data type attribute of Customer.

D. Interaction & Behavioral Diagrams

1. Sequence Diagrams

Purpose: Show interactions between objects over time (temporal ordering).
Notation:
- Lifeline: Vertical dashed line (object/class rectangle at top).
- Activation Bar: Thin rectangle on lifeline during operation execution.
- Messages: Horizontal arrows between lifelines.
  - Synchronous: Solid line with filled arrowhead (caller waits).
  - Asynchronous: Solid line with open arrowhead (caller continues).
  - Return: Dashed line with open arrowhead.
- Self-call: Message to same lifeline.
Construction for Scenario (Library: Issue Book):
1. Actor Member → Librarian (interface): issueBook(bookId, memberId)
2. Librarian → BookCatalog: findBook(bookId) (synchronous)
3. BookCatalog → Librarian: return Book object.
4. Librarian → MemberRecord: findMember(memberId)
5. MemberRecord → Librarian: return Member.
6. Librarian → Book: setStatus(borrowed)
7. Librarian → LoanRecord: createLoan(...)
8. Librarian → Member: displayDueDate(...)

2. Collaboration Diagrams (Communication Diagrams)

Purpose: Show structural organization of objects and their links; messages are numbered for sequence.
Similarities to Sequence:
- Both model interactions.
- Both show objects/messages.
Dissimilarities:

| Sequence Diagram | Collaboration Diagram | |----------------------|--------------------------| | Emphasizes time ordering (vertical axis). | Emphasizes structural links (network). | | Easy to see sequence of messages. | Easy to see which objects are connected. | | Can become wide with many objects. | Can become cluttered with many messages. | | Messages shown as horizontal arrows. | Messages shown as numbered links near links. |
Conversion: Sequence → Collaboration: note message numbers and links. Collaboration → Sequence: order by numbers.

3. Activity Diagrams

Purpose: Model workflow/business process or algorithm logic.
When NOT to use:
- For detailed object interactions (use Sequence/Collaboration).
- When the flow is primarily sequential and simple (use flowchart).
- For real-time or event-driven systems (use State Machine).
Preferable Alternatives:
- Complex object interactions: Sequence/Collaboration.
- State-dependent behavior: State Machine diagram.
- Use case logic: Activity diagram is good for "what happens" in a use case.
Practical Situations:
- Use Activity: Business process modeling, algorithm steps, parallel activities.
- Use Sequence: Detailed scenario of message passing between objects.
- Use Object Diagram: Snapshot of objects at a point in time (rarely used).

E. Advanced UML Diagrams & Architectural Modeling

1. UML Diagram Notations Overview (14 Diagrams)

Structural (7): Class, Object, Component, Composite Structure, Deployment, Package, Profile.
Behavioral (7): Use Case, Activity, State Machine, Sequence, Collaboration, Timing, Interaction Overview.
Key Purposes:
- Class: Static structure (attributes, operations, relationships).
- Component: Physical replaceable parts (libraries, executables).
- Deployment: Physical nodes and artifacts.
- Sequence: Time-ordered interactions.
- State Machine: State transitions of an object.

2. Component Diagrams

Purpose: Show organization and dependencies among software components (physical, replaceable parts).
Component Models:
- CORBA (Common Object Request Broker Architecture):
  - Standard by OMG for distributed objects.
  - Uses ORB (Object Request Broker) as middleware.
  - Components are objects with interfaces defined in IDL (Interface Definition Language).
  - Language-independent, platform-independent.
- COM/DCOM (Component Object Model / Distributed COM):
  - Microsoft's binary standard for component interaction.
  - COM: For same machine; components expose interfaces via IUnknown.
  - DCOM: Extension for distributed systems (network).
  - Uses Registry for component location.
  - Language-independent (within Windows).

3. Deployment Diagrams

Purpose: Model physical architecture: nodes (hardware/software), artifacts (files, executables), and connections.
Elements:
- Node: <<device>> (hardware) or <<executionEnvironment>> (software like OS).
- Artifact: Rectangle with <<artifact>> and name (e.g., main.exe, config.xml).
- Deployment: Connect node to artifact (manifestation).
- Communication Path: Line between nodes (protocol: <<TCP/IP>>).
Example: Banking Application
- Nodes: Client PC, Application Server, Database Server.
- Artifacts: BankApp.jar on App Server, Oracle DB on DB Server.
- Paths: Client PC --(HTTP)--> Application Server; Application Server --(JDBC)--> Database Server.

F. User Interface (UI) Design

1. Designing UI for ATM Banking System

Key Screens & Interactions:
1. Card Insertion Screen: Prompt "Insert Card". Validates card.
2. PIN Entry Screen: Numeric keypad, hide digits, 3 attempts.
3. Main Menu: Options: Withdrawal, Deposit, Balance Inquiry, Transfer, Exit.
4. Account Selection: If multiple accounts, choose.
5. Withdrawal Screen: Enter amount, select account, confirm, dispense cash, print receipt.
6. Deposit Screen: Insert envelope/checks, confirm amount.
7. Balance Inquiry: Display balance, option to print.
8. Transfer Screen: Select from/to accounts, enter amount.
9. Receipt Screen: Option to print, return card.
Design Principles:
- Simplicity: Few steps per transaction.
- Error Handling: Clear messages (e.g., "Insufficient funds", "Invalid PIN").
- Security: Hide PIN, timeout after inactivity, card retention after 3 wrong PINs.
- Accessibility: Large buttons, audio jack for visually impaired.
Relation to Use Cases: Each screen corresponds to a use case or sub-use case (e.g., Withdraw Cash use case includes Enter Amount, Confirm steps).

\boxed{\text{These notes cover all topics from the provided past exam questions for Unit 5.}}