Timed automaton
آٹومیٹا تھیوری میں، ایک ٹائمڈ آٹومیٹن ایک محدود آٹومیٹن ہے جو حقیقی قدر والی گھڑیوں کے ایک محدود سیٹ کے ساتھ توسیع شدہ ہے۔ ٹائمڈ آٹومیٹن کی دوڑ کے دوران، گھڑی کی اقدار ایک ہی رفتار کے ساتھ بڑھتی ہیں۔ آٹومیٹن کی منتقلی کے ساتھ، گھڑی کی اقدار کا موازنہ انٹیجرز سے کیا جا سکتا ہے۔ یہ موازنہ محافظوں کی تشکیل کرتے ہیں جو منتقلی کو فعال یا غیر فعال کر سکتے ہیں اور ایسا کرنے سے آٹومیٹن کے ممکنہ طرز عمل کو محدود کر سکتے ہیں۔ مزید یہ کہ گھڑیوں کو دوبارہ ترتیب دیا جا سکتا ہے۔ ٹائمڈ آٹومیٹا ایک قسم کے ہائبرڈ آٹومیٹا کی ذیلی کلاس ہے۔ ٹائمڈ آٹومیٹا کو کمپیوٹر سسٹمز کے ٹائمنگ رویے کو ماڈل اور تجزیہ کرنے کے لیے استعمال کیا جا سکتا ہے، مثال کے طور پر، ریئل ٹائم سسٹمز یا نیٹ ورکس۔ پچھلے 20 سالوں میں حفاظت اور زندہ پن کی خصوصیات دونوں کی جانچ کے طریقے تیار کیے گئے ہیں اور ان کا گہرائی سے مطالعہ کیا گیا ہے۔ یہ دکھایا گیا ہے کہ ٹائمڈ آٹومیٹا کے لیے ریاست کی رسائی کا مسئلہ فیصلہ کن ہے، جو اسے ہائبرڈ آٹومیٹا کا ایک دلچسپ ذیلی طبقہ بناتا ہے۔ ایکسٹینشنز کا بڑے پیمانے پر مطالعہ کیا گیا ہے، ان میں اسٹاپ واچز، ریئل ٹائم ٹاسک، لاگت کے افعال، اور ٹائمڈ گیمز شامل ہیں۔ ٹائمڈ آٹومیٹا اور ایکسٹینشنز کو ان پٹ اور تجزیہ کرنے کے لیے مختلف قسم کے ٹولز موجود ہیں، جن میں ماڈل چیکرز یو پی پی اے اے ایل، کرونوس، اور شیڈول ایبلٹی اینالائزر ٹائمز شامل ہیں۔ یہ اوزار زیادہ سے زیادہ پختہ ہوتے جا رہے ہیں، لیکن پھر بھی یہ تمام تعلیمی تحقیقی اوزار ہیں۔ مثال باضابطہ طور پر ٹائمڈ آٹومیٹن کی وضاحت کرنے سے پہلے، کچھ مثالیں دی گئی ہیں۔ یونیری حروف تہجی پر ٹائمڈ الفاظ کی زبان پر غور کریں کہ پہلی بار یونٹ کے دوران ایک ہے، اور دو یکے بعد دیگرے کے درمیان ایک سے بھی کم ٹائم یونٹ ہے۔ اس زبان کو پہچاننے والا ایک ٹائمڈ آٹومیٹن، قریب کی تصویر میں، ایک واحد گھڑی کا استعمال کرتا ہے، جو کبھی بھی ایک کے برابر نہیں ہونی چاہیے۔ یہ گھڑی دوڑ کے آغاز کے بعد کے وقت کو شمار کرتی ہے اگر کوئی اخراج نہیں ہوا تھا، یا دوسری صورت میں آخری اخراج سے۔ اس کا مطلب یہ ہے کہ ہر بار جب ایک خارج ہوتا ہے، تو یہ گھڑی صفر پر ری سیٹ ہو جاتی ہے۔ بائنری حروف تہجی پر ٹائمڈ الفاظ کی زبان پر اس طرح غور کریں کہ ہر ایک کے بعد اگلی ٹائم یونٹ میں a آئے۔ قریب کی تصویر میں اس زبان کو پہچاننے والا ٹائمڈ آٹومیٹن یاد کرتا ہے کہ آیا کوئی ایسی زبان تھی جس کے بعد ابھی تک کوئی نہیں آیا تھا۔ اگر ایسا نہیں ہے، تو یہ دوڑ کو قبول کرتا ہے، بصورت دیگر اسے مسترد کر دیتا ہے۔ مزید برآں، جب ایسا ہوتا ہے، تو اس میں ایک گھڑی ہوتی ہے جو اس طرح کے پہلے اخراج کے بعد سے گزرے ہوئے وقت کو ریکارڈ کرتی ہے۔ اس صورت میں، a کا اخراج نہیں کیا جا سکتا اگر گھڑی کم از کم ایک کے برابر ہو، اور اس طرح رن ناکام ہو جائے۔ رسمی تعریف ٹائمڈ آٹومیٹن رسمی طور پر، ایک ٹائمڈ آٹومیٹن ایک ٹپل ہے جو مندرجہ ذیل اجزاء پر مشتمل ہوتا ہے: ایک محدود سیٹ ہے جسے حروف تہجی یا کے اعمال کہا جاتا ہے۔ ایک محدود سیٹ ہے۔ کے عناصر کو مقامات یا 'ریاستیں' کہا جاتا ہے۔ آغاز کے مقامات کا مجموعہ ہے۔ ایک محدود سیٹ ہے جسے کلاکس آف کہا جاتا ہے۔ قبول شدہ مقامات کا مجموعہ ہے۔ کناروں کا ایک مجموعہ ہے، جسے ٹرانزیشنز آف کہا جاتا ہے، جہاں سے گھڑیاں شامل ہوتی ہیں، اور اس کا پاور سیٹ ہے۔ ایک ایج سے مقامات سے ایکشن، گارڈ اور کلاک ری سیٹ کے ساتھ منتقلی ہے۔ توسیعی ریاست مقام اور گھڑی کی قیمت کے ساتھ ایک جوڑی کو توسیعی ریاست یا ریاست کہا جاتا ہے۔ نوٹ کریں کہ لفظ ریاست اس طرح مبہم ہے، کیونکہ، مصنف پر منحصر ہے، اس کا مطلب یا تو ایک جوڑا یا ایک عنصر ہو سکتا ہے۔ وضاحت کی خاطر، یہ مضمون عنصر کے لیے لوکیشن کی اصطلاح اور جوڑوں کے لیے توسیعی لوکیشن کی اصطلاح استعمال کرے گا۔ یہاں ٹائمڈ آٹومیٹا اور فائنٹ آٹومیٹا کے درمیان سب سے بڑا فرق ہے۔ ایک محدود آٹومیٹن میں، عمل کے کسی وقت، حالت کو مکمل طور پر پڑھے گئے حروف کی تعداد اور ممکنہ اقدار کی ایک محدود تعداد سے بیان کیا جاتا ہے، جنہیں دراصل "ریاستیں" کہا جاتا ہے۔ اس کا مطلب یہ ہے کہ، ایک حالت اور پڑھنے کے لیے لفظ کے لاحقہ کو دیکھتے ہوئے، بقیہ دوڑ مکمل طور پر طے کی جاتی ہے۔ اس طرح، "فائنٹ آٹومیٹا" کے نام میں لفظ "فائنٹ" ہے۔ تاہم، جیسا کہ ذیل میں "رن" سیکشن میں بیان کیا گیا ہے، دوبارہ شروع کرنے کے لیے گھڑیاں اس بات کا تعین کرنے کے لیے استعمال کی جاتی ہیں کہ کون سی ٹرانزیشن لی جا سکتی ہیں۔ اس طرح، آٹومیٹن کی حالت جاننے کے لیے، آپ دونوں کو معلوم ہونا چاہیے کہ آپ کس مقام پر ہیں، اور گھڑی کی قیمت۔ ایک ٹائمڈ لفظ کے ساتھ، غیر منفی نمبر کی بڑھتی ہوئی ترتیب، اور اوپر کے طور پر ایک ٹائمڈ آٹومیٹن کو دیکھتے ہوئے، رن فارم کا ایک سلسلہ ہے جو مندرجہ ذیل رکاوٹ کو پورا کرتا ہے: (شروعات) (تقدیس)، سب کے لیے، فارم میں ایک کنارے موجود ہے کہ: ہم فرض کرتے ہیں کہ ٹائم یونٹس گزر چکے ہیں، اور اس وقت، گارڈ مطمئن ہے۔ I. e. مطمئن کرتا ہے، نئی گھڑی کی قیمت اس سے مطابقت رکھتی ہے، جس میں وقت کی اکائیاں گزرتی ہیں اور جس میں گھڑیاں کہاں ری سیٹ ہوتی ہیں۔ رسمی طور پر۔ دوڑ کو قبول کرنے کے تصور کی تعریف محدود الفاظ کے لیے محدود آٹومیٹا میں اور لامحدود الفاظ کے لیے بوچی آٹومیٹا میں کی گئی ہے۔ یعنی، اگر لمبائی محدود ہے، تو رن قبول کرنا ہے۔ اگر لفظ لامحدود ہے، تو رن قبول کرنا ہے اگر اور صرف اس صورت میں جب اس طرح کی پوزیشن کی لامحدود تعداد موجود ہو۔ جیسا کہ محدود اور بوچی آٹومیٹن کے معاملے میں، ایک ٹائمڈ آٹومیٹن تعیناتی یا غیر تعیناتی ہو سکتا ہے۔ بدیہی طور پر، ان میں سے ہر معاملے میں فیصلہ کن ہونے کا ایک ہی مطلب ہے۔ اس کا مطلب یہ ہے کہ شروع ہونے والے مقامات کا مجموعہ سنگلٹن ہے، اور یہ کہ، ایک ریاست اور ایک خط کو دیکھتے ہوئے، صرف ایک ہی ممکنہ حالت ہے جس تک پڑھنے سے پہنچا جا سکتا ہے۔ تاہم، ٹائمڈ آٹومیٹن کے معاملے میں رسمی تعریف قدرے زیادہ پیچیدہ ہے۔ رسمی طور پر، ایک ٹائمڈ آٹومیٹن فیصلہ کن ہوتا ہے اگر: منتقلی کے ہر جوڑے کے لیے ایک سنگلٹن ہو اور، گھڑیوں کی قیمتوں کا مجموعہ جو مطمئن کرتا ہے وہ گھڑیوں کی قیمتوں کے سیٹ سے مطمئن نہیں ہوتا ہے۔ بندش کی خاصیت غیر متعین ٹائمڈ آٹومیٹا کے ذریعہ تسلیم شدہ زبانوں کی کلاس ہے: اتحاد کے تحت بند، درحقیقت، دو ٹائمڈ آٹومیٹا کا جداگانہ اتحاد ان آٹومیٹا کے ذریعہ تسلیم شدہ زبان کے اتحاد کو تسلیم کرتا ہے۔ چوراہے کے نیچے بند۔ تکمیل کے تحت بند نہیں۔ مسائل اور ان کی پیچیدگی ٹائمڈ آٹومیٹا سے متعلق کچھ مسائل کی کمپیوٹیشنل پیچیدگی اب دی گئی ہے۔ ٹائمڈ آٹومیٹا کے لیے خالی پن کا مسئلہ ریجن آٹومیٹن بنا کر اور یہ چیک کر کے حل کیا جا سکتا ہے کہ آیا یہ خالی زبان کو قبول کرتا ہے یا نہیں۔ یہ مسئلہ پی ایس پی اے سی ای مکمل ہے۔ غیر متعین ٹائمڈ آٹومیٹن کا عالمگیریت کا مسئلہ ناقابل فیصلہ ہے، اور زیادہ واضح طور پر Π۔ تاہم، جب آٹومیٹن میں ایک ہی گھڑی ہوتی ہے، تو اس کی خاصیت فیصلہ کن ہوتی ہے ؛ تاہم، یہ ابتدائی تکراری نہیں ہے۔ یہ مسئلہ یہ فیصلہ کرنے پر مشتمل ہے کہ آیا ہر لفظ کو ٹائمڈ آٹومیٹن کے ذریعے قبول کیا جاتا ہے۔ یہ بھی دیکھیں کہ الٹرنیٹنگ ٹائمڈ آٹومیٹن: یونیورسل ٹرانزیشن کے ساتھ ٹائمڈ آٹومیٹن کی توسیع۔ نوٹس آٹومیٹا (کمپیوٹیشن)