UNIT 3: THEORY OF COMPUTATION & OBJECT-ORIENTED ANALYSIS & DESIGN

A. THEORY OF COMPUTATION

1. Finite Automata & Regular Languages

Regular Expressions & DFA Equivalence

• Regular Expression (RE): Algebraic notation to describe regular languages. Built using union (+), concatenation, and Kleene star (*).

• State Elimination Method (DFA → RE):

  1. Ensure DFA has a single start and accept state (add new if needed).

  2. Eliminate states one by one, updating edge labels with REs.

  3. Final RE is label on direct edge from new start to new accept.

• Thompson’s Construction (RE → ε-NFA):

  • Base: For symbol a, create S →a→ F.

  • For r+s, create new start with ε to two sub-NFAs, their accepts ε to new final.

  • For r·s, connect accept of first to start of second with ε.

  • For r*, add ε loops from new start to sub-NFA and from its accept back to its start.

• Equivalence: RE, DFA, NFA, and Regular Grammars all describe the same class of languages (Regular Languages).

[!TIP]

Exam Focus: State elimination is error-prone. Always label multiple edges between states as union of REs. For Thompson’s, remember ε-transitions are key.

DFA Design for Sequence Detection

• Without Overlap: Once pattern found, reset to start state.

  • Example: For "1100", states track longest prefix matched. After accept, go to state 0.

• With Overlap: Suffix of pattern may be prefix of pattern.

  • Method: Build DFA where each state = length of longest prefix of pattern that is suffix of input so far.

  • Example for "1100" over {0,1}:

    • States: S0 (no match), S1 ("1"), S2 ("11"), S3 ("110"), S4 ("1100" – accept).

    • Transitions from S4 on '0' go to S3 (overlap: "110" is suffix of "1100").

    • Result: 5 states. Accept state loops on '0' to S3, on '1' to S1.

NFA Design

• ε-NFA: Transitions without input symbol (ε-moves).

• Design for Divisibility (e.g., decimal equivalent divisible by 4 over Σ={0,1,2}):

  • States represent remainder modulo 4: q0 (0), q1 (1), q2 (2), q3 (3).

  • Start state q0 (empty string = 0).

  • Transition: δ(q_i, a) = q_j where j = (10·i + a) mod 4.

  • Accept state: q0.

• ε-elimination: Compute ε-closure for each state. New transitions from p to r on symbol a if ∃ q in ε-closure(p) with δ(q,a)=s and r in ε-closure(s).

Conversion Between Automata

• Subset Construction (NFA → DFA):

  • DFA state = set of NFA states.

  • Start state = ε-closure(NFA start).

  • δ_DFA(S, a) = ∪_{q∈S} ε-closure(δ_NFA(q, a)).

• DFA Minimization (Table-filling / Partitioning):

  1. Mark distinguishable pairs (one accepting, one not).

  2. Iteratively mark pairs if ∃ a such that δ(p,a) and δ(q,a) are already marked.

  3. Unmarked pairs are equivalent; merge them.

Regular Grammars

• Right-Linear: A → aB | a | ε (production has at most one non-terminal, at right end).

• Left-Linear: A → Ba | a | ε (non-terminal at left end).

• Example: L = {w over {a,b} | at most one 'a', more than two 'b's}.

  • Right-linear grammar:

    
    S → bS | A | bbb
    
    A → a | aB
    
    B → bB | b
    
    

  • Generates: strings with 0 'a' (≥3 b's) or 1 'a' (any b's).

2. Context-Free Languages & Pushdown Automata

Context-Free Grammars (CFG)

• Components: G = (V, Σ, P, S) where V = non-terminals, Σ = terminals, P = productions, S = start.

• Design for Nested Dependencies (e.g., L = {a^n b^m c^m d^{2n}}):

  
  S → a S d d | T
  
  T → b T c | ε
  
  

  • S handles a...d with 2:1 ratio, T handles equal b and c.

