樹變換器
編輯在理論計算機科學和形式語言理論中,樹變換器(TT)是一種抽象的機器,它將一棵樹作為輸入,并生成輸出--通常是其他的樹,但也有產生詞或其他結構的模型。粗略地說,樹換能器擴展了樹自動機,與詞換能器擴展詞自動機的方式相同。操作樹狀結構而不是詞,使得樹形變換器能夠對形式語言或自然語言的語法定向變換進行建模。然而,在算法復雜性、閉合特性等方面,樹自動機并不像它們的詞自動機那樣表現良好。特別是,大多數的主要類別在組合下是不封閉的。樹型轉換器的主要類別是。
作為術語重寫的語義
編輯換能器
T的每個狀態以及T本身的語義是輸入樹(關于Σ)和輸出樹(關于Γ)之間的二元關系。
確定性和域
編輯與樹狀自動機一樣,如果δ的兩個規則沒有共享相同的左手邊,并且最多只有一個初始狀態,那么就說TOP是確定性的(縮寫為DTOP)。在這種情況下,DTOP的語義是一個從輸入樹(關于Σ)到輸出樹(關于Γ)的部分函數,DTOP的每個狀態的語義也是如此。換能器的域就是其語義的域。同樣,換能器的圖像也是其語義的圖像。
DTOP的屬性
編輯DTOP在聯合下是不封閉的:這對于確定性的詞轉換器來說已經是這樣了。DTOP的域是一個規則的樹狀語言。考慮到DTOP規則的左手邊與DTTA的左手邊相同,該領域是可被DTTA識別的,這一點并不令人驚訝。
因此,識別DTOP領域的DTTA的構造必須考慮到狀態的集合,并計算其領域的交集,因此有指數。
內容由匿名用戶提供,本內容不代表www.gelinmeiz.com立場,內容投訴舉報請聯系www.gelinmeiz.com客服。如若轉載,請注明出處:http://www.gelinmeiz.com/163357/