ارتباط بین اتوماتای درختی فازی قطعی و نگاشت های مرحله ای تشخیص پذیر نرمال

در اﯾﻦ ﻣﻘﺎﻟﻪ، ﺑﻪ ﺑﺮرﺳﯽ اﺗﻮﻣﺎﺗﺎی درﺧﺘﯽ ﻓﺎزی ﻣﯽﭘﺮدازﯾﻢ. ﯾﮏ زﺑﺎن درﺧﺖ ﻓﺎزی ﻣﺮﺣﻠﻪای ﺗﺸﺨﯿﺺﭘﺬﯾﺮ را ﺗﻌﺮﯾﻒ ﮐﺮده و ﻧﺸﺎن ﻣﯽدﻫﯿﻢ ﻫﺮ زﺑﺎن درﺧﺖ ﻓﺎزی ﺗﺸﺨﯿﺺﭘﺬﯾﺮ ﯾﮏ زﺑﺎن درﺧﺖ ﻓﺎزی ﻣﺮﺣﻠﻪای ﺗﺸﺨﯿﺺﭘﺬﯾﺮ اﺳﺖ. در اداﻣ ﻪ، ﯾﮏ اﺗﻮﻣﺎﺗﻮن درﺧﺘﯽ ﻓﺎزی ﻗﻄﻌﯽ را ﻣﻌﺮﻓﯽ ﮐﺮده و ﻧﺸ ﺎن ﻣ ﯽدﻫﯿ ﻢ ﺗﮑﯿﻪﮔﺎه ﯾﮏ زﺑﺎن درﺧﺖ ﻓ ﺎزی ﻗﺎﺑﻞ ﺗﺸﺨﯿﺺ ﺗ ﻮﺳﻂ ﯾﮏ اﺗ ﻮﻣ ﺎﺗﻮن درﺧﺘﯽ ﻓﺎزی، ﺗﺸﺨﯿﺺﭘﺬﯾﺮ اﺳﺖ. اﯾﻦ ﻣﻔﺎﻫﯿﻢ را روی ﺑﺮﺧﯽ اﺗﻮﻣﺎﺗﺎی درﺧﺘﯽ ﻓﺎزی ﻧﻤﺎﯾﺶ ﻣﯽدﻫﯿﻢ. ﻫﻤﭽﻨﯿﻦ، ﺛﺎﺑﺖ ﻣﯽﮐﻨﯿﻢ ﮐﻪ ﮐﻼس زﺑﺎنﻫﺎی درﺧﺖ ﻓﺎزی ﻗﺎﺑﻞ ﺗﺸﺨﯿﺺ ﺗﻮﺳﻂ اﺗﻮﻣﺎﺗﺎی درﺧﺘﯽ ﻓﺎزی ﻗﻄﻌﯽ، ﺑﺎ ﮐﻼس ﻧﮕﺎﺷﺖﻫﺎی ﻣﺮﺣﻠﻪای ﺗﺸﺨﯿﺺﭘﺬﯾﺮ ﺑﺮاﺑﺮ اﺳﺖ. در ﻧﻬﺎﯾﺖ، ﻧﺸﺎن ﻣﯽدﻫﯿﻢ ﮐﻪ ﯾﮏ زﺑﺎن درﺧﺖ ﻓﺎزی ﺗﻮﺳﻂ ﯾﮏ اﺗﻮﻣﺎﺗﻮن درﺧﺘﯽ ﻓﺎزی ﻗﻄﻌﯽ ﻗﺎﺑﻞ ﺗﺸﺨﯿﺺ اﺳﺖ اﮔﺮ و ﻓﻘﻂ اﮔﺮ آن زﺑﺎن، ﯾﮏ ﻧﮕﺎﺷﺖ ﻣﺮﺣﻠﻪای ﺗﺸﺨﯿﺺﭘﺬﯾﺮ ﻧﺮﻣﺎل ﺑﺎﺷﺪ.

Relation Between Deterministic Fuzzy Tree Automata and Normal Recognizable Step Mappings

In this paper we investigate fuzzy tree automata. Fuzzy tree automata extend fuzzy automata. In fuzzy automata we deal with strings and in fuzzy tree automata we utilize trees instead of strings. We define a recognizable step fuzzy tree language and by a theorem we show that recognizable fuzzy tree language is recognizable step fuzzy tree language. Then, we define a deterministic fuzzy tree automaton and support of a fuzzy tree language and show that support of a fuzzy tree language can be recognized by a fuzzy tree automaton. We explain these concepts by examples. We also show that for a recognizable step mapping, there exists a deterministic fuzzy tree automaton that can recognize it, and vice versa. In fact we prove that the class of recognizable fuzzy tree languages is equal to the class of normal recognizable step mappings.The obtained theorems generalize the results of weighted automata to tree automata.