01-03-2012, 09:22 PM
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,http://vulms.vu.edu.pk/Courses/CS402/Dow...nt1.00.zip to see how to make Transition Graph in MS Word.
Assignment Uploading Instructions:
o Upload single word file having solutions for all parts.
IDEA SOLUTION:
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 vu solutoin .com 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 (snow) 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).
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,http://vulms.vu.edu.pk/Courses/CS402/Dow...nt1.00.zip to see how to make Transition Graph in MS Word.
Assignment Uploading Instructions:
o Upload single word file having solutions for all parts.
IDEA SOLUTION:
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 vu solutoin .com 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 (snow) 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).
0300-9520262
Get solution in 24 hour |cpmputer & internet
mileys81:[SIZE="4"][SIZE="3"]....[/SIZE][/SIZE]