CS402 Assignment No. 3 Announced

Theory of Automata (CS402)

Assignment No.3

Total Marks: 20                                                                                   Due Date: 09-06-2011

Rules for Marking

It should be clear that your assignment will not get any credit if:

• The assignment is submitted after due date
• The assignment is copied

Objectives:

After completing this assignment you will be able to have a great deal of understanding of:

• Moore machine 
• Mealy machine 
• Regular language
• Non-regular language
• Complement method

Question No.1

Moore and Mealy machine 

Consider the following Moore machine 

IMAGE HERE

a)      Draw the transition table

b)      Run the string babbab over the above machine and determine corresponding output string plus table as well.

c)      Convert given Moore machine into an equivalent Mealy machine

                                

Question No.2

Regular Languages

Consider FA1 and FA2 representing languages L1 and L2 given below,

IMAGE HERE

Prove that Language representing FA1FA2 is regular using complement method.

                                              

Hint:

We know that a language is regular if it’s RE or FA or TG exists, so to prove L1L2 is regular you need to find FA1 U FA2 using complement method

[First find L1^c and L2^c Then L1^c ∩ L2^c then (L1^c∩ L2^c) ^c  then find out the final FA as (L1^c∩ L2^c) ^c = L1 U L2

Assignment Uploading Instructions:

Upload single word file in office 2003 format having solutions for all questions.