• Useless Symbol Removal:

  1. Remove non-generating symbols (cannot derive terminal string).

  2. Remove non-reachable symbols (not reachable from start).

• ε-Production Removal (if ε ∉ L):

  • Find nullable non-terminals (can derive ε).

  • For each A → α, add productions A → β for all β obtained by removing one or more nullable symbols from α.

  • Remove ε-productions (except possibly S → ε if ε ∈ L).

• Unit Production Removal (A → B):

  • For each A → B, add A → γ for all B → γ (γ not single non-terminal).

  • Remove A → B.

Ambiguity in CFG

• Definition: CFG is ambiguous if some string has >1 leftmost or >1 rightmost derivation (or >1 parse tree).

• Example Grammar:

  
  S → Ab | aaB
  
  A → a | Aa
  
  B → b
  
  

  • String aab has two leftmost derivations:

    1. S → Ab → aAb → aaB → aab

    2. S → aaB → aAb → aaB → aab

• Conversion to Unambiguous:

  • Introduce new non-terminals to enforce order.

  • Unambiguous grammar for above:

    
    S → aA | aB
    
    A → aA | a
    
    B → b
    
    

  • Now aab derives uniquely: S → aA → aA → aB → aab? Wait, check: Actually S→aB gives ab, not aab. Correction:

    
    S → aS | A
    
    A → aB
    
    B → b
    
    

    Better: For language {a^n b | n≥1} ∪ {a^n b | n≥2}? Original L = {a^+ b}? Actually original ambiguous grammar generates {a^+ b}. Unambiguous:

    
    S → aS | aB
    
    B → b
    
    

    Generates same, unique leftmost: S→aS→aB→ab for n=2? For aab: S→aS→aB→ab? That's ab. Need aab: S→aS→aS→aB→aab. Yes unique.

Pushdown Automata (PDA)

• Definition: PDA = (Q, Σ, Γ, δ, q0, Z0, F) where Γ = stack alphabet, Z0 = initial stack symbol.

• NPDA for w starts and ends with same symbol (Σ={0,1}):

  • Non-deterministically guess middle.

  • Push first symbol, then for each subsequent symbol, push its opposite? Actually:

    
    States: q0 (start), q1 (pushing), q2 (popping), q_accept
    
    Stack: initially Z0.
    
    δ:
    
      (q0, ε, Z0) → (q1, Z0)  // stay in q0? Better:
    
      (q0, a, Z0) → (q1, a Z0) for a∈{0,1}  // push first symbol
    
      (q1, b, a) → (q1, b a) for b∈{0,1}  // push until guess middle
    
      (q1, ε, a) → (q2, ε)  // non-deterministically pop matching a
    
      (q2, b, b) → (q2, ε)  // pop matching
    
      (q2, ε, Z0) → (q_accept, Z0)
    
    

  • Accept by empty stack or final state.

