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
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
No comments:
Post a Comment