解題區/解題區 - UVa

UVa 10597 - Right Words

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

對一個已經是 Chomsky normal form 的 CFG，問一個 string 是否在 CFG 之中。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
S
SABC
ab
S -> AB
S -> BC
A -> BA
A -> a
B -> CC
B -> b
C -> AB
C -> a
# -> #
baaba
ab
abaa
a
aaaaa
bbbbb
#
S
SAB
ab
S -> AB
A -> AA
A -> a
B -> b
# -> #
ab
aaab
aba
baaaaaaaa
abbbbbb
aaaaaba
baaaaaaaab
aaaa
a
ab
#

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
baaba is in L(G)
ab is in L(G)
abaa is in L(G)
a is not in L(G)
aaaaa is in L(G)
bbbbb is not in L(G)
 
ab is in L(G)
aaab is in L(G)
aba is not in L(G)
baaaaaaaa is not in L(G)
abbbbbb is not in L(G)
aaaaaba is not in L(G)
baaaaaaaab is not in L(G)
aaaa is not in L(G)
a is not in L(G)
ab is in L(G)

Solution

因為 chomsky normal form 恰好劃分成兩個，定義字串 dp[l][r] 中可以解析出那些 nonterminal，藉由矩陣鍊乘積的方式，將其組合。最後檢查整個字串是否可以推回 start symbol。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <stdio.h> 
#include <string.h>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    char s1[1024], s2[1024];
    while (scanf("%s", s1) == 1) {
        char start = s1[0];
        scanf("%*s %*s");
        set<char> re[128];
        set<char> rule[128][128];
        while (scanf("%s -> %s", s1, s2) == 2 && s1[0] != '#') {
            if (s2[1] == '\0')
                re[s2[0]].insert(s1[0]);
            else {
                rule[s2[0]][s2[1]].insert(s1[0]);
            }
        }
        while (scanf("%s", s1) == 1 && s1[0] != '#') {
            int n = strlen(s1);
            set<char> dp[64][64];
            for (int i = 0; i < n; i++) {
                dp[i][i].insert(re[s1[i]].begin(), re[s1[i]].end());
            }
            for (int i = 1; i < n; i++) {
                for (int j = 0; i + j < n; j++) {
                    for (int k = j; k < i+j; k++) {
                        for (set<char>::iterator a = dp[j][k].begin();
                            a != dp[j][k].end(); a++)
                        for (set<char>::iterator b = dp[k+1][i+j].begin();
                            b != dp[k+1][i+j].end(); b++)
                            dp[j][i+j].insert(rule[*a][*b].begin(), rule[*a][*b].end());
                    }
                }
            }
            printf("%s is %sin L(G)\n", s1, dp[0][n-1].find(start) == dp[0][n-1].end() 
                                        ? "not " : "");
        }
        puts("");
    }
    return 0;
}