06-16-2011, 07:15 PM
Theory of Automata (CS402)
Assignment No.4
Deadline
Your assignment must be uploaded before or on 23rd June 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
Objective of this assignment is to make students able to understand the following
concepts,
• Pumping Lemma Version I and II
• Defining Context Free Grammars for Different Languages
• Null and Null-able Transitions and Regular Context Free Grammars
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.
[Hint: Part b is somewhat tricky you need to be go through definition of pumping lemma
thoroughly to give answer of this part]
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.
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.
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
Important Note:
While attempting any question always remember the following points:
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).
Appendix
i. PALINDROME [already given in handouts]
S --------- > aSa | bSb | a | b | Є
ii. EVEN PALINDROME
S --------- > aSa | bSb | Є
iii. ODD PALINDROME
S --------- > aSa | bSb | a | b
Assignment Uploading Instructions:
Upload single word file in word 2003 format having solutions for all questions.
Assignment No.4
Deadline
Your assignment must be uploaded before or on 23rd June 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
Objective of this assignment is to make students able to understand the following
concepts,
• Pumping Lemma Version I and II
• Defining Context Free Grammars for Different Languages
• Null and Null-able Transitions and Regular Context Free Grammars
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.
[Hint: Part b is somewhat tricky you need to be go through definition of pumping lemma
thoroughly to give answer of this part]
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.
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.
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
Important Note:
While attempting any question always remember the following points:
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).
Appendix
i. PALINDROME [already given in handouts]
S --------- > aSa | bSb | a | b | Є
ii. EVEN PALINDROME
S --------- > aSa | bSb | Є
iii. ODD PALINDROME
S --------- > aSa | bSb | a | b
Assignment Uploading Instructions:
Upload single word file in word 2003 format having solutions for all questions.