VUDESK
¤Virtual University Of Pakistan Network¤
VUDESk ALL Subject CODES
Find Your Subject Code , Join Group And You Will Get ALL related Data
CS001 CS101 CS201 CS301 CS302 CS304 CS401 CS402 CS403 CS408 CS410 CS501 CS502 CS504 CS506 CS507 CS508 CS601 CS602 CS604 CS605 CS606 CS607 CS609 CS610 CS614 CS615 CS619 CS701 CS702 CS703 CS704 CS708 CS709 CS710CS712 CS716 CS718 CS720 CS723
CS724
ETH201
HRM611 HRM619 HRMI619HRM620 HRM623 HRM624 HRM625 HRM627 HRM628HRM619 HRMI619HRMI620
ISL201
MCM101 MCM301 MCM304 MCM310 MCM311 MCM401 MCM404 MCM411 MCM431 MCM501 MCM511 MCM514 MCM515 MCM516 MCM517 MCM520MCM531 MCM532 MCM601 MCM604 MCM610 MCM619 MCMI619
MGT101 MGT111 MGT201 MGT211 MGT301 MGT401 MGT402 MGT411 MGT501 MGT502 MGT503 MGT504 MGT510 MGT520 MGT601 MGT602 MGT603 MGT604 MGT610 MGT611 MGT613 MGT619 MGTI619MGT620 MGTI620
MKT501 MKT530MKT610 MKT611 MKT621 MKT624 MKT625 MKT630 MKT619MKTI619MKT620MKTI620
PSY101 PSY401 PSY402 PSY403 PSY404 PSY405 PSY406 PSY407 PSY408 PSY409 PSY502 PSY504 PSY505 PSY510 PSY511 PSY512 PSY513 PSY514 PSY515 PSY610 PSY619 PSY631 PSY632 PSYI619
URD101
CS402 Theory of Automata-assignment 4 idea
CS_402 Assignment No.4
Theory of Automata
ASSIGNMENT NO.4
Total Marks= 20 (10+10)
Assignment Submission Deadline
Your assignment must be uploaded before or on 3rd of Jan, 2011 [upload your assignment well before due date to avoid any assignment uploading related issues].
Rules for Marking
It should be clear that your assignment will not get any credit if:
o The assignment is submitted after due date
o The assignment is copied
Objectives
Objectives of this assignment are to make students able to understand the following concepts,
o Transition Graph
o Regular Languages
o Non-Regular Languages
o Pumping Lemma Version I
o 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 vu solutions.com languages. If L1 and L2 are expressed by TG1 and TG2 given below then find:
I. L1 + L2
II. L1L2
III. L1*
IV. L2C
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:
anb3n Where n = 1, 2, 3 …
Some strings belonging to this language are, abbb , aabbbbbb , aaabbbbbbbbb, …..
[a1b3, a2b6 ,a3b9 ,a4b12, …]
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,to see how to make Transition Graph in MS Word.
http://vulms.vu.edu.pk/Courses/CS402/Downloads/Assignment1.00.zip
Assignment Uploading Instructions:
o Upload single word file having solutions for all parts.
Tags: 4, Automata-assignment, CS402, Theory, idea, of
-
-
cs402 assignment 4.pdf, 332 KB
-
Replies to This Discussion
-
Permalink Reply by Imtiaz Zaman on -
plz share any one idea solution of cs402
-
-
BS(CS)Permalink Reply by Nosheen on -
Question No.1 Pumping Lemma Version I and II
a. Suppose we have a language defined below,
anbm Where m = n! (n-factorial) and n = 1, 2, 3 …
Some strings belonging to this language are,
ab , aabb , aaabbbbbb , aaaabbbbbbbbbbbbbbbbbbbbbbbb , …
[a1b1 ,a2b2 ,a3b6 ,a4b24 , …]
Try to prove that this language is non-regular by Applying Pumping
Lemma Version I
and II on this language separately [by taking some example strings]
b. Can we say using PUMPING LEMMA I AND II for sure that a
given language is
regular or NOT.
according to definition of pumming lemma version 1 and 11 and by
proof this example
+++
If the pumping lemma is applied directly on the language L = {an bn :
n=0,1,2,3,…}, it can be observed that for the word w =
(aaa)(aaaabbbb)(bbb)
where x = aaa, y = aaaabbbb and z = bbb
xyyz will contain as many number of a’s as there are b’s but this string
will not belong to L because the substring ab can occur at the most
once in the words of L, while the string xyyz contains the substring ab
twice.
On the other hand if y-part consisting of only a’s or b’s, then xyyz will
contain number of a’s different from number of b’s. This shows that
pumping lemma does not hold and hence the language is not regular.
+++
Then the anbm Where m = n! (n-factorial) and n = 1, 2, 3 …
Some strings belonging to this language are,
ab , aabb , aaabbbbbb , aaaabbbbbbbbbbbbbbbbbbbbbbbb , …
[a1b1 ,a2b2 ,a3b6 ,a4b24 , …] is not regular language.
+++++
B) Let L be an infinite language accepted by a finite automaton with N
states, then for all words w in L that have langth more than N, there are
strings x,y and z (y being non-null string) and length(x) + length(y) <=
N s.t.
w = xyz and all strings of the form xynz are in L for n = 1,2,3, …
According to example pumming lamma ll given language is
NOT regular
+++++++
Question No.2 Defining Context Free Grammars
a. Consider the languages EVEN and ODD defined as language having
strings of
even and odd lengths respectively, their RE’s are
Even Length Language:
((a+b)(a+b))* = (aa + ab + ba + bb)*
Odd Length Language:
((a+b)(a+b))* (a+b) = (aa + ab + ba + bb)* (a+b)
Give Context Free Grammars for these two languages separately.
S = {a,b}
productions:
S -->XaaX
X --> aX
X --> bX
X --> L
This grammar defines the language expressed by (a+b)*aa(a+b)*.
++++++
productions: for Odd Length Language:
((a+b)(a+b))* (a+b) = (aa + ab + ba + bb)* (a+b)
S --> SS
S --> XS
S -->
S --> YSY
X --> aa
X --> bb
Y --> ab
Y --> ba
This grammar generates EVEN-EVEN language.then the language is
((a+b)(a+b))* = (aa + ab + ba + bb)*
productions:
S --> SS
S --> XS
S -->
S --> YSY
X --> aa
X --> bb
Y --> ab
Y --> ba
X --> a
Y --> b
This grammar generates EVEN-EVEN language.
b. Let us define a Language MULTIPLE OF THREE PALINDROME having
all
those strings of PALINDROME which have length multiple of three,
some
words belonging to this language are,
^ , aaa , aba , bab , bbb , aaaaaa , aabbaa , abaaba , abbbba ,
baaaaab ,
babbab , bbaabb
bbbbbb, ….
[Null string is included considering zero is also multiple of three as 0 x
3 = 0]
i. Give CFG for this language.
++++
Consider the CFG of the language PALINDROME
S --> aSa | bSb | a | b |
It may be noted that this CFG is unambiguous as all the words of the
language PALINDROME can only be generated by a unique production
tree.
It may be noted that if the production S --> aaSaa is added to the
given CFG, the CFG thus obtained will be no more unambiguous.
+++++
ii. Modify your CFG for MULTIPLE OF THREE PALINDROME for
two languages below,
• EVEN MULTIPLE OF THREE PALINDROME
• ODD MULTIPLE OF THREE PALINDROME
HINT: See appendix to see definition of palindrome, even palindrome
and odd
palindrome
Question No.3 Null and Nullable Transitions, Regular
Context Free Grammars
Consider the two CFG’s given below,
S ---- > aAA | bBB | Є
A --- > bB | Є
B --- > aA | Є
S ---- > aAA | bBB | Є
A --- > bB | Z
B --- > aA | Є
Z--- > Є
[Here Є means null string, In CFG’s we generally use Є for indicating
null string instead
of ^ sign]
a. Find null and null-able transitions (if any) separately in these two
CFG’s
b. Remove null transitions from these CFG’s and give new CFG’s for
both cases without
null transitions
Appendix
i. PALINDROME
S --------- > aSa | bSb | a | b | Є
ii. EVEN PALINDROME
S --------- > aSa | bSb | Є
iii. ODD PALINDROME
S --------- > aSa | bSb | a | b
o Where OR is used in the description of a language it means that
expressions on
both sides of ‘OR’ are parts of the language.
o Where NOT is used in the description of the language it means
that language
includes all strings except described in the ‘NOT’ condition, for
example
language NOT starting with a, means all strings not having a in the
start (you
have to evaluate yourself what kinds of strings are these). -
-
Permalink Reply by Yasmeen(S.admin) on -
YE PDF FILE MAIN SOLUTION HAI .
DOWNLOAD KRK DEKH LAIN
-
Super Active Members
=======================
Popular Social Events
=======================
+ Miss VU
+ Mr VU
---------------------------------------
௵ MR VU,S
௵ ADMINS
ʭ☀Administration☀ʭ
Senior Admin : Yasmeen
VUDESK Owner : Ismail Shah
VUDESK GROUPS
© 2013 Created by ʭIsmail Shahʭ.
Become a Fan.
Follow Us On Twitter.
Subscribe To RSS.
Contact Us.