In Section 5.3.1, we considered the grammar S rightarrow | SS | iS | iSe and cla
ID: 3763794 • Letter: I
Question
In Section 5.3.1, we considered the grammar S rightarrow | SS | iS | iSe and claimed that we could test for membership in its language L by repeatedly doing the following, starting with a string w. The string w changes during repetitions. If the current string begins with e, fail; w is not in L. If the string currently has no e's (it may have i's), succeed; w is in L. Otherwise, delete the first e and the i immediately to its left. Then repeat these three steps on the new string. Prove that this process correctly identifies the strings in L.Explanation / Answer
s=iiiii(n times)eeeee(m times) n=0,1,2,3... and m=0,1,2,3.....(n>=m)
Examples: i,iiii,ie,iiee, eee
let x be a string in grammer.
Given process contain three steps.
1) If x begins with e then x is not in S
2) If x has no e's then x is in S
3)O.W delete the first e ans the i immediately left to it. Then repeat the process for the remaining string.
now let there are p i's and q e's in the string x and p>=q. All the p i's are at the begining and all the q e's are at the ending of x.
proof:
If p=0 then q= 0 as p>=q. (x=empty) This comes under 2nd step as there are no e's so string is identified.
If p>0 and q=0 then this comes under 2nd step as there are no e's and the string x is identified as part of the grammer.
If p>0 and q>0 then follow the 3rd step and remove first e and the i immediately left to it. then we are left with the string with p-1 i's and q-1 e's in the string. as pand q are finite finally we will be left with p-q i's which is part of the grammer by the 2nd step.
Therefore we can conclude that the process correctly identifies the Strings in L.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.