Theory of Automata (CS402) Assignment # 6 spring 2012

Theory of Automata (CS402)

Assignment # 6

  Total marks = 20

                                                                                    

Please carefully read the following instructions before attempting the assignment.

Rules for Marking

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

• The assignment is submitted after due date.
• The submitted assignment does not open or file is corrupt.
• The assignment is copied.

Note that strict action would be taken if the submitted assignment is copied from any other student. Both students will be punished severely.

1)      You should concern recommended books to clarify your concepts as handouts are not sufficient.

2)      You are supposed to submit your assignment in .doc format. Any other formats like scan images, PDF, Zip, rar, bmp etc will not be accepted.

3)      You are advised to upload your assignment at least two days before Due date.

Important Note: 

Assignment comprises of 20 Marks. Note that no assignment will be accepted after due date via email in any case (whether it is the case of load shedding or emergency electric failure or internet malfunctioning etc.). Hence, refrain from uploading assignment in the last hour of the deadline, and try to upload Solutions at least 02 days before the deadline to avoid inconvenience later on.

For any query please contact: CS402@vu.edu.pk

Q1. Convert the following FA into equivalent PDA.

                                                                                                                        [Marks 7]

Q2. For which type of languages we must use Push and Pop in their corresponding PDA’s?

                                                                                                                        [Marks 3]

Q3. Construct a PDA that accepts the language of aⁿbⁿ⁺².

[Marks 10]

“Best of luck”

Theory of Automata (CS402) Assignment # 5 spring 2012

Theory of Automata (CS402)

Assignment # 5

  Total marks = 20

                                                                                       Deadline Date = June 19, 2012

Please carefully read the following instructions before attempting the assignment.

Rules for Marking

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

• The assignment is submitted after due date.
• The submitted assignment does not open or file is corrupt.
• The assignment is copied.

Note that strict action would be taken if the submitted assignment is copied from any other student. Both students will be punished severely.

1)      You should concern recommended books to clarify your concepts as handouts are not sufficient.

2)      You are supposed to submit your assignment in .doc format. Any other formats like scan images, PDF, Zip, rar, bmp etc will not be accepted.

3)      You are advised to upload your assignment at least two days before Due date.

Important Note: 

Assignment comprises of 20 Marks. Note that no assignment will be accepted after due date via email in any case (whether it is the case of load shedding or emergency electric failure or internet malfunctioning etc.). Hence, refrain from uploading assignment in the last hour of the deadline, and try to upload Solutions at least 02 days before the deadline to avoid inconvenience later on.

For any query please contact: CS402@vu.edu.pk

Q1. Write down CFG of a language in which the number of 1’s are greater than 0’s defined over an alphabet set {0,1}.                                                        Marks [7]

Q2. Make a CFG corresponding to the following RE:               

 ab*(a+b)* b + ba*(a+b)*a                                                                  Marks [7]

Q3. Sà aSb | bSa | SS | _^                                                         

Show that the given grammar is ambiguous by running “abab” and creating any of its two different parse trees.                                                                               Marks [6]

CS402 Assignment # 4 solution Spring 2012

cs402 4th assignment spring 2012

cme and discuss here about 4th assignment.
Question: Consider the following sequential circuit:
There are two points X and Y with respect to which the following four states of the machine are identified according to the presence and absence of current at these points:
q0(X=0, Y=0) (0,0)
q1 (X=0, Y=1) (0,1)
q2 (X=1, Y=0) (1,0)
q3 (X=1, Y=1) (1,1)
a. Write down the expressions to find out new X, new Y and output?
[Marks 5]
b. Calculate all the values of the respective transition table for a mealy machine?
[Marks 10]
c. Draw the resulting mealy machine from the transition table (calculated in step b)? [Marks 5]
Read more: cs402 4th assignment - Virtual University of Pakistan http://vustudents.ning.com/group/cs402theoryofautomata/forum/topic/show?id=3783342%3ATopic%3A1287433&xg_source=msg#ixzz1wMfH9NGS

CS402 Assignment No 5 fall 2012

Theory of Automata (CS402)

Assignment No.5

Deadline

Your assignment must be uploaded before or on.

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

