Note: Show a complete proof for each item and statement. SLIDES
Posted: Sat May 14, 2022 7:14 pm
Note: Show a complete proof for each item and statement.
SLIDES
(f) Use the CYK (dynamic programming) algorithm to determine if the G we used in class (see slides) generates the string babba (draw a similar table).
ACFG E P & Bottom-up DP = = n • Fix CFG G in Chomsky normal form. Input to DP algorithm is string w=w,w2w, with [w] =n = •W, In our case of DP, subproblems are to determine which variables in G can generate each substring of w. Create an n x n table 1 2 3 Complete string O FZ 3 Substrings of length 3 Substrings of length 2 Substrings of length 1 12 w
ACFG E P & Bottom-up DP 1 2 3 FZ Complete string 1 2 3 Substrings of length 3 Substrings of length 2 Substrings of length 1 21 TO O For i =j, (i, j)-th entry contains those variables that can generate substring w=w;W+1 • • •W ; For i>j, (i, j)-th entry is unused DP starts by filling in all entries for substrings of length 1, then all entries for length 2, then all entries for length 3, etc. Idea: Use shorter lengths to determine how to construct longer lengths O
ACFG E P & Bottom-up DP Suppose s = uv, B=*u, C=*v, and (3) rule A → BC. Then A=*s because A = BC=*uv = s. Suppose that algorithm has determined which variables generate each substring of length <k To determine if variable A can generate substring of length k +1: split substring into 2 non-empty pieces in all possible (k) ways For each split, algorithm examines rules A™ BC Each piece is shorter than current substring, so table tells how to generate each piece • Check if B generates first piece • Check if C generates second piece If both possible, then add A to table
ACEG E P & Bottom-up DP = = - = D = "On input string w=wW2...Wn: 1. For w=ɛ, if S → E is a rule, accept; else reject. (w = ε case) 2. For i= 1 to n [examine each substring of length 1] 3. For each variable A, 4. Test whether A →b is a rule, where b=wi 5. If so, put A in tableli, i) 6. For 1 = 2 to n, [l is length of substring] 7. For i=1 to n - 1+1, 8. Let j = i+1-1, [j is end position of substring] 9. For k=i to j-1, [k is split position] 10. For each rule ABC, 11. If table(i, k) contains B and table(k +1, j) contains C, put A in table(i, j) 12. If S is in table(1, n), accept; else, reject." = - - n
- Note Show A Complete Proof For Each Item And Statement Slides 1 (22.78 KiB) Viewed 42 times
- Note Show A Complete Proof For Each Item And Statement Slides 2 (226.08 KiB) Viewed 42 times
- Note Show A Complete Proof For Each Item And Statement Slides 3 (254.71 KiB) Viewed 42 times
- Note Show A Complete Proof For Each Item And Statement Slides 4 (128.55 KiB) Viewed 42 times
- Note Show A Complete Proof For Each Item And Statement Slides 5 (146.75 KiB) Viewed 42 times
ACFG E P & Bottom-up DP = = n • Fix CFG G in Chomsky normal form. Input to DP algorithm is string w=w,w2w, with [w] =n = •W, In our case of DP, subproblems are to determine which variables in G can generate each substring of w. Create an n x n table 1 2 3 Complete string O FZ 3 Substrings of length 3 Substrings of length 2 Substrings of length 1 12 w
ACFG E P & Bottom-up DP 1 2 3 FZ Complete string 1 2 3 Substrings of length 3 Substrings of length 2 Substrings of length 1 21 TO O For i =j, (i, j)-th entry contains those variables that can generate substring w=w;W+1 • • •W ; For i>j, (i, j)-th entry is unused DP starts by filling in all entries for substrings of length 1, then all entries for length 2, then all entries for length 3, etc. Idea: Use shorter lengths to determine how to construct longer lengths O
ACFG E P & Bottom-up DP Suppose s = uv, B=*u, C=*v, and (3) rule A → BC. Then A=*s because A = BC=*uv = s. Suppose that algorithm has determined which variables generate each substring of length <k To determine if variable A can generate substring of length k +1: split substring into 2 non-empty pieces in all possible (k) ways For each split, algorithm examines rules A™ BC Each piece is shorter than current substring, so table tells how to generate each piece • Check if B generates first piece • Check if C generates second piece If both possible, then add A to table
ACEG E P & Bottom-up DP = = - = D = "On input string w=wW2...Wn: 1. For w=ɛ, if S → E is a rule, accept; else reject. (w = ε case) 2. For i= 1 to n [examine each substring of length 1] 3. For each variable A, 4. Test whether A →b is a rule, where b=wi 5. If so, put A in tableli, i) 6. For 1 = 2 to n, [l is length of substring] 7. For i=1 to n - 1+1, 8. Let j = i+1-1, [j is end position of substring] 9. For k=i to j-1, [k is split position] 10. For each rule ABC, 11. If table(i, k) contains B and table(k +1, j) contains C, put A in table(i, j) 12. If S is in table(1, n), accept; else, reject." = - - n