Timed automaton
ઓટોમેટા થિયરીમાં, ટાઈમ્ડ ઓટોમેટન એ વાસ્તવિક મૂલ્યની ઘડિયાળોના મર્યાદિત સમૂહ સાથે વિસ્તૃત મર્યાદિત ઓટોમેટન છે. સમયબદ્ધ ઓટોમેટનની દોડ દરમિયાન, ઘડિયાળના મૂલ્યો સમાન ગતિ સાથે વધે છે. ઓટોમેટનના સંક્રમણો સાથે, ઘડિયાળના મૂલ્યોની પૂર્ણાંકો સાથે સરખામણી કરી શકાય છે. આ સરખામણીઓ રક્ષકો બનાવે છે જે સંક્રમણોને સક્ષમ અથવા અક્ષમ કરી શકે છે અને આમ કરીને ઓટોમેટનની સંભવિત વર્તણૂકોને અવરોધે છે. વધુમાં, ઘડિયાળોને ફરીથી સેટ કરી શકાય છે. ટાઈમ્ડ ઓટોમેટા એ હાઇબ્રિડ ઓટોમેટા પ્રકારનો પેટા વર્ગ છે. ટાઈમ્ડ ઓટોમેટાનો ઉપયોગ કોમ્પ્યુટર સિસ્ટમ્સના ટાઈમિંગ બિહેવિયરનું મોડેલ અને વિશ્લેષણ કરવા માટે થઈ શકે છે, દા. ત., રીઅલ-ટાઇમ સિસ્ટમ્સ અથવા નેટવર્ક. છેલ્લા 20 વર્ષોમાં સલામતી અને જીવંત ગુણધર્મો બંનેની તપાસ માટેની પદ્ધતિઓ વિકસાવવામાં આવી છે અને તેનો સઘન અભ્યાસ કરવામાં આવ્યો છે. એવું દર્શાવવામાં આવ્યું છે કે ટાઈમ્ડ ઓટોમેટા માટે રાજ્યની સુલભતાની સમસ્યા નિર્ણાયક છે, જે આને હાઇબ્રિડ ઓટોમેટાનો એક રસપ્રદ પેટા વર્ગ બનાવે છે. એક્સ્ટેન્શન્સનો વ્યાપક અભ્યાસ કરવામાં આવ્યો છે, જેમાં સ્ટોપવૉચ, રીઅલ-ટાઇમ કાર્યો, ખર્ચ કાર્યો અને સમયબદ્ધ રમતો સામેલ છે. ટાઇમ ઓટોમેટા અને એક્સ્ટેન્શન્સને ઇનપુટ અને વિશ્લેષણ કરવા માટે વિવિધ સાધનો અસ્તિત્વમાં છે, જેમાં મોડેલ ચેકર્સ યુપીપીએએએલ, ક્રોનોસ અને શેડ્યૂલેબિલિટી એનાલાઇઝર ટાઈમ્સનો સમાવેશ થાય છે. આ સાધનો વધુને વધુ પરિપક્વ બની રહ્યા છે, પરંતુ હજુ પણ તમામ શૈક્ષણિક સંશોધન સાધનો છે. ઉદાહરણ ટાઇમ ઓટોમેટન શું છે તે ઔપચારિક રીતે વ્યાખ્યાયિત કરતા પહેલા, કેટલાક ઉદાહરણો આપવામાં આવ્યા છે. યુનરી મૂળાક્ષર પર સમયબદ્ધ શબ્દોની ભાષાને ધ્યાનમાં લો કે જેથી પ્રથમ વખત એકમ દરમિયાન એક હોય, અને બે ક્રમિક વચ્ચે એક કરતા ઓછો સમય એકમ હોય. નજીકમાં ચિત્રિત આ ભાષાને ઓળખતી સમયબદ્ધ ઓટોમેટન, એક જ ઘડિયાળનો ઉપયોગ કરે છે, જે ક્યારેય એકની બરાબર ન હોવી જોઈએ. આ ઘડિયાળ દોડની શરૂઆતથી સમયની ગણતરી કરે છે જો કોઈ ઉત્સર્જિત ન થયું હોય, અથવા અન્યથા છેલ્લા ઉત્સર્જિત સમયથી. આનો અર્થ એ છે કે દરેક વખતે જ્યારે a ઉત્સર્જિત થાય છે, ત્યારે આ ઘડિયાળ શૂન્ય પર રીસેટ થાય છે. દ્વિસંગી મૂળાક્ષર પર સમયબદ્ધ શબ્દોની ભાષાને ધ્યાનમાં લો કે જેથી દરેકને આગામી સમય એકમમાં a દ્વારા અનુસરવામાં આવે. નજીકમાં ચિત્રિત આ ભાષાને ઓળખતું સમયબદ્ધ ઓટોમેટન યાદ કરે છે કે ત્યાં એક હતું કે નહીં જે હજુ સુધી એક દ્વારા અનુસરવામાં આવ્યું ન હતું. જો એવું ન હોય તો, તે દોડ સ્વીકારે છે, અન્યથા તે તેને નકારી કાઢે છે. વધુમાં, જ્યારે આવી ઘડિયાળ હોય છે, ત્યારે તેમાં એક ઘડિયાળ હોય છે જે આ પ્રકારની પ્રથમ બહાર પાડવામાં આવી ત્યારથી વીતી ગયેલા સમયની નોંધ કરે છે. આ કિસ્સામાં, જો ઘડિયાળ ઓછામાં ઓછી એકની બરાબર હોય અને આમ રન નિષ્ફળ જાય તો a ઉત્સર્જિત કરી શકાતો નથી. ઔપચારિક વ્યાખ્યા ટાઈમ્ડ ઓટોમેટન ઔપચારિક રીતે, ટાઈમ્ડ ઓટોમેટન એ એક ટુપલ છે જેમાં નીચેના ઘટકોનો સમાવેશ થાય છેઃ એક મર્યાદિત સમૂહ છે જેને મૂળાક્ષર અથવા ક્રિયાઓ કહેવાય છે. તે એક મર્યાદિત સમૂહ છે. ના તત્વોને સ્થાનો અથવા 'રાજ્યો' કહેવામાં આવે છે. તે શરૂઆતના સ્થળોનો સમૂહ છે. તે એક મર્યાદિત સમૂહ છે જેને ઘડિયાળો કહેવાય છે. તે સ્વીકાર્ય સ્થળોનો સમૂહ છે. તે ધારોનો સમૂહ છે, જેને ટ્રાન્ઝિશન ઓફ કહેવાય છે, જ્યાં ઘડિયાળોનો સમાવેશ કરતી ઘડિયાળની મર્યાદાઓનો સમૂહ છે, અને તે ઘડિયાળનો પાવરસેટ છે. એક ધાર એ સ્થાનોમાંથી ક્રિયા, રક્ષક અને ઘડિયાળ રીસેટ સાથેનું સંક્રમણ છે. વિસ્તૃત રાજ્ય સ્થાન અને ઘડિયાળ મૂલ્યાંકન સાથેની જોડી વિસ્તૃત રાજ્ય અથવા રાજ્ય કહેવાય છે. નોંધ લો કે શબ્દ સ્થિતિ આમ અસ્પષ્ટ છે, કારણ કે, લેખકના આધારે, તેનો અર્થ જોડી અથવા તત્વ હોઈ શકે છે. સ્પષ્ટતાની ખાતર, આ લેખ તત્વ માટે સ્થાન શબ્દ અને જોડી માટે વિસ્તૃત સ્થાન શબ્દનો ઉપયોગ કરશે. અહીં ટાઈમ્ડ ઓટોમેટા અને ફાઈનાઈટ ઓટોમેટા વચ્ચેનો સૌથી મોટો તફાવત છે. મર્યાદિત ઓટોમેટનમાં, અમલના અમુક તબક્કે, સ્થિતિ સંપૂર્ણપણે વાંચેલા અક્ષરની સંખ્યા અને સંભવિત મૂલ્યોની મર્યાદિત સંખ્યા દ્વારા વર્ણવવામાં આવે છે, જેને વાસ્તવમાં "સ્થિતિઓ" કહેવામાં આવે છે. તેનો અર્થ એ કે, રાજ્ય અને વાંચવા માટેના શબ્દનો પ્રત્યય આપવામાં આવે તો, બાકીની દોડ સંપૂર્ણપણે નક્કી થાય છે. આમ, "ફાઈનાઈટ ઓટોમેટા" નામમાં "ફાઈનાઈટ" શબ્દ. જો કે, નીચે "રન" વિભાગમાં સમજાવ્યા મુજબ, ઘડિયાળો ફરી શરૂ કરવા માટે કયા સંક્રમણો લઈ શકાય તે નક્કી કરવા માટે ઘડિયાળોનો ઉપયોગ કરવામાં આવે છે. આમ, ઓટોમેટનની સ્થિતિ જાણવા માટે, તમારે બંનેને ખબર હોવી જોઈએ કે તમે કયા સ્થાને છો અને ઘડિયાળનું મૂલ્યાંકન. સમયબદ્ધ શબ્દ સાથે, બિન-નકારાત્મક સંખ્યાના વધતા ક્રમ અને ઉપરની જેમ સમયબદ્ધ ઓટોમેટનને જોતાં, રન એ નીચેના અવરોધને સંતોષતા સ્વરૂપનો ક્રમ છેઃ (આરંભીકરણ) (પવિત્રતા), બધા માટે, સ્વરૂપમાં એક ધાર અસ્તિત્વમાં છે જેમ કેઃ આપણે ધારીએ છીએ કે સમય એકમો પસાર થઈ ગયા છે, અને આ સમયે, રક્ષક સંતુષ્ટ છે. આઈ. ઇ. સંતોષ આપે છે, નવી ઘડિયાળનું મૂલ્યાંકન અનુરૂપ છે, જેમાં સમય એકમો પસાર થાય છે અને જેમાં ઘડિયાળો જ્યાં રીસેટ થાય છે. ઔપચારિક રીતે. દોડ સ્વીકારવાની કલ્પનાને મર્યાદિત શબ્દો માટે મર્યાદિત ઓટોમેટા તરીકે અને અનંત શબ્દો માટે બુચી ઓટોમેટા તરીકે વ્યાખ્યાયિત કરવામાં આવે છે. એટલે કે, જો લંબાઈ મર્યાદિત હોય, તો પછી રન સ્વીકારવામાં આવે છે. જો શબ્દ અનંત હોય, તો રન સ્વીકારે છે જો અને માત્ર ત્યારે જ જો ત્યાં અનંત સંખ્યામાં સ્થિતિ અસ્તિત્વમાં હોય. નિર્ધારિત સમયબદ્ધ ઓટોમેટન મર્યાદિત અને બુચી ઓટોમેટનના કિસ્સામાં, સમયબદ્ધ ઓટોમેટન નિર્ધારિત અથવા બિન-નિર્ધારિત હોઈ શકે છે. સહજ ભાવે, તે દરેક કિસ્સામાં નિર્ધારક બનવાનો અર્થ સમાન છે. તેનો અર્થ એ છે કે શરૂઆતના સ્થળોનો સમૂહ સિંગલટન છે, અને તે, એક સ્થિતિ અને એક અક્ષર આપવામાં આવે તો, માત્ર એક જ સંભવિત સ્થિતિ છે જે વાંચીને પહોંચી શકાય છે. જો કે, ટાઈમ્ડ ઓટોમેટનના કિસ્સામાં ઔપચારિક વ્યાખ્યા થોડી વધુ જટિલ છે. ઔપચારિક રીતે, ટાઈમ્ડ ઓટોમેટન નિર્ધારિત હોય છે જોઃ દરેક જોડીના સંક્રમણો માટે સિંગલટન હોય અને સંતોષકારક ઘડિયાળના મૂલ્યાંકનનો સમૂહ ઘડિયાળના સંતોષકારક મૂલ્યાંકનના સમૂહથી અલગ હોય. બંધ કરવાની મિલકત બિન-નિર્ધારિત સમયબદ્ધ ઓટોમેટા દ્વારા માન્યતા પ્રાપ્ત ભાષાઓનો વર્ગ છેઃ જોડાણ હેઠળ બંધ, ખરેખર, બે સમયબદ્ધ ઓટોમેટાઓનું અસંબદ્ધ જોડાણ તે ઓટોમેટા દ્વારા માન્યતા પ્રાપ્ત ભાષાના જોડાણને ઓળખે છે. આંતરછેદ હેઠળ બંધ. પૂરક હેઠળ બંધ નથી. સમસ્યાઓ અને તેમની જટિલતા સમયબદ્ધ ઓટોમેટા સંબંધિત કેટલીક સમસ્યાઓની ગણતરીની જટિલતા હવે આપવામાં આવી છે. સમયબદ્ધ ઓટોમેટા માટેની ખાલીપણાની સમસ્યાને ક્ષેત્ર ઓટોમેટન બનાવીને અને તે ખાલી ભાષાને સ્વીકારે છે કે કેમ તે ચકાસીને ઉકેલી શકાય છે. આ સમસ્યા સ્પેસ-પૂર્ણ છે. બિન-નિર્ધારિત સમયબદ્ધ ઓટોમેટનની સાર્વત્રિકતાની સમસ્યા અનિર્ણાયક છે, અને વધુ ચોક્કસપણે Π. જો કે, જ્યારે ઓટોમેટનમાં એક જ ઘડિયાળ હોય છે, ત્યારે ગુણધર્મ નિર્ણાયક હોય છે; જો કે, તે આદિમ પુનરાવર્તિત નથી. આ સમસ્યામાં એ નક્કી કરવાનો સમાવેશ થાય છે કે દરેક શબ્દ સમયબદ્ધ ઓટોમેટન દ્વારા સ્વીકારવામાં આવે છે કે કેમ. વૈકલ્પિક સમયબદ્ધ ઓટોમેટનઃ સાર્વત્રિક સંક્રમણો સાથે સમયબદ્ધ ઓટોમેટનનું વિસ્તરણ પણ જુઓ. નોંધો ઓટોમેટા (ગણતરી)