Objective of this assignment is to make you able to understand the following concepts,

·         Defining Context Free Grammars for Different Languages

·         Null and Null-able Transitions and Regular Context Free Grammars

·         Chomsky Normal Form

·         Push Down Automata

Question No.1

Give CFG for the following languages,

1. aⁿb^m where m = n-1 and n = 1,2,3…

Some words belonging to this language are, a ,  aab , aaabb , aaaabbb , ….

2. aⁿb²ⁿ where n = 1,2,3…

Some words belonging to this language are, abb ,  aabbbb , aaabbbbbb , ….

Question No.2

Consider the CFG given below and find Null and Null-able transitions (if any) also remove these transitions to give new CFG

S ---- > ABB | CC | ABC | AC

A --- > a | Є

B --- > b | C

C --- > ab | Є

[Here Є means null string, as in CFG’s we use Є for indicating null string instead of ^ sign]

Question No.3

Convert the CFG (Context Free Grammar) given below to CNF (Chomsky Normal Form)

S ---- > YYY | ZZ | aa | bb

Y --- > a | Z

Z --- > b | Y

Question No.4

Design PDA (Push Down Automata) for the language given below,

(ba)ⁿ(a)ⁿ                  n = 1,2,3…

 

Assignment Uploading Instructions:

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

CS402 Assignment No 4 Solution & Discussion Due Date: 03-01-2012 Read more: CS402 Assignment No 4 Solution & Discussion Due Date: 03-01-2012

Objectives

Objectives of this assignment are to make students able to understand the following concepts,

• Transition Graph
• Regular Languages
• Non-Regular Languages
• Pumping Lemma Version I
• Pumping Lemma Version II

Assignment No.4

Question No 1

Marks: (2.5*4) =10 

Recall the idea of regular languages, so if L1 and L2 are regular languages then L1 + L2 , L1L2 and L1* are also regular languages. If L1 and L2 are expressed by TG1 and TG2 given below then find:

1.        I.      L1 + L2
2.     II.      L1L2
3.  III.      L1*
4.   IV.      L2^C 

L1= {all words that have different first and last letters}

L2= {Λ, ab, aaa, bbbb}

Question No 2

Marks: (5*2) =10

Suppose we have a language defined below:

à aⁿb³ⁿ Where n = 1, 2, 3 …

Some strings belonging to this language are, abbb , aabbbbbb , aaabbbbbbbbb, …..

à [a¹b³, a²b⁶ ,a³b⁹ ,a⁴b¹², …]

Using below given methods, prove that the given language is non-regular:

1. Pumping Lemma Version I
2. Pumping Lemma Version II

Hint: [Make use of some example strings]

 

 

 

 

You can view the demo video in file,http://vulms.vu.edu.pk/Courses/CS402/Downloads/Assignment1.00.zip to see how to make Transition Graph in MS Word.

 

Assignment Uploading Instructions:

• Upload single word file having solutions for all parts.

Read more: CS402 Assignment No 4 Solution & Discussion Due Date: 03-01-2012 - Virtual University of Pakistan http://vustudents.ning.com/group/cs402theoryofautomata/forum/topics/cs402-assignment-no-4-solution-discussion-due-date-03-01-2012#ixzz1i7xwYX1e

CS402 Theory of Automata ASSIGNMENT # 3 by Virtual University

                               CS402 Theory of Automata 

                            ASSIGNMENT # 3

                                           

                                                                                              Totalmarks=20

Fall 2011

Question No.1

1. Convert Moore machine given below in corresponding Mealy machine.

1. Run string abbbba on this machine and corresponding Mealy machine by showing complete process and confirm that both machines generate same outputs (ignoring extra character of Moore machine).

Question No.2

1. Convert following Mealy machine into corresponding Moore machine.

1. Run string bbaaba on this machine and corresponding Moore machine by showing complete process and confirm that both machines generate same outputs (ignoring extra character of Moore machine).

You can view the demo video in file,http://vulms.vu.edu.pk/Courses/CS402/Downloads/Assignment1.00.zip to see how to make Moore and Mealy machines in MS Word.

Assignment Uploading Instructions:

• Upload single word file having solutions for all parts.