الگوریتم ساختمان تامپسون
From Wikipedia, the free encyclopedia
در علوم نظری کامپیوتر ، به ویژه در نظریه زبان رسمی ، الگوریتم ساختمان تامپسون (TCA) یک عبارت منظم را به یک اتوماتای قطعی متناهی (NFA) تبدیل میکند، که یک تبدیل بین دو نوع از چند نوع فرمت تعریف زبانهای منظم ایجاد میکند. هنگامی که عبارتهای منظم به عنوان مثال برای توصیف الگوهای جستجوی پیشرفته در عملیاتهایی شبیه "پیدا و جایگزین کردن" در خدمات پردازش متن مورد استفاده قرار میگیرند، فرم NFA برای اجرا روی کامپیوتر مناسب تر است.
الگوریتم به صورت بازگشتی کار میکند به این صورت که با قطعه قطعه کردن عبارت به زیرعبارتهای اصلی ، و با استفاده از یک سری قوانین، NFA ساخته میشود.[1] چنین اتوماتایی میتواند با ساختمان پاورست و بعد مینیمم سازی آن با هدف تولید اتوماتایی بهینه ، به یک اتوماتای قطعی متناظر با عبارت منظم داده شده تبدیل شود.
برعکس الگوریتم تامپسون ، الگوریتم کلین یک اتوماتای متناهی را به یک عبارت منظم تبدیل میکند.