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