In computational theory, we have a lemma called Pumping Lemma and it says: If A is...

 

Transcribed Image Text:

In computational theory, we have a lemma called Pumping Lemma and it says: "If A is a regular language, then there is a positive integer p where if s is any string in A of length at least p, then s can be divided into three pieces, s = xyz, satisfying the following three conditions: 1) for each i 20, xyz A 2) lyl > 0 and 3) Ixyl p". This is a long lemma, and we can use notations and predicate functions to analyze it. Let's use R to represent the set of all regular languages, use size (x) to represent the length of string x, and let D (s, p) ="s can be divided into three pieces, s= xyz, satisfying the following conditions: 1) for each i 0, xyz A 2) lyl > 0 and 3) |xy| p". Then the above lemma becomes: AER 3p > 0.Vs A.size(s) > p D (s,p) Answer the following questions. a. Given a language A, can we use the above lemma to prove that A R? Why? b. Given a language A, what can be used as a witness / or witnesses to prove that A R? (Hint: come up with a predicate that can logically imply A & R first. The witness you find should be some s E A with some property that can be described using notations and functions defined above.) 2. Let e = if x 0 then b[0] else a[1][3] fi. Answer the following questions. a. If a = b (in other words, a and b are the same array), then is e a legal expression in our programming language? Why? b. Let o = (x = -1, b = (2), a = (a, B)), where a = (2,4) and B= (0). Is a proper for e? Does it satisfy e? Why? 3. Let u and v some be variables and a and be some semantic values (z and v might be the same variable, a and & might be the same value). When is o[ua][v+ B] = o[v B][ua] and when is olu a][v B]=o[v B][u a]? Discuss the four different cases depending on whether uvand whether a = B. o[u a][v ] = o[v B][u a]? o[u a][v+ B] = o[v B][u a]? UV U V U EV UEV a = a = B a = B a = B In computational theory, we have a lemma called Pumping Lemma and it says: "If A is a regular language, then there is a positive integer p where if s is any string in A of length at least p, then s can be divided into three pieces, s = xyz, satisfying the following three conditions: 1) for each i 20, xyz A 2) lyl > 0 and 3) Ixyl p". This is a long lemma, and we can use notations and predicate functions to analyze it. Let's use R to represent the set of all regular languages, use size (x) to represent the length of string x, and let D (s, p) ="s can be divided into three pieces, s= xyz, satisfying the following conditions: 1) for each i 0, xyz A 2) lyl > 0 and 3) |xy| p". Then the above lemma becomes: AER 3p > 0.Vs A.size(s) > p D (s,p) Answer the following questions. a. Given a language A, can we use the above lemma to prove that A R? Why? b. Given a language A, what can be used as a witness / or witnesses to prove that A R? (Hint: come up with a predicate that can logically imply A & R first. The witness you find should be some s E A with some property that can be described using notations and functions defined above.) 2. Let e = if x 0 then b[0] else a[1][3] fi. Answer the following questions. a. If a = b (in other words, a and b are the same array), then is e a legal expression in our programming language? Why? b. Let o = (x = -1, b = (2), a = (a, B)), where a = (2,4) and B= (0). Is a proper for e? Does it satisfy e? Why? 3. Let u and v some be variables and a and be some semantic values (z and v might be the same variable, a and & might be the same value). When is o[ua][v+ B] = o[v B][ua] and when is olu a][v B]=o[v B][u a]? Discuss the four different cases depending on whether uvand whether a = B. o[u a][v ] = o[v B][u a]? o[u a][v+ B] = o[v B][u a]? UV U V U EV UEV a = a = B a = B a = B