درخت ( نظریه خودکار )

در تئوری اتوماتا، درخت روش بخصوصی برای نشان دادن ساختار درختی به عنوان دنباله‌ای از اعداد طبیعی می باشد.

تصویر گرافیکی درخت علامت دار که در مثال توضیح داده شده است

برای مثال، هر گره درخت یک کلمه از مجموعه اعداد طبیعی( $\mathbb {N}$ ) بیشتر می باشد که به استفاده از این تعریف در تئوری خودکار کمک می کند.

درخت مجموعه ای به شکل ^*$\mathbb {N}$ $\subseteq$ Tاست به طوری که اگر t . c ∈T , با ^*$\mathbb {N}$ $\in$ t و $\mathbb {N}$ $\in$ c ، سپس t ∈ T و t . c ₁ ∈ T برای همه $0\leq c1<c$. عناصر T تحت نام گره شاناسایی می شوند و کلمه خالی ε (تنها) ریشه T است. برای هر t∈ T عنصر t . c ∈ T جانشین t در جهت c می باشد. تعداد جانشینان t درجه یا آریتی آن نام گذاری می شود و باd(t) نشان داده می شود. گره در حالتی که دارای جانشینی نباشدT یک برگ می باشد . اگر هر گره درختی به طور متناهی جانشین های زیادی را شامل شود، آن را متناهی و در غیر این حالت یک درخت بی نهایت شاخه می نامند. مسیر π زیرمجموعه ای از T می باشد به گونه ای که ε ∈ π و برای هر t ∈ T ، یا t یک برگ می باشد یا یک c ∈ $\mathbb {N}$ یکتا موجود می باشد. به شکلی که t . c ∈ π. یک راه امکان دارد مجموعه ای متناهی یا نامتناهی باشد. در حالتی که تمام راه های درختی متناهی باشند، آن درخت، متناهی و در غیر این صورت نامحدود نامیده می شود. درختی را که همه ی مسیرهای آن بی نهایت باشند، کاملا نامحدود می نامند. با توجه به الفبای Σ، درخت شامل علامتΣ به صورت یک جفت می باشد( T ، V )، که در آن T یک درخت و V : T → Σ هر گره T را به یک سمبل در Σ ترسیم می کند. یک درخت علامت دار رسما یک ساختار درختی اصطلاح متداول را معرفی می کند. به سری هایی از درختان علامت دار، زبان درختی گفته می شود.

درختی را مرتب شده می نامند که در میان جانشینان هر یک از گره های آن نظمی برقرار باشد. تعریف بالا از درخت طبیعتاً نظمی را در میان جانشینان پیشنهاد می دهد که بتوان از آن برای رتبه بندی درخت استفاده کرد.

در مورد الفبای درجه بندی شده، متدی اضافی Ar : Σ → $\mathbb {N}$ تعیین شده است. این متد یک درجه ی مشخص را به هر نماد الفبا پیوند می دهد. در این صورت، هر t∈ T می بایست Ar ( V ( t )) = d ( t ) را برآورده کند. درختانی که این خصوصیات را برآورده می کنند درختان درجه بندی شده نام گذاری می شوند. درختانی که (الزاما) آن خاصیت را برآورده نمی کنند، نامرتب خوانده می شوند.

برای مثال، تعریف بالا در تعریف خودکار درختی بی نهایت مورد استفاده قرار می گیرد.

مثال

فرض کنید ^*T = {0,1} و Σ = { a, b }. ما متدی تحت عنوان V را به صورت زیر تعریف می‌کنیم: نامگذاری برای گره ریشه، V (ε) = a است و برای هر گره دیگر t ^*∈ {0,1} ، نامگذاری گره‌های جانشین آن V ( t 0.0) = a و V ( t .1) = b می باشد. از تصویر عیان است که T یک درخت دودویی (به طور کامل) بی نهایت را متشکل می شود.

منابع

Comon, Hubert; Dauchet, Max; Gilleron, Rémi; Jacquemard, Florent; Lugiez, Denis; Löding, Christof; Tison, Sophie; Tommasi, Marc (November 2008). "Preliminaries". Tree Automata Techniques and Applications (PDF). Retrieved 11 February 2014.