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

Questions

1. Q1

   1. a)

      Convert the given NFA- ε to an NFA to DFA.

      [9]
   2. b)

      Design a DFA which can accept a decimal number divisible by 3.

      Also asked:Aug 2025

      [6]
   OR

2. Q2

   1. a)

      Convert following NFA to DFA.

      [7]
   2. b)

      i) Design a moore machine for the 1’s complement of binary number. ii) Design a Mealy machine to find out 2’s complement of a given binary number. 2

      [8]

3. Q3

   1. a)

      Convert the following RE to ε -NFA and find the ε -closure of all the states and corresponding DFA. (0 + 1) *.1.(0 + 1).

      [9]
   2. b)

      i) Regular Expression of strings over {0,1} that have at least one 1. ii) Regular Expression of strings over {0,1} that have at most one 1. iii) Regular Expression of all strings over {0,1} ending with 00 and beginning with 1.

      [6]
   OR

4. Q4

   1. a)

      i) Write the regular expression for the language starting with a but not having consecutive b’s. ii) Write the regular expression for the language L over ∑ = {0,1} such that all the string do not contain the substring 01. iii) Write the regular expression for the language containing the string over {0,1} in which there are atleast two occurrences of 1’s between any two occurrences of 1’s between any two occurrences of 0’s.

      [7]
   2. b)

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

      [4]
   3. c)

      Construct the regular expression for the given DFA using Ardens Theorem. 

      [4]