Timed automaton
অটোমেটা তত্ত্বে, একটি সময়োপযোগী অটোমেটন হল একটি সসীম অটোমেটন যা বাস্তব-মূল্যবান ঘড়ির একটি সসীম সেটের সাথে প্রসারিত। একটি সময়োপযোগী অটোমেটন চালানোর সময়, ঘড়ির মান একই গতিতে বৃদ্ধি পায়। অটোমেটন রূপান্তরের সময়, ঘড়ির মানগুলিকে পূর্ণসংখ্যার সাথে তুলনা করা যেতে পারে। এই তুলনাগুলি এমন রক্ষী গঠন করে যা রূপান্তরগুলিকে সক্ষম বা অক্ষম করতে পারে এবং এটি করার মাধ্যমে স্বয়ংক্রিয় যন্ত্রের সম্ভাব্য আচরণগুলিকে সীমাবদ্ধ করে। উপরন্তু, ঘড়ি পুনরায় সেট করা যেতে পারে। টাইমড অটোমাটা হল এক ধরনের হাইব্রিড অটোমাটার একটি উপ-শ্রেণী। সময়োপযোগী স্বয়ংক্রিয় তথ্য কম্পিউটার সিস্টেমের সময় আচরণের মডেল এবং বিশ্লেষণ করতে ব্যবহার করা যেতে পারে, যেমন, রিয়েল-টাইম সিস্টেম বা নেটওয়ার্ক। গত 20 বছর ধরে সুরক্ষা এবং প্রাণবন্ত বৈশিষ্ট্য উভয়ই পরীক্ষা করার পদ্ধতিগুলি উন্নত এবং নিবিড়ভাবে অধ্যয়ন করা হয়েছে। এটি দেখানো হয়েছে যে সময়োপযোগী অটোমাটার জন্য রাজ্যের পৌঁছানোর সমস্যাটি নির্ণায়ক, যা এটিকে হাইব্রিড অটোমাটার একটি আকর্ষণীয় উপ-শ্রেণীতে পরিণত করে। এক্সটেনশনগুলি ব্যাপকভাবে অধ্যয়ন করা হয়েছে, যার মধ্যে স্টপওয়াচ, রিয়েল-টাইম কাজ, খরচ ফাংশন এবং সময়োপযোগী গেম রয়েছে। টাইমড অটোমাটা এবং এক্সটেনশনগুলি ইনপুট এবং বিশ্লেষণ করার জন্য বিভিন্ন সরঞ্জাম রয়েছে, যার মধ্যে রয়েছে মডেল চেকার্স ইউপিএএএল, ক্রোনোস এবং সময়সূচী বিশ্লেষক টাইমস। এই সরঞ্জামগুলি আরও বেশি পরিপক্ক হয়ে উঠছে, তবে এখনও সমস্ত একাডেমিক গবেষণার সরঞ্জাম। উদাহরণ টাইমড অটোমেটন কী তা আনুষ্ঠানিকভাবে সংজ্ঞায়িত করার আগে, কিছু উদাহরণ দেওয়া হয়েছে। ইউনারি বর্ণমালার উপর সময়োপযোগী শব্দের ভাষা বিবেচনা করুন যাতে প্রথম সময় একক থাকে এবং পরপর দুটি শব্দের মধ্যে এক সময়ের কম একক থাকে। কাছাকাছি চিত্রিত এই ভাষাটি শনাক্তকারী একটি সময়োপযোগী স্বয়ংক্রিয় যন্ত্র একটি একক ঘড়ি ব্যবহার করে, যা কখনই একটির সমান হওয়া উচিত নয়। এই ঘড়িটি দৌড় শুরু হওয়ার পর থেকে সময় গণনা করে যদি কোনটি নির্গত না হয়, অথবা অন্যথায় শেষটি নির্গত হয়। এর মানে হল যে প্রতিবার একটি নির্গত হলে, এই ঘড়িটি শূন্যে পুনরায় সেট করা হয়। বাইনারি বর্ণমালার উপর সময়োপযোগী শব্দের ভাষা বিবেচনা করুন যাতে প্রতিটি পরবর্তী সময় ইউনিটে a দ্বারা অনুসরণ করা হয়। কাছাকাছি চিত্রিত এই ভাষাটিকে শনাক্তকারী সময়োপযোগী স্বয়ংক্রিয় যন্ত্রটি স্মরণ করে যে একটি ভাষা ছিল কি না যা এখনও একটি দ্বারা অনুসরণ করা হয়নি। যদি তা না হয়, তবে এটি রানটি গ্রহণ করে, অন্যথায় এটি প্রত্যাখ্যান করে। উপরন্তু, যখন এই ধরনের একটি ঘড়ি থাকে, তখন এটিতে এমন একটি ঘড়ি থাকে যা এই ধরনের প্রথমটি নির্গত হওয়ার পর থেকে অতিবাহিত সময় রেকর্ড করে। এই ক্ষেত্রে, একটি নির্গত হতে পারে না যদি ঘড়িটি কমপক্ষে একটির সমান হয় এবং এইভাবে রানটি ব্যর্থ হয়। আনুষ্ঠানিক সংজ্ঞা টাইমড অটোমেটন আনুষ্ঠানিকভাবে, একটি টাইমড অটোমেটন হল একটি টুপল যা নিম্নলিখিত উপাদানগুলি নিয়ে গঠিতঃ একটি সীমাবদ্ধ সেট যাকে বর্ণমালা বা এর ক্রিয়া বলা হয়। এটি একটি সীমাবদ্ধ সেট। এর উপাদানগুলিকে অবস্থান বা 'রাজ্য' বলা হয়। এটি শুরুর অবস্থানগুলির সেট। এটি একটি সীমাবদ্ধ সেট যাকে ঘড়ি বলা হয়। এটি গ্রহণযোগ্য অবস্থানের সমষ্টি। এটি প্রান্তের একটি সেট, যাকে ট্রানজিশনস অফ বলা হয়, যেখানে থেকে ঘড়ির সাথে জড়িত ঘড়ির সীমাবদ্ধতার সেট, এবং এর পাওয়ারসেট। থেকে একটি প্রান্ত হল অবস্থান থেকে অ্যাকশন, গার্ড এবং ঘড়ি রিসেট সহ একটি রূপান্তর। একটি অবস্থান এবং একটি ঘড়ির মূল্যায়ন সহ একটি জোড়াকে বর্ধিত রাজ্য বা রাজ্য বলা হয়। লক্ষ্য করুন যে রাষ্ট্র শব্দটি এইভাবে দ্ব্যর্থহীন, যেহেতু, লেখকের উপর নির্ভর করে, এর অর্থ একটি জোড়া বা এর একটি উপাদান হতে পারে। স্বচ্ছতার স্বার্থে, এই নিবন্ধটি উপাদানের জন্য অবস্থান শব্দটি এবং জোড়ার জন্য বর্ধিত অবস্থান শব্দটি ব্যবহার করবে। এখানে টাইমড অটোমাটা এবং ফাইনাইট অটোমাটার মধ্যে সবচেয়ে বড় পার্থক্য রয়েছে। একটি সীমাবদ্ধ স্বয়ংক্রিয় নিয়মে, কার্যকর করার এক পর্যায়ে, অবস্থাটি সম্পূর্ণরূপে পঠিত অক্ষরের সংখ্যা এবং সীমিত সংখ্যক সম্ভাব্য মান দ্বারা বর্ণনা করা হয়, যাকে আসলে "অবস্থা" বলা হয়। এর অর্থ হল, একটি অবস্থা এবং পড়ার জন্য শব্দের একটি প্রত্যয় দেওয়া হলে, অবশিষ্ট দৌড় সম্পূর্ণরূপে নির্ধারিত হয়। সুতরাং, "ফাইনাইট অটোমাটা" নামে "ফাইনাইট" শব্দটি রয়েছে। যাইহোক, নীচের "রান" বিভাগে যেমন ব্যাখ্যা করা হয়েছে, ঘড়িগুলি পুনরায় চালু করার জন্য কোন রূপান্তরগুলি নেওয়া যেতে পারে তা নির্ধারণ করতে ব্যবহৃত হয়। সুতরাং, অটোমেটনটির অবস্থা জানতে হলে, আপনাকে অবশ্যই জানতে হবে যে আপনি কোন অবস্থানে আছেন এবং ঘড়ির মূল্যায়ন। একটি সময়োপযোগী শব্দের সাথে, অ-ঋণাত্মক সংখ্যার ক্রমবর্ধমান ক্রম এবং উপরের মতো একটি সময়োপযোগী অটোমেটন দেওয়া হলে, একটি রান হল ফর্মের একটি ক্রম যা নিম্নলিখিত সীমাবদ্ধতাকে সন্তুষ্ট করেঃ (সূচনা) (পবিত্রতা), সকলের জন্য, ফর্মের একটি প্রান্ত রয়েছে যাতেঃ আমরা ধরে নিই যে সময় ইউনিটগুলি পাস হয়েছে, এবং এই সময়ে, গার্ড সন্তুষ্ট। আই. ই. সন্তুষ্ট করে, নতুন ঘড়ির মূল্যায়ন এর সাথে মিলে যায়, কোন সময় ইউনিটে পাস হয়েছে এবং যেখানে ঘড়িগুলি পুনরায় সেট করা হয়েছে। আনুষ্ঠানিক ভাবে। দৌড় গ্রহণ করার ধারণাকে সীমাবদ্ধ শব্দের জন্য সীমাবদ্ধ স্বয়ংক্রিয় হিসাবে এবং অসীম শব্দের জন্য বুচি স্বয়ংক্রিয় হিসাবে সংজ্ঞায়িত করা হয়। অর্থাৎ, যদি দৈর্ঘ্যের সীমা থাকে, তবে রানটি গ্রহণ করা হয় যদি। যদি শব্দটি অসীম হয়, তবে রানটি গ্রহণ করা হয় যদি এবং শুধুমাত্র যদি এমন একটি অসীম সংখ্যক অবস্থান বিদ্যমান থাকে। নির্দিষ্ট সময়ের অটোমেটন যেমন সসীম এবং বুচি অটোমেটন-এর ক্ষেত্রে, একটি নির্দিষ্ট সময়ের অটোমেটন নির্ধারণমূলক বা অনির্ধারিত হতে পারে। স্বজ্ঞাতভাবে, প্রতিটি ক্ষেত্রেই নির্ণায়ক হওয়ার অর্থ একই। এর মানে হল যে শুরুর অবস্থানগুলির সেট একটি সিঙ্গলটন, এবং একটি অবস্থা এবং একটি অক্ষর দেওয়া হলে, শুধুমাত্র একটি সম্ভাব্য অবস্থা রয়েছে যা পড়ার মাধ্যমে পৌঁছানো যেতে পারে। তবে, সময়োপযোগী অটোমেটন-এর ক্ষেত্রে আনুষ্ঠানিক সংজ্ঞাটি একটু বেশি জটিল। আনুষ্ঠানিকভাবে, একটি সময়োপযোগী স্বয়ংক্রিয় যন্ত্র নির্ধারণযোগ্য হয় যদিঃ প্রতিটি জোড়া পরিবর্তনের জন্য একটি একক টন হয় এবং, সন্তোষজনক ঘড়ির মূল্যায়নের সেটটি সন্তোষজনক ঘড়ির মূল্যায়নের সেট থেকে বিচ্ছিন্ন হয়। ক্লোজার প্রপার্টি অ-নির্ধারিত টাইমড অটোমাটা দ্বারা স্বীকৃত ভাষাগুলির শ্রেণীটি হ 'লঃ ইউনিয়নের অধীনে বন্ধ, প্রকৃতপক্ষে, দুটি টাইমড অটোমাটার বিচ্ছিন্ন ইউনিয়ন সেই অটোমাটা দ্বারা স্বীকৃত ভাষার সংযোগকে স্বীকৃতি দেয়। সংযোগস্থলের নিচে বন্ধ। পরিপূরকের অধীনে বন্ধ নয়। সমস্যা এবং তাদের জটিলতা সময়োপযোগী অটোমাটা সম্পর্কিত কিছু সমস্যার গণনামূলক জটিলতা এখন দেওয়া হয়েছে। সময়োপযোগী স্বয়ংক্রিয়তার জন্য শূন্যতার সমস্যাটি একটি অঞ্চল স্বয়ংক্রিয়করণ তৈরি করে এবং এটি খালি ভাষা গ্রহণ করে কিনা তা পরীক্ষা করে সমাধান করা যেতে পারে। এই সমস্যাটি পি. এস. পি. এ. সি সম্পূর্ণ। অনির্ধারিত সময়োপযোগী অটোমেটন-এর সর্বজনীনতা সমস্যা অনির্ধারিত, এবং আরও সুনির্দিষ্টভাবে Π। যাইহোক, যখন অটোমেটনটিতে একটি একক ঘড়ি থাকে, তখন বৈশিষ্ট্যটি নির্ণায়ক হয়; তবে, এটি আদিম পুনরাবৃত্তিমূলক নয়। এই সমস্যাটি প্রতিটি শব্দ একটি সময়োপযোগী অটোমেটন দ্বারা গৃহীত হয় কিনা তা নির্ধারণ করে। আরও দেখুন বিকল্প সময়োপযোগী অটোমেটনঃ সর্বজনীন রূপান্তর সহ সময়োপযোগী অটোমেটন-এর একটি সম্প্রসারণ। নোটস অটোমেটা (গণনা)