• Deterministic PDA (DPDA):

  • At most one transition for (state, input, stack-top).

  • No ε-moves if input symbol available.

  • Example: L = {a^n b^m | m ≥ 2n+2}.

    
    States: q0, q1, q2, q3
    
    Start: q0, stack Z0.
    
    δ:
    
      (q0, a, Z0) → (q1, A Z0)  // push A for each a, count n
    
      (q1, a, A) → (q1, A A)   // push another A
    
      (q1, b, A) → (q2, ε)     // start popping, need 2 per A? Actually m≥2n+2.
    
      Better: Use two phases.
    
      q0: read a's, push A.
    
      q1: after first b, pop one A, go to q2.
    
      q2: for each remaining A, need two b's? Actually m ≥ 2n+2 means after n a's, need at least 2n+2 b's.
    
      Design: 
    
        q0: on a, push A; on b (first b), go to q1, pop A, push B (mark start of b's).
    
        q1: on b, pop A if exists, else stay? Complex.
    
      Standard: Use stack to count n, then require 2n+2 b's.
    
      Alternative: 
    
        δ(q0, a, Z0) = (q0, A Z0)
    
        δ(q0, a, A) = (q0, A A)
    
        δ(q0, b, A) = (q1, A)  // first b, don't pop yet? Actually we need to ensure 2n+2.
    
        Better: 
    
        q0: read a's, push A.
    
        q1: on first b, go to q2, push X (special).
    
        q2: on b, if stack top A, pop A and push two B's? Not possible.
    
      Actually DPDA for m≥2n+2 is tricky. Often done by:
    
        - Push A for each a.
    
        - Then for each a, need two b's: so pop A and push BB.
    
        - Then need two extra b's: so after all A's popped, need two b's.
    
      States:
    
        q0: read a, push A.
    
        q1: on first b, go to q2, push B (extra b counter).
    
        q2: on b, if top A, pop A and push BB (so each A gives two b's).
    
              if top B, pop B (for extra b).
    
        Accept when stack empty (Z0) and input done.
    
    

• CFG → NPDA (Standard Construction):

  • PDA simulates leftmost derivation.

  • Stack starts with start symbol S.

  • At each step, if top is terminal, match and pop; if non-terminal A, non-deterministically choose production A → α and replace A with α (push α in reverse).

• NPDA → CFG:

  • For each pair of states p,q, create variable [p q] generating strings taking PDA from p to q with stack unchanged except initial symbol.

  • Productions based on transitions.

3. Turing Machines & Computability

Turing Machine (TM) Design

• Components: (Q, Σ, Γ, δ, q0, B, F) where Γ = tape alphabet (Σ ⊂ Γ), B = blank.

• For L = {0^n 1^{2n} 2^n}:

  • Idea: Match each 0 with two 1's and one 2.

  • Algorithm:

    1. Scan right to find first 0, mark it (e.g., X), then find first 1, mark it (Y), then find next 1, mark it (Y), then find first 2, mark it (Z).

    2. Repeat until all 0's marked.

    3. Accept if all 0's, 1's, 2's marked and in order.

  • States: q0 (start), q1 (find 0), q2 (find first 1), q3 (find second 1), q4 (find 2), q5 (return left), q_accept, q_reject.

  • Transitions (partial):

    • δ(q0, 0) = (q1, X, R) // mark first 0

    • δ(q1, 1) = (q2, Y, R) // first 1

    • δ(q2, 1) = (q3, Y, R) // second 1

    • δ(q3, 2) = (q4, Z, R) // corresponding 2

    • δ(q4, 0) = (q1, X, R) // next 0

    • δ(q4, Y) = (q4, Y, R) // skip marked 1's

    • δ(q4, Z) = (q4, Z, R) // skip marked 2's

    • δ(q4, B) = (q5, B, L) // end of tape, go back

    • δ(q5, X) = (q5, X, L) // move left to start

    • δ(q5, Y) = (q5, Y, L)

    • δ(q5, Z) = (q5, Z, L)

    • δ(q5, 0) = (q0, 0, R) // restart

    • Accept if all symbols marked: in q0, if read B after X's, Y's, Z's? Actually after marking all, we have X...Y...Z... then B. So δ(q0, B) = accept if stack? No stack. Check: after last mark, in q4 read B, go q5, move left to first symbol. If first symbol is X and next is Y etc. But simpler: after marking all, we have no 0,1,2 left. So in q0, if read X, Y, Z, skip; if read B, accept.

    • Actually: after all marked, tape looks like X...Y...Z...B. So from q0, if see X, move right; if see B, accept.

    • Need to ensure order: X's then Y's then Z's.

    • In q0, if see 0 → reject (unmarked 0 left).

    • If see X, move right; if see Y, move right; if see Z, move right; if see B, accept.

    • So add state q_check:

      δ(q5, X) = (q_check, X, R)

      δ(q_check, Y) = (q_check, Y, R)

      δ(q_check, Z) = (q_check, Z, R)

      δ(q_check, B) = (q_accept, B, R)

      δ(q_check, 0) = (q_reject, 0, R) // unmarked 0

      δ(q_check, 1) = (q_reject, 1, R) // unmarked 1

      δ(q_check, 2) = (q_reject, 2, R) // unmarked 2

Undecidability & Reducibility

• Halting Problem: H = {⟨M,w⟩ | M halts on w} is undecidable.

• Proof by Reduction: Assume H decidable, use it to decide A_TM = {⟨M,w⟩ | M accepts w} (known undecidable).

  • Construct TM R that on ⟨M,w⟩:

    1. Simulate M on w.

    2. If M accepts, accept; if M rejects, loop.

    • Then ⟨M,w⟩ ∈ A_TM iff R halts on ⟨M,w⟩.

    • So if H decidable, A_TM decidable → contradiction.

• Rice’s Theorem: Any non-trivial property of RE languages is undecidable.

  • Non-trivial: not all RE languages have it, and some RE language has it.

  • Example: "L(M) is finite", "L(M) contains a palindrome" → undecidable.

• Reduction: To prove problem X undecidable, reduce known undecidable Y to X: construct computable f such that ⟨M⟩ ∈ Y iff f(⟨M⟩) ∈ X.

Closure Properties

• Recursive Languages (decidable): Closed under union, intersection, complement, concatenation, Kleene star.

  • Proof for complement: Decider for L, just swap accept/reject.

• Recursively Enumerable Languages (semi-decidable): Closed under union, intersection, concatenation, Kleene star. Not closed under complement.

  • Counterexample: A_TM is RE but its complement is not RE.

[!TIP]

Common Pitfall: Confusing "recursive" (decidable) with "RE". RE includes recursive but also undecidable languages like A_TM. Complement of RE may not be RE.

B. OBJECT-ORIENTED ANALYSIS & DESIGN (OOAD)

1. Modeling Fundamentals & Object-Oriented Concepts

Purpose of Modeling

• Why Model?

  • Manage complexity of real systems.

  • Communicate ideas among stakeholders.

  • Document decisions for maintenance.

  • Enable analysis before implementation (reduce risk).

• Types of Models:

  | Model Type | Purpose | Example | |------------|---------|---------| | Conceptual | Understand domain, independent of implementation | Domain model with classes/associations | | Specification | Describe functionality, interface, behavior | Use case diagrams, sequence diagrams | | Implementation | Guide code construction | Class diagrams with attributes/methods, component diagrams |

Object-Oriented Paradigm

• Four Aspects:

  1. Objects: Instances with state (attributes) and behavior (operations).

  2. Classes: Blueprints for objects (define attributes/methods).

  3. Inheritance: Mechanism for specialization (superclass → subclass).

  4. Polymorphism: Ability of different classes to respond to same message (method overriding/overloading).

• Object-Oriented vs. Object-Based:

  • OO: Supports all four aspects (inheritance + polymorphism).

  • Object-Based: Supports objects/classes but not inheritance/polymorphism (e.g., Ada, some modules).

Domain Modeling

• Goal: Identify conceptual classes (real-world entities) and their relationships.

• Identifying Attributes & Operations:

  • Attributes: Focus on data type attributes (domain-specific, not primitive).

    • Good: AccountNumber (type: String, format: 10 digits), Date (type: Date).

    • Avoid: accountId as int (too primitive), name as String (ok but consider PersonName class if complex).

  • Operations: Only those essential to domain (e.g., deposit(amount) for Account, not printReceipt() – that’s UI).

• Criteria for Class:

  • Has meaningful attributes/operations.

  • Represents a thing (noun) with distinct identity.

  • Not just a role (e.g., "Customer" is class, "buyer" might be role).

2. UML Diagrams & Notations

Use Case Diagrams

• Purpose: Capture functional requirements; show system’s external interactions.

• Elements:

  • Actor: Role played by user/ external system (stick figure).

  • Use Case: Oval representing functionality (e.g., "Withdraw Cash").

  • System Boundary: Box around use cases.

• Relationships:

  • Association: Actor uses use case (solid line).

  • Include: Mandatory subfunction (dashed arrow with <<include>>).

  • Extend: Optional/conditional behavior (dashed arrow with <<extend>>).

  • Generalization: Actor or use case specialization (solid line with hollow arrow).

• Example: Online Shopping:

  • Actors: Customer, Admin, Payment Gateway.

  • Use Cases: Browse Items, Place Order, Manage Inventory (Admin).

  • "Place Order" <<include>> "Make Payment".

  • "Place Order" <<extend>> "Apply Discount" (if coupon exists).

Interaction Diagrams

• Sequence Diagram:

  • Focus: Time ordering of messages between objects.

  • Lifelines: Vertical dashed lines for objects/participants.

  • Activation bars: Thin rectangles on lifeline showing operation execution.

  • Messages: Horizontal arrows (solid = synchronous, dashed = asynchronous).

  • Self-call: Arrow looping back to same lifeline.

  • Example: ATM Card Based Banking:

    
    User -> ATM: insertCard()
    
    ATM -> Bank: validateCard()
    
    Bank --> ATM: status
    
    ATM -> User: enterPIN()
    
    User -> ATM: enterPIN(pin)
    
    ...
    
    

• Collaboration Diagram (Communication Diagram in UML 2.x):

  • Focus: Structural organization of objects and links.

  • Messages numbered to show sequence (1., 2., 1.1, etc.).

  • Less emphasis on time, more on links.

• Similarities/Dissimilarities:

  | Feature | Sequence Diagram | Collaboration Diagram | |---------|-------------------|------------------------| | Primary focus | Time ordering | Object links | | Notation | Lifelines + activation | Links + numbered messages | | Easier to see | Concurrency, timing | Object relationships | | UML 2.x name | Sequence Diagram | Communication Diagram |

[!TIP]

Exam Question: "Draw interaction diagram for ATM". Use sequence diagram – clearer for time-based transactions. Show: User, ATM, Bank, CardReader as objects.

Class Diagrams

• Purpose: Static structure – classes, attributes, operations, relationships.

• Elements:

  • Class box: Three compartments (name, attributes, operations).

  • Association: Solid line between classes; may have multiplicity (1, , 0..1, 1..).

  • Navigability: Arrowhead shows direction (who knows whom).

  • Aggregation: Hollow diamond (whole-part, part can exist independently).

  • Composition: Filled diamond (strong ownership, part lifecycle tied to whole).

  • Generalization: Hollow arrow (inheritance).

• Identifying Associations:

  • Look for verbs relating classes (e.g., "Customer places Order" → association between Customer and Order).

  • Eliminate unnecessary: if association has no attributes and low cohesion, consider merging or removing.

• Example: Library Management:

  • Classes: Book, Member, Loan, Librarian.

  • Associations:

    • Member borrows Loan (1..*), Loan is for Book (1).

    • Librarian processes Loan (0..*).

  • Composition: Book has Chapters (filled diamond).

Activity Diagrams

• Purpose: Model workflow or business process; show parallel behavior.

• When to Use:

  • Complex algorithm with decisions/parallel threads.

  • Use case implementation (alternative flows).

  • Workflow across multiple classes.

• When NOT to Use:

  • Simple sequential logic → use sequence diagram.

  • Detailed object interactions → use sequence/collaboration.

  • Static structure → use class diagram.

• Notation:

  • Rounded rectangle = action.

  • Diamond = decision (branches labeled).

  • Bar = fork/join (parallel).

  • Swimlanes: partition by class/role.

Component & Deployment Diagrams

• Component Diagram:

  • Shows physical components (files, libraries, executables) and dependencies.

  • Component models:

    • CORBA (Common Object Request Broker Architecture):

      • Uses ORB (Object Request Broker) for communication.

      • Language-independent, network-transparent.

      • Components interface defined in IDL (Interface Definition Language).

    • COM/DCOM (Component Object Model / Distributed COM):

      • Microsoft’s binary standard.

      • COM: In-process (DLL) or local (EXE).

      • DCOM: Extension for distributed objects (network).

      • Uses interfaces (IUnknown) and reference counting.

• Deployment Diagram:

  • Shows hardware nodes and software artifacts deployed.

  • Example: Banking Application:

    • Nodes: Web Server, Application Server, Database Server, ATM.

    • Artifacts: banking.war on Web Server, banking.jar on App Server, banking.db on DB.

    • Connections: HTTP, JDBC, TCP/IP.

UML Notations Overview

• Standard Symbols:

  • Class: rectangle with compartments.

  • Interface: <<interface>> or circle.

  • Abstract class: italic name or {abstract}.

  • Package: tabbed folder.

  • Note: dog-eared rectangle (for comments).

• Extension Mechanisms:

  • Stereotypes: <<entity>>, <<control>>, <<boundary>> (from GRASP).

  • Tagged Values: {persistent}, {author="XYZ"}.

  • Constraints: {subtype disjoint}, {xor} in braces.

3. Analysis & Design Process

Class Identification & Refinement

• Techniques:

  1. Noun-verb analysis: From use case text, extract nouns (potential classes), verbs (potential operations/associations).

  2. CRC Cards (Class-Responsibility-Collaborator):

     • Card: Class name, responsibilities (what it does), collaborators (other classes it interacts with).

     • Team-based brainstorming.

• Elimination Criteria:

  • Unnecessary classes: Remove if:

    • No attributes/operations (just a role).

    • Duplicate responsibility (merge).

    • Outside system scope.

  • Unnecessary associations:

    • Low cohesion (association not central to class purpose).

    • Derived (can be computed from other associations).

    • Redundant (already implied by generalization).

  • Generalization: Use if subclasses have additional attributes/operations or vary behavior (polymorphism needed).

Design Patterns & Principles (Implied)

• Basic Principles:

  • Encapsulation: Hide implementation, expose interface.

  • Separation of Concerns: Divide system into distinct features (e.g., MVC).

  • High Cohesion, Low Coupling: Classes should have focused responsibility and minimal dependencies.

• GRASP (General Responsibility Assignment Software Patterns):

  • Creator: Class that contains/uses another should create it.

  • Controller: Assign responsibility for handling system events to non-UI class (e.g., "Use Case Controller").

User Interface Modeling

• Design UI with UML:

  • Use use case diagrams for user goals.

  • Sequence diagrams for screen navigation flow.

  • Class diagrams for UI widgets (if complex).

• Mapping Use Cases to Components:

  • Each use case → boundary class (e.g., WithdrawScreen).

  • Each use case → control class (e.g., WithdrawController).

  • Entity classes (domain) accessed by control.

• Example: ATM Banking System:

  • Boundary: CardReader, Keypad, Screen, CashDispenser.

  • Control: SessionController, TransactionController.

  • Entity: Account, BankDatabase.

  • Navigation: From "Main Screen" → "Withdraw Screen" → "Confirm Screen".

EXAM-DRIVEN PRIORITIES (RECAP)

QUICK REFERENCE: KEY FORMULAS & THEOREMS

• Subset Construction: $$\displaystyle |Q_{DFA}| \leq 2^{|Q_{NFA}|} $$

• Pumping Lemma for CFLs: If L is CFL, ∃ p (pumping length) s.t. any $w \in L$ with $|w| \geq p$ can be written $$\displaystyle w = uvxyz $$ with $|vy| \geq 1$, $|vxy| \leq p$, and $$\displaystyle uv^ixy^iz \in L $$ for all $i \geq 0$.

• Rice’s Theorem: Every non-trivial semantic property of RE languages is undecidable.

• Closure:

  • Recursive: $\cup, \cap, \complement, \cdot, *$

  • RE: $\cup, \cap, \cdot, *$ (not $\complement$)

• UML Multiplicity:

  • 1 exactly one

  • 0..1 zero or one

  • * or 0..* many

  • 1..* at least one

\boxed{\text{Revise past papers: Nov 2022 (ToC), Dec 2024 (OOAD) for exact question patterns.}}