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

Questions

1. Q1

   1. a)

      Design a DFA which accepts a binary number divisible by 4.

      [5]
   2. b)

      Design a Mealy machine to increment binary number by 1. Write down transition table.

      [4]
   3. c)

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

      [6]
   OR

2. Q2

   1. a)

      Define the following terms with proper examples. i) Alphabets ii) String iii) Natural language

      [6]
   2. b)

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

      [5]
   3. c)

      Construct a DFA over the alphabet {a, b} for accepting the strings ending with “ab”.

      [4]

3. Q3

   1. a)

      Find the regular expression for the set of strings recognized by the given FA using Arden’s theorem.

      [5]
   2. b)

      Determine the regular expression over the alphabet {0, 1} for the following : i) All the string containing exactly two 0’s ii) All the string that do not end with 01 iii) All the string containing 1 as a third character from end.

      [6]
   3. c)

      Explain the following terms : i) Kleene closure ii) Positive closure

      [4]
   OR

4. Q4

   1. a)

      Explain any three closure properties of Regular language.

      [6]
   2. b)

      What is a Regular expression? Explain in brief the applications of regular expressions.

      [5]
   3. c)

      Construct a NFA for the following RE using direct method RE = (ab + ba)*aa 

      [4]