# 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

### 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
We offer 