Sem 5

Information Technology

Year 3

Third Year

`Unit 1`

`FINITE STATE MACHINE1.What is power of alphabet? Give examples.2. Draw and explain lexical analyzer.3.  State Kleen’s theorem.4. Draw and explain transition matrix for full adder.5. How do a DFA process strings?6. Design a FA which accepts a decimal odd number.7. Design a FA which accepts an odd binary number.8. Design a FA to test divisibility by 3 for a unary number.9. Construct DFA for language defined by set S.10. Construct on NFA accepting {0} {1}* {0} *{1}.11. Define the following terms:<ul style="padding-left:0pt"><li style="font-family:serif; color:#ff0000; margin-left:12pt; line-height:150%; text-align:justify; font-size:12pt">Symbol</li><li style="font-family:serif; color:#ff0000; margin-left:12pt; line-height:150%; text-align:justify; font-size:12pt">Alphabet</li><li style="font-family:serif; color:#ff0000; margin-left:12pt; line-height:150%; text-align:justify; font-size:12pt">Word</li><li style="font-family:serif; color:#ff0000; margin-left:12pt; line-height:150%; text-align:justify; font-size:12pt">Formal language</li><li style="font-family:serif; color:#ff0000; margin-left:12pt; line-height:150%; text-align:justify; font-size:12pt">NFA</li></ul>12. M =({q0, q1, q2},{a,b}, δ, q0, q2}) be an NFA with δ as shown below. Q0 is start state is q2 is a final state. Find DFA. `