اتوماتون بوچی

اتوماتون بوچی (زبان انگلیسی: Büchi automaton) را می‌توان به عنوان اتوماتونی در نظر گرفت که می‌توانند رشته‌های نامتناهی الفبا را بپذیرد. این اتوماتون اولین بار توسط ژولیوس ریچارد بوچی (Julius Richard Büchi) منطق‌دان سوئیسی در سال ۱۹۶۲ معرفی شد.^[1] اگر ω را به عنوان مجموعه اعداد طبیعی و Σ رابه عنوان الفبا در نظر بگیریم یک کلمه نامتناهی (یا یک ω-کلمه) را می‌توان به عنوان یک تابع از ω به Σ در نظر گرفت به این ترتیب مجموعه تمام کلمه‌های نامتناهی را با${\displaystyle \Sigma ^{\omega }}$ نشان می‌دهیم.

Julius Richard Büchi

تعریف

یک اتوماتون بوچی قطعی ۵ تایی ${\displaystyle A=(Q,\Sigma ,\delta ,q_{0},F)}$ است که در ان:

• Q مجموعه ای محدود از حالات است.
• Σ مجموعه‌ای محدود از نمادها است که الفبای A یا الفبای ورودی خوانده می‌شود.
• ${\displaystyle \delta :Q\times \Sigma \rightarrow Q}$ تابع انتقال است.
• ${\displaystyle q_{0}}$ عضوی از Q است و حالت ابتدایی نامیده می‌شود
• ${\displaystyle F\subset Q}$ مجموعه حالات قبول یا پایانی خوانده می‌شود.

فرض کنید ${\displaystyle A=(Q,\Sigma ,\delta ,q_{0},F)}$ یک اتوماتون بوچی متناهی باشد در این صورت یک تعمیم طبیعی از مفهوم اجرا (نسبت به اتوماتون قطعی متناهی) می‌تواند مطرح شود که به این صورت است که یک اجرا روی یک کلمه نامتناهی ${\displaystyle \sigma =a_{1}a_{2}a_{3}...}$ را به صورت دنبالهٔ ${\displaystyle r=sq_{1}q_{2}q_{3}...}$ تعریف می‌کنیم که از s شروع می‌کنیم و با ${\displaystyle a_{1}}$ به ${\displaystyle q_{1}}$ و سپس با ${\displaystyle a_{2}}$ به ${\displaystyle q_{2}}$ و… می‌رویم. به عنوان مثال در این اتوماتون:

A non-deterministic Büchi automaton that recognizes (0∪۱)*0^ω

اگر ${\displaystyle \sigma =100^{\omega }..}$ در اینصورت ${\displaystyle r=q_{0}q_{1}q_{1}^{\omega }}$ یه اجرای A است.

در این صورت می‌گوییم ماشین A رشته σ را قبول می‌کند اگر اجرایی وجود داشته باشد که در ان حداقل یکی از حالات قبول را به تعداد نامتناهی دیده باشیم.

در اتوماتون بوچی غیرقطعی به‌جای تابع انتقال، رابطهٔ انتفال مطرح است و مانند NFA هر حالت تحت رابطهٔ انتقال به مجموعه ای از حالات منجر می‌شود و به‌جای حالت آغازی مجموعه از حالات ابتدایی در نظر گرفته می‌شود. در حالت کلی وقتی کلمه اتوماتون بوچی را به تنهایی به کار می‌بریم منظورمان اتوماتون بوچی غیرقطعی است.

زبان‌های قابل تشخیص توسط اتوماتون بوچی

مجموعه تمام ω-کلمه‌های را که یک بوچی اتوماتون قبول می‌کند زبان ان بوچی اتوماتون می‌گویند. حالا یک زبان ${\displaystyle A\subset \Sigma ^{\omega }}$ را بوچی تشخیص پذیر می‌گوییم اگر بوچی اتوماتون M ای پیدا شود که ${\displaystyle L(M)=A}$ . یک زبان بوچی تشخیص پذیر است اگر و فقط اگر یک زبان امگا‌ی منظم باشد. مثلاً ${\displaystyle A=\Sigma ^{*}a^{\omega }\bigcup \Sigma ^{*}(ab)^{\omega }}$ .

ویژگی‌های بستاری

فرض کنید A,B دو بوچی اتوماتون باشند و C یک اتوماتون متناهی باشد در این داریم:

1. اجتماع:بوچی اتوماتونی هست که ${\displaystyle L(A)\cup L(B)}$ را تشخیص می‌دهد
2. اشتراک:بوچی اتوماتونی هست که ${\displaystyle L(A)\cap L(B)}$ را تشخیص می‌دهد
3. اتصال:بوچی اتوماتونی هست که ${\displaystyle L(C).L(A)}$ را تشخیص می‌دهد
4. ω-بستار:اگر${\displaystyle L(C)}$ کلمهٔ تهی را نداشته باشد بوچی اتوماتونی هست که ${\displaystyle L(C)^{\omega }}$ را تشخیص می‌دهد
5. مکمل:بوچی اتوماتونی هست که ${\displaystyle \Sigma ^{\omega }/L(A)}$ را تشخیص می‌دهد

انواع

• اتوماتون Co-Büchi
• اتوماتون بوچی ضعیف
• اتوماتون بوچی نیمه قطعی
• اتوماتون بوچی توسعه یافته

کاربرد

از بوچی اتوماتون معمولاً در وارسی مدل به عنوان یه نسخه نظریه ماشینی از یک فرمول در منطق موقت خطی استفاده می‌شود.

جستارهای وابسته

• وارسی مدل
• زبان امگا
• مترجم دوگانه
• ماشین بوخی توسعه یافته

منابع

1. Büchi, J.R. (1962). "On a decision method in restricted second order arithmetic". Proc. International Congress on Logic, Method, and Philosophy of Science. 1960. Stanford: Stanford University Press: 1–12.

• Y. Choueka: “Theories of automata on !-tapes: A simplified approach”, Journal of

Computer and System Sciences 8 (1974) No. 2, 117–141.

• https://faculty.math.illinois.edu/~eid1/ba.pdf