(مبانی برنامه نویسی) دیاگرام های قابل انتقال یا Transition Diagram (عمومی _ الکترونیک)
پژوهشگر و نویسنده: ( افشین رشید )
نکته: برای پیاده سازی دستی یک اسکنر از ابزاری بنام دیاگرام انتقال (TransitionDiagram) کمک می گیریم.یک دیاگرام انتقال در واقع یک گراف جهت دار است که هر یک از گره های آن معرف یک وضعیت (State) است.
یکی از وضعیت ها بعنوان وضعیت شروع و یکی ( یا چند تا ) از آنها بعنوان وضعیت های خاتمه مشخص میگردد.برچسب ( Label) هایی روی لبه های یک دیاگرام انتقال قرار داده می شود که مشخص می کند در چه صورتی میتوان از یک وضعیت به وضعیت دیگر رفت .هر دیاگرام انتقال معرف یک زبان است .با خواندن کاراکترهای یک رشته تطبیق آنها با برچسب های دیاگرام انتقال معرف یک زبان و پیمایش آن دیاگرام می توان مشخص نمود که آیا آن رشته متعلق به زبان مورد نظر است یا خیر .به عنوان مثال دیاگرام انتقال زیر و عبارت منظم abb)* b|a) هر دو زبانی را توصیف میکنند که شامل رشته های‌تشکیل شده از علائم " a " و " b " که به زیر رشته " abb " ختم میشوند است.
دیاگرام فوق یک دیاگرام غیر قطعی (NonDeterministic) است. یک دیاگرام انتقال غیر قطعی دیاگرامی است که یکی از دو خاصیت زیر را داشته باشد :
_ لبه های خارج شده از برخی از وضعیت های آن برچسب مشابه داشته باشند.
_ لبه های دارای برچسب € وجود داشته باشد ( برچسب € به این معنی است که بدون توجه به ورودی می توانیم از یک وضعیت به وضعیتی دیگر برویم ) دیاگرام فوق غیر قطعی است زیرا از وضعیت S0 دو لبه با برچسب مشترک " a " خارج شده است.در صورتیکه دیاگرامی غیرقطعی نباشد آنرا قطعی (Deterministic) گویند. همچنین هر دیاگرام غیر قطعی را می توان به یک دیاگرام قطعی معادل تبدیل کرد.
نویسنده: دکتر (افشین رشید )