مسئله ارتفاع ستاره

مسئلهٔ ارتفاع ستاره که توسط Eggan Lawrence C مطرح شده است، مسئله ای در تئوری زبان صوری است که سعی در پاسخ به این پرسش دارد که آیا می توان همهٔ زبان منظم را به کمک عبارات منظمی که ارتفاع ستارهٔ محدودی دارند بیان کرد؟ ارتفاع ستارهٔ یک عبارت منظم، بیشینهٔ عمق ستاره های تو در تویی است که در آن عبارت وجود دارد. به طور مشخص تر، این مسئله بیان می کند که آیا همیشه عمق تو در توی یک کافی است و امکان پذیر است که همهٔ زبان های منظم را با عبارات منظم به عمق یک نشان داد؟ اگر پاسخ این سؤال منفی است، آیا الگوریتمی وجود دارد که عمق مورد نیاز را مشخص کند؟
مسئلهٔ اولیه، نخستین بار توسط Eggan پاسخ داده شد . او با ارائه مثالی نشان داد که پاسخ این پرسش منفی است. او برای هر عدد طبیعی مانند n، یک زبان منظم با ارتفاع ستارهٔ n ارائه داد. ساخت این عبارات به صورت بازگشتی است و به این ترتیب صورت می گیرد که عبارت e n + 1 ، از کنار هم قرار دادن دو نسخهٔ e n و تغییر نام نسخهٔ دوم با نام های جدید و پس از آن اضافه کردن یک نشانهٔ جدید در انتها و اضافه کردن پرانتز و ستاره در اطراف عبارت ساخته شده تا اینجا، صورت می گیرد.
با به کارگیری تنظیم «چپ» تصویر در سمت چپ متن ظاهر می شود. Eggan ثابت کرد که هیچ عبارت منظمی با ارتفاع ستارهٔ کمتر از n وجود ندارد که معادل با e n باشد . هرچند مثال ارائه شده توسط او از الفبای بزرگی استفاده می کند که برای زبانی با ارتفاع ستارهٔ n، اندازهٔ آن 2n - ۱ است. به همین دلیل، سؤال دیگری که مطرح کرد این بود که آیا مثال هایی روی الفبای دودویی وجود دارد که به این شکل باشند؟ این سؤال به سرعت توسط Dejean و Schützenberger پاسخ داده شد . آن ها مثالی بازگشتی از چنین عباراتی به ازای هر n ارائه دادند. e n در هر گام به این صورت ساخته می شود که ابتدا به تعداد 2n نشانهٔ اول و سپس e n و پس از آن به تعداد 2n نشانهٔ دوم و در انتها نیز e n قرار می گیرد. در نهایت پرانتز دور این عبارت قرار گرفته و ستاره اضافه می شود.
Dejean و Schützenberger و Salomaa نشان دادند که هیچ عبارت منظمی با ارتفاع ستارهٔ کمتری نمی تواند n را توصیف کند .
سؤال مطرح شدهٔ دوم، پاسخ به نسبت پیچیده تری نسبت به سؤال اول دارد و برای حدود دو دهه به عنوان یکی از مسائل معروف حل نشدهٔ حوزهٔ زبان های صوری شناخته می شد . Hashiguchi در سال ۱۹۸۸ الگوریتمی برای تعیین ارتفاع ستارهٔ هر عبارت منظمی ارائه داد. اما این الگوریتم عملی نیست و به محاسباتی می انجامد که حتی برای مثال های کوچک نیز امکان پذیر نیست. الگوریتم بهینه تری توسط Kirsten در سال ۲۰۰۵ ارائه شد، اما حتی این الگوریتم هم فاصلهٔ زیادی با آنچه که قابل انجام است، دارد . این الگوریتم توسط Colcombet و Löding در سال ۲۰۰۸ کلی سازی و بهینه سازی شده است و در سال ۲۰۱۷ در ابزار Stamina پیاده سازی شده است . [ ۱] [ ۲] [ ۳] [ ۴] [ ۵] [ ۶] [ ۷]