CSE1008 -Theory of Computation

CSE1008 -Theory of Computation
Digital Assignment -1
 Date of Announcement    : 14-09-2020
Date of Submission           : 28-09-2020

  1. Give DFA’s accepting the following strings over the alphabet {0,1}
  2. The set of all strings beginning with 101.
  3. The set of all strings with exactly three consecutive 0’s.


  1. Consider the following ε-NFA


δ ε a b c
→p {q,r} φ {q} {r}
q φ {p} {r} {p,q}
*r φ φ φ φ
  1. Compute the ε-closure of each state.
  2. Convert into ε-NFA to NFA.


  1. Find the regular expression for the set of all strings denoted by R133 from the DFA given below
  2. Convert the following DFA to a Regular expression using state-elimination technique.
  0 1
→*  p s p
q p s
r r q
s q r


  1. Construct a PDA accepting (an bm cm dn | m,n ≥ 1} by empty stack. Give an ID representation for one valid and invalid string.
  2. Convert the PDA P=({p, q},{0,1},{X,Z0},δ,q,Z0) to a CFG if δ is given by:
  3. δ (q,1,Z0)={(q,XZ0)}
  4. δ (q,1,X)={(q, XX)}
  5. δ (q,0,X)={(p, X)}
  6. δ (q, ε, X)={(q, ε)}
  7. δ (p,1,X)={(p, ε)}
  8. δ (p,0,Z0)={(q,Z0)}


  1. Construct the CNF from the following CFG.

S→aAa | bBb | ε
A→ C | a
B→C | b
C→CDE | ε
D→A | B | ab

  1. Convert the CFG into GNF.

SàAA | 0
AàSS | 1

  1. Design context-free grammars for the following languages:
  2. {ai bj | i≤2j}


  1. Construct an NFA equivalent to the regular expression ((0+1)(0+1)(0+1))*.


  1. Show that the set L={On | n is a perfect cube} is not regular.


  1. Check the following grammar is ambiguous or not.

S->AS | ε
A->aa | ab | ba | bb
Order Now

Calculate a fair price for your paper

Such a cheap price for your free time and healthy sleep

1650 words
Place an order within a couple of minutes.
Get guaranteed assistance and 100% confidentiality.
Total price: $78
WeCreativez WhatsApp Support
Our customer support team is here to answer your questions. Ask us anything!
👋 Hi, how can I help?