**MCA SEM II**

**Subject Code: 620007**

**Subject Name: Theory of Computation**

**UNIT – II**

**Question List -C**

Q.1 | (a) | Do as Directed. | |

(i) Define Regular Languages and Regular Expression over Σ | 2 | ||

(ii) Give the Regular Expression for The Language of C identifiers. | 1 | ||

(iii) List out any three Application of Regular Expression. | 1 | ||

(iv) What is the Precedence order for Regular Expression? | 1 | ||

(b) | Draw the FA for all strings over {0, 1} that begin and end with 111. | 5 | |

Q.2 | (a) | Define Distinguishable String With Respect to Language. Draw the FA for Regular Expression (a + b)* abb. | 5 |

(b) | Explain Different Types of State in Finite Automata. Draw DFA that will recognize the set {1, 00} and categorized all state in DFA according to its type. | 5 | |

OR | |||

(b) | Prove the Following. (i) (111*)* = (11 + 111)* (ii) (00*1)*1 = 1 + 0(0+10)*11 | 5 |