文字列のピラミッド遷移行列

Question

こんにちはちょうどDFA

問題にNFA関連する問題を見ました。リーフノードの1つがルートノードに変換できる場合はtrueを返し、そうでない場合はfalseを返します。

例：

 root 
    /\ 
    X X 
    /\ /\ 
    X X X 
/\/ \/ \ 
A B C D 

地図：

 left: A | B | C | D 
right--------------------------------- 
A    B |A or C| D | A 
B    D |B or C| A | 
C        B 
D 

注：1。左の子がB、右の子がA、親ノードがBまたはCのいずれかである可能性があります

Answer 1

def generate_status(all_status, matrix): 
# print all_status 
if len(all_status) == 1: 
    return all_status[0] 

next_all_status = [] 
for i in xrange(len(all_status) - 1): 
    cur_status = set() 
    for first_status in all_status: 
     for second_status in all_status[i+1]: 
      cur_status |= set(list(matrix[first_status][second_status])) 
    next_all_status.append(cur_status) 

return generate_status(next_all_status, matrix) 


def is_legal_status(expression, status, matrix): 
    all_status = [set(s) for s in expression] 

return status in generate_status(all_status, matrix)