Skip to content
InsemOct 20242019 patternTE IT

Theory of Computation (TOC) SPPU Insem Question Paper Oct 2024

All 4 questions from this SPPU insem paper, as printed. Read them here or open the PDF.

Open the PDFMost repeated TOC questions
Subject code
314441
Pattern
2019 pattern
Exam
Insem
Session
Oct 2024
Max. marks
30
Time
1 Hour
Semester
I
Paper code
[6360]-55

Printed for: T.E. (Information Technology) (Insem)

Instructions to the candidates

  1. Answer Q1 or Q2, Q3 or Q4.
  2. Neat Diagrams must be drawn wherever necessary.
  3. Figure to the right indicate full marks.
  4. Assume suitable data if necessary.

Questions

  1. Q1

    1. a)

      Design a Moore machine to find 2’s complement of any binary number. Write the definition of a Moore Machine.

      [4]
    2. b)

      This part has equations that don’t show as text. Open the PDF to read it.

      [5]
    3. c)

      Write the formal definitions for the following : i) DFA (Deterministic Finite Automata) ii) Finite State Machine iii) NFA (Non- Deterministic Finite Automata) with  moves

      [6]

  2. Q2

    1. a)

      Construct a Moore machine for a binary input sequence such that if it has a substring ‘110’, the machine outputs A; if it has a substring ‘101’, the machine outputs B, otherwise machine outputs C.

      [5]
    2. b)

      Show that following DFAs (Deterministic Finite Automata) are equivalent or not.

      [5]
    3. c)

      Justify that there can be the equivalent Mealy machine for any Moore machine by suitable example.

      [5]

  3. Q3

    1. a)

      For the following regular expressions, draw the FA (Finite Automata) recognizing the corresponding language. i) ab* + ba* + b*a + (a*b)* ii) b*a (a+b)*ab*

      [5]
    2. b)

      State and explain Pumping Lemma for a regular language.

      [5]
    3. c)

      Find the regular Expression for the FA (Finite Automata) using Arden’s Theorem.

      [5]

  4. Q4

    1. a)

      This part has equations that don’t show as text. Open the PDF to read it.

      [5]
    2. b)

      Represent the following language using regular expression over  = {0,l,2} for the following i) At least one occurrence of 0 followed by at least one occurrence of 1 followed by at least one occurrence of 2. ii) Any number of 0’s followed by at least one occurrence of 1 followed by at least one occurrence of 2

      [5]
    3. c)

      This part has equations that don’t show as text. Open the PDF to read it.

      [5]