(1) (10 pts) Let L-(00k | k > i + j). Use the pumping ien ma to show that L is n

Question

(1) (10 pts) Let L-(00k | k > i + j). Use the pumping ien ma to show that L is not regular (2) (10 pts) Let L- fww E f0,1 to show that L is not regular w is not a palindrome Use the pumping lemma (3) (15 pts) Let L(om1 | m n. Use closure properties of regular languages to prove L is not regular (4) (15 pts) Let -(0.1, +,-) Let ADDy+z | x,y,z are binary integers, and x is the sum of y and z pumping lemma to prove ADD is not regular Use the (5) (10 pts) Let L 1 that L is regular e (0, and y contains at least k 1s, for k Show

Explanation / Answer

Answer 1:

L = { 0^i 1^j 0^k | k > i + j }

Here k> i + j

Let i = 3 , j = 1 , k = 5

Now L = 000100000

Now let L be regular language , then there exists p > =1 such that each string w is in L. Here p is pumping length and w can be written as w = xyz

Now see we have divided w in substrings x , y and z

L = 000100000

Let x = 00 , y = 01000 , z = 00

and it should satisfy the conditions :

1. |y| > = 1

Here |y| is length of the substring y = 5

5 > 1 true

2. |xy| < = p

Here |xy| = length of substring = 7 , p = 9

Hence 9 > 7 true

3. xy^nz belongs to L

n is any integer > 0

y is a substring that can be pumped here

Now see

Let n = 2

xy^nz = 00(01000)^2 00 belongs to L

= 00010000100000 is not from L , thus we can says that L is not a regular language

DEAR PLEASE DO RATE IT IF HELPS ELSE LET ME KNOW YOUR DOUBT.

KINDLY POST SEPARARELY AS WE ARE RESTRICTED TO ANSWER MORE THAN ONE QUESTIONS POSTED TOGETHER.

THANK YOU!!!

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.