2013年7月7日 星期日

11203 - Can you decide it for ME?

Background

就如同你所明白的,一個形式系統(formal system)包括公設(axioms)以及推論(production rules) 的集合。在一般情況下,理論(theorem) 可以從上述的公設和推論中的系統得到。決定一個描述句(statement) 是否是來自 formal system 的 theorem 不是件容易的事。事實上,對於某些系統是不可能辦到的,最容易被想到的是 Gödel's incompleteness theorem。

The Problem

ME 是一套 formal system 有無限多個 axioms 和一個 production rule。但只有三個字符會出現在 ME 的 axioms,而這三個字母會有兩個大寫字母 M, E 以及字符 '?'。儘管有無限多個 axioms 這裡卻有一個簡單方法去描述:
  • Axiom 定義:
    ME 公設一個字串格式為 xM?Ex?,其中 x 是一個字串,由一個或多個 '?' 字符組成。
    注意到這一個詞 "
    M?Ex?" 並不是公設中的,因為 x 在 ME 中並不是合法字符。這裡描述的只是一個模式去描述這些公設。??M?E??? 的確是一個 axiom,因為將 x 替換成 ??。
有另外在 ME 中一種合法字串,每個 axiom 對於 ME 都是一個 theorem。此外,根據 production rule 也可以產生 theorems。
  • Production rule: 如果 xMyEz 是 theorem,則 xMy?Ez? 也是 theorem,其中 x, y, z 是由一個或多個 '?' 組成的字串。
舉個例子,字串 ??M?E??? 是 theorem,因為它是來自於公設,而字串 ??M??E???? 也是 theorem,因為它可以藉由 Production rule 從 ??M?E??? 推論得到。

我們可以決定一個字串是否是 ME 的 theorem,寫一個演算法來決定它。
讀入一個最多 50 字符的字串,並且決定它是否是 ME 的 theorem。

Input

輸入開始將會有一個整數 N,表示接下來有幾筆輸入。
而每一行將會有一個最多 50 的字串(非空字串,且不會有空白字元),不一定每個字符都是 ME 中所定義的。

Output

對於每組測資,如果是 theorem ,輸出 "theorem",反之輸出 "no-theorem"

Sample Input

7
??M?E??? 
xM?Ex?
??M??E????
M?E?
??m?e???
?M?E??
12M12E????

Sample Output

theorem
no-theorem
theorem
no-theorem
no-theorem
theorem
no-theorem

沒有留言:

張貼留言