6 சுருக்க ஆட்டோமேட்டா கோட்பாட்டின் அடிப்படை கருத்துகள் மற்றும் வரையறைகள் (விரிவுரை எண். 9)
டிஜிட்டல் (தனிப்பட்ட) தானியங்கி இயந்திரம் (டிஏ) என்பது ஒரு குறிப்பிட்ட வழிமுறையின்படி தனித்தனி தகவலைப் பெறும், சேமிக்கும் மற்றும்/அல்லது மாற்றும் ஒரு சாதனமாகும். இலக்கு பார்வையாளர்களின் எடுத்துக்காட்டுகளில் உயிரினங்கள், செயலிகள், வீட்டு உபகரணங்கள், கால்குலேட்டர்கள் ஆகியவை அடங்கும் - இவை உண்மையான சாதனங்கள், மேலும் சுருக்கமானவை உள்ளன, எடுத்துக்காட்டாக, வழிமுறைகளின் மாதிரிகள். TA சேர்ந்தது தொடர் சாதனங்கள்.இந்த வகை சாதனங்கள், வெளியீடுகளின் மதிப்பு உள்ளீட்டு மதிப்புகளை மட்டுமல்ல, சாதனத்தின் தற்போதைய நிலையையும் சார்ந்துள்ளது என்பதன் மூலம் தீர்மானிக்கப்படுகிறது. அந்த. கருத்து அறிமுகப்படுத்தப்பட்டது - நிலை. சாதனம் அமைந்துள்ள மாநிலத்தைப் பற்றிய தரவைச் சேமிப்பதற்காக, இலக்கு பார்வையாளர்களில் சேமிப்பக கூறுகள் - தூண்டுதல்கள் பயன்படுத்தப்படுகின்றன.
6.1 டிஜிட்டல் இயந்திரத்தின் கணித மாதிரி
டிஜிட்டல் இயந்திரம் - ஒரு தொகுப்பால் வகைப்படுத்தப்படும் சாதனம் உள் மாநிலங்கள்அதில் உட்பொதிக்கப்பட்ட நிரலின் கட்டளைகளின் செல்வாக்கின் கீழ் அது விழும். ஒரு ஆட்டோமேட்டனை ஒரு மாநிலத்தில் இருந்து மற்றொரு நிலைக்கு மாற்றுவது ஒரு குறிப்பிட்ட நேரத்தில் நிகழ்கிறது.

இலக்கு பார்வையாளர்களின் கணித மாதிரி (மற்றும் உள்ளே பொது வழக்குஎந்தவொரு தனித்த சாதனம்) என்பது சுருக்கமான ஆட்டோமேட்டன் என்று அழைக்கப்படுகிறது, இது 6-கூறு டூப்பிள் என வரையறுக்கப்படுகிறது: S=(A,X,Y,,,a 1) இதில் உள்ளது:

1. 
   A=(a 1 , a 2 , ... ,a m ) – மாநிலங்களின் எழுத்துக்கள் – வடிவமைக்கப்பட்ட டிஜிட்டல் ஆட்டோமேட்டனைக் கண்டறியக்கூடிய நிலைகளின் தொகுப்பு. நாடகங்களின் எண்ணிக்கை முக்கிய பங்குஇலக்கு பார்வையாளர்களை செயல்படுத்தும் போது. அதிக நிலைகள், இலக்கு பார்வையாளர்களை உருவாக்க அதிக சேமிப்பக கூறுகள் (தூண்டுதல்கள்) தேவைப்படுகின்றன.
2. 
   X=(x 1 , x 2 , ... ,x f ) - உள்ளீட்டு மதிப்புகளின் எழுத்துக்கள் - இலக்கு பார்வையாளர்களுக்கு உள்ளீடு செய்யக்கூடிய மதிப்புகளின் தொகுப்பு. எடுத்துக்காட்டாக, இயந்திரம் இரண்டு இலக்க பைனரி உள்ளீட்டைக் கொண்டிருந்தால், எழுத்துக்களின் கூறுகள் 00, 01, 10 மற்றும் 11 ஆக இருக்கலாம்.
3. 
   Y=(y 1, y 2, ..., y g) - வெளியீட்டு மதிப்புகளின் எழுத்துக்கள் - இலக்கு பார்வையாளர்களின் வெளியீட்டில் அமைக்கக்கூடிய மதிப்புகளின் தொகுப்பு.
4. 
   : AXA - மாற்றம் செயல்பாடு a(t+1)= (x(t),a(t)). மாற்றம் செயல்பாடு எந்த நிலையை தீர்மானிக்கிறது a(t+1)உள்ளீட்டு சமிக்ஞையின் செல்வாக்கின் கீழ் இயந்திரம் நகரும் x(t), தற்போதைய நேரத்தில் இயந்திரம் மாநிலத்தில் இருந்தால் a(t).
5. 
    : AZW - வெளியீடு செயல்பாடு ஒய்(டி)=  (அ(டி), எக்ஸ்(டி)). வெளியீடுகளின் செயல்பாடு என்ன வெளியீட்டு மதிப்பை தீர்மானிக்கிறது ஒய்(டி) உள்ளீட்டு மதிப்பைப் பொறுத்து இயந்திரத்தின் வெளியீட்டில் அமைக்கப்படும் எக்ஸ்(டி) மற்றும் தற்போதைய நிலை அ(டி) .
6. 
   ஒரு ஐ  A - இயந்திரத்தின் ஆரம்ப நிலை - மின்சாரம் பயன்படுத்தப்பட்ட பிறகு அல்லது மீட்டமைக்கப்பட்ட பிறகு DA நிறுவப்பட்ட நிலை

படம் 6.1 - சுருக்க ஆட்டோமேட்டன்

ஒரு சுருக்க ஆட்டோமேட்டன் (படம் 6.1) ஒரு உள்ளீடு மற்றும் ஒரு வெளியீடு உள்ளது. ஆட்டோமேட்டன் தனித்தனி நேரத்தில் செயல்படுகிறது, எதிர்மறை அல்லாத முழு எண் மதிப்புகள் t = 0,1,2,... தனித்தனி நேரத்தின் ஒவ்வொரு கணமும் t, ஆட்டோமேட்டன் மாநிலங்களின் தொகுப்பிலிருந்து ஏதாவது ஒரு நிலையில் a(t) இருக்கும். ஆட்டோமேட்டன், மற்றும் ஆரம்ப தருணத்தில் t = 0 அது எப்போதும் ஆரம்ப நிலையில் a(0)=a1 இல் இருக்கும். கணம் t, a(t) நிலையில் இருப்பதால், ஆட்டோமேட்டன் X(t) உள்ளீட்டு எழுத்துக்களின் எழுத்தை உள்ளீடாகப் பெறும் திறன் கொண்டது.  Z. வெளியீட்டுச் செயல்பாட்டிற்கு இணங்க, அது அதே நேரத்தில் t வெளியீட்டு எழுத்துக்களின் y(t)=(a(t), z(t)) என்ற எழுத்தை உருவாக்கும் மற்றும் மாற்றம் செயல்பாட்டிற்கு ஏற்ப, அடுத்த நிலை a(t+1 )=, a(t)  A, y(t)  ஒய்.

ஒரு சுருக்க ஆட்டோமேட்டனின் கருத்தின் பொருள் என்னவென்றால், உள்ளீட்டு எழுத்துக்கள் X இன் சொற்களின் தொகுப்பிலிருந்து வெளியீட்டு எழுத்துக்கள் Y இன் சொற்களின் தொகுப்பிற்கு சில மேப்பிங்கைச் செயல்படுத்துகிறது. அதாவது, ஆட்டோமேட்டனின் உள்ளீடு, ஆரம்ப நிலை a1 என அமைக்கப்பட்டால், உள்ளீடு எழுத்துக்களின் x(0), x(1),... - உள்ளீட்டு வார்த்தையின் குறிப்பிட்ட வரிசை எழுத்துக்களுடன் கடிதம் மூலம் கடிதம் வழங்கப்பட்டால், பின்னர் எழுத்துக்கள் வெளியீட்டு எழுத்துக்களின் y(0) ஆனது ஆட்டோமேட்டனின் வெளியீட்டில் வரிசையாக தோன்றும், y(1),... என்பது வெளியீட்டு வார்த்தை. அந்த. வெளியீட்டு சொல் = (உள்ளீட்டு சொல்), இங்கு  என்பது சுருக்க ஆட்டோமேட்டனால் செய்யப்படும் மேப்பிங் ஆகும்.

சுருக்கக் கோட்பாட்டின் மட்டத்தில், "ஒரு ஆட்டோமேட்டனின் செயல்பாடு" என்ற கருத்து, உள்ளீட்டு வார்த்தைகளை வெளியீட்டு வார்த்தைகளாக மாற்றுவதாக புரிந்து கொள்ளப்படுகிறது. ஒரு சுருக்க ஆட்டோமேட்டனில் நாம் அதன் கட்டமைப்பிலிருந்து - செவ்வகத்தின் உள்ளடக்கங்களை (படம் 6.1) "கருப்பு பெட்டி" என்று கருதுகிறோம் என்று கூறலாம், அதாவது. தொடர்புடைய இயந்திரத்தின் நடத்தையில் நாங்கள் கவனம் செலுத்துகிறோம் வெளிப்புற சுற்றுசூழல்.

ஒரு ஆட்டோமேட்டனின் வரையறையில் நிலை என்ற கருத்து அறிமுகப்படுத்தப்பட்டது, ஏனெனில் அதன் வெளியீடுகள் உள்ளீடுகளின் நிலையை மட்டுமல்ல, அமைப்புகளின் நடத்தையையும் விவரிக்க வேண்டிய அவசியம் உள்ளது. இந்த நேரத்தில்நேரம், ஆனால் சில வரலாற்றுக்கு முந்தைய காலத்திலிருந்து, அதாவது. முந்தைய கணினி உள்ளீடுகளுக்கு வந்த சமிக்ஞைகளிலிருந்து. மாநிலங்கள் கடந்த காலத்தின் சில நினைவகத்துடன் துல்லியமாக ஒத்துப்போகின்றன, நேரத்தை ஒரு வெளிப்படையான மாறியாக அகற்ற அனுமதிக்கிறது மற்றும் வெளியீட்டு சமிக்ஞை ஒரு குறிப்பிட்ட நேரத்தில் நிலை மற்றும் உள்ளீட்டின் செயல்பாடாக வெளிப்படுத்தப்படுகிறது.

6.2 டிஜிட்டல் இயந்திரங்களின் வகைப்பாடு

மேலே விவாதிக்கப்பட்ட சுருக்க ஆட்டோமேட்டாவை பிரிக்கலாம்:

1. 
   முழுமையாக வரையறுக்கப்பட்ட மற்றும் பகுதி;
2. 
   நிர்ணயம் மற்றும் நிகழ்தகவு;
3. 
   ஒத்திசைவான மற்றும் ஒத்திசைவற்ற;

பகுதி அனைத்து ஜோடிகளுக்கும் (a i, z j) மாற்றம் செயல்பாடு அல்லது வெளியீடு செயல்பாடு அல்லது இந்த இரண்டு செயல்பாடுகளும் வரையறுக்கப்படாத ஒரு சுருக்கமான ஆட்டோமேட்டன் ஆகும்.

TO நிர்ணயிக்கப்பட்ட தெளிவற்ற மாற்றங்களின் நிபந்தனை திருப்தியளிக்கும் ஆட்டோமேட்டா இதில் அடங்கும்: ஒரு குறிப்பிட்ட நிலையில் அமைந்துள்ள ஒரு ஆட்டோமேட்டான், எந்த உள்ளீட்டு சமிக்ஞை z j இன் செல்வாக்கின் கீழ் ஒன்றுக்கும் மேற்பட்ட மாநிலங்களுக்கு மாற முடியாது.

இல்லையெனில் அது இருக்கும் நிகழ்தகவு தானியங்கி , இதில், கொடுக்கப்பட்ட நிலை a i மற்றும் கொடுக்கப்பட்ட உள்ளீட்டு சமிக்ஞை z j க்கு, பல்வேறு நிலைகளுக்கு கொடுக்கப்பட்ட நிகழ்தகவுடன் ஒரு மாற்றம் சாத்தியமாகும்.

தீர்மானிப்பதற்காக ஒத்திசைவான மற்றும் ஒத்திசைவற்ற ஆட்டோமேட்டா என்ற கருத்து அறிமுகப்படுத்தப்பட்டது நிலையான நிலை . ஒரு ஆட்டோமேட்டனின் நிலை a s நிலையானது என அழைக்கப்படுகிறது, எந்த ஒரு மாநிலத்திற்கும் a i மற்றும் உள்ளீட்டு சமிக்ஞை z j அதாவது (a i , z j) = a s நம்மிடம் உள்ளது (a s , z j) = a s , i.e. சில சிக்னல் zj இன் செல்வாக்கின் கீழ் இந்த மாநிலத்திற்குள் நுழைந்தால், ஆட்டோமேட்டன் அதை zj இலிருந்து வேறுபட்ட மற்றொரு சமிக்ஞை zk இன் செல்வாக்கின் கீழ் மட்டுமே விட்டுவிட்டால், ஒரு நிலை நிலையானது.

அனைத்து மாநிலங்களும் நிலையானதாக இருக்கும் ஒரு தானியங்கி - ஒத்திசைவற்ற .

இயந்திரம் என்று அழைக்கப்படுகிறது ஒத்திசைவான , அது ஒத்திசைவற்றதாக இல்லாவிட்டால்.

சுருக்க ஆட்டோமேட்டன் என்று அழைக்கப்படுகிறது இறுதி , A = (a 1 , a 2 , ..., a m ) செட் வரையறுக்கப்பட்டதாக இருந்தால், Z = (z 1 , z 2 , ..., z f ), W = (w 1 , w 2 , ... , w g ). இயந்திரத்தின் பெயர் ஆரம்ப , ஆரம்ப நிலை a 1 அதில் தேர்ந்தெடுக்கப்பட்டால்.
6.3 டிஜிட்டல் இயந்திரங்களின் வகைகள்
நடைமுறையில், இரண்டு வகை இயந்திரங்கள் மிகவும் பரவலாகப் பயன்படுத்தப்படுகின்றன - மீலி மற்றும் மூர் இயந்திரங்கள்.

மீலி இயந்திரத்தின் செயல்பாட்டு விதி சமன்பாடுகளால் வழங்கப்படுகிறது:

மீலி மற்றும் மூர் ஆட்டோமேட்டாவைத் தவிர, சி-ஆட்டோமேட்டான் என்று அழைக்கப்படும் ஆட்டோமேட்டனின் ஒருங்கிணைந்த மாதிரியைப் பயன்படுத்துவது சில நேரங்களில் வசதியானது.

ஒரு சுருக்கமான சி-ஆட்டோமேட்டனை ஒரு உள்ளீடு கொண்ட சாதனமாகக் குறிப்பிடலாம், இது X உள்ளீட்டு எழுத்துக்களில் இருந்து சமிக்ஞைகளைப் பெறுகிறது, மேலும் இரண்டு வெளியீடுகள், இதில் Y மற்றும் U என்ற எழுத்துக்களின் சிக்னல்கள் சி-தானியங்கிக்கும் மீலிக்கும் இடையே உள்ள வேறுபாடு மற்றும் மூர் மாதிரிகள் என்பது  1 மற்றும்  2 ஆகிய இரண்டு வெளியீட்டு செயல்பாடுகளை ஒரே நேரத்தில் செயல்படுத்துகிறது, ஒவ்வொன்றும் இந்த மாதிரிகளின் தனித்தன்மை வாய்ந்தது. சி-மெஷினின் இயக்க விதியை பின்வரும் சமன்பாடுகளால் விவரிக்கலாம்:
a(t+1) =(a(t), z(t)); w(t) = 1 (a(t), z(t)); u(t) =  2 (a(t)); t = 0, 1, 2, ...
வெளியீட்டு சமிக்ஞை U h = 2 (a m) இயந்திரம் ஒரு m நிலையில் இருக்கும் போது எல்லா நேரத்திலும் வழங்கப்படும். வெளியீட்டு சமிக்ஞை Wg= 1 (a m, z f) இயந்திரம் a m நிலையில் இருக்கும்போது Z f உள்ளீட்டு சமிக்ஞையின் செயல்பாட்டின் போது வெளியிடப்படுகிறது.
7 ஆட்டோமேட்டாவை விவரிக்கும் மற்றும் குறிப்பிடும் முறைகள் (விரிவுரை எண். 10)
ஒரு ஆட்டோமேட்டனை வரையறுக்க, டூப்பிள் S=(A, X, Y, , , a 1) இன் அனைத்து கூறுகளையும் விவரிக்க வேண்டியது அவசியம். A, X, Y ஆகிய தொகுப்புகள் அவற்றின் கூறுகளின் எளிய பட்டியலால் விவரிக்கப்பட்டு குறிப்பிடப்படுகின்றன. பன்முகத்தன்மைக்கு மத்தியில் பல்வேறு வழிகளில்செயல்பாடுகளின் பணிகள்  மற்றும்  (எனவே முழு இயந்திரமும்), அட்டவணை மற்றும் வரைகலை ஆகியவை மிகவும் பரவலாகப் பயன்படுத்தப்படுகின்றன.
7.1 டிஜிட்டல் இயந்திரங்களை விவரிக்கும் அட்டவணை முறை

டிஜிட்டல் இயந்திரங்களை விவரிக்கும் அட்டவணை முறையில், இரண்டு வகையான அட்டவணைகள் பயன்படுத்தப்படுகின்றன - ஒரு மாற்றம் அட்டவணை மற்றும் ஒரு வெளியீட்டு அட்டவணை.

மாற்றம் அட்டவணைமாற்றங்கள் செயல்பாட்டைக் காட்டுகிறது. அட்டவணையின் வரிசைகள் இயந்திரத்தின் நிலைகளுக்கு ஒத்திருக்கும், அதாவது. இயந்திரத்தின் நிலைகள் உள்ளதைப் போலவே அட்டவணையில் பல வரிசைகள் உள்ளன. அட்டவணையின் நெடுவரிசைகள் உள்ளீட்டு மதிப்புகளுக்கு ஒத்திருக்கும், அவை இலக்கு பார்வையாளர்களின் உள்ளீடுகளுக்கு வழங்கப்படலாம், அதாவது. உள்ளீட்டு எழுத்துக்களில் உள்ள கூறுகள் உள்ள பல நெடுவரிசைகள். அட்டவணைக் கலத்தில் உள்ள i-நெடுவரிசை மற்றும் j-வரிசையின் குறுக்குவெட்டில், இலக்கு பார்வையாளர்கள் உள்ளீட்டு சமிக்ஞையின் செல்வாக்கின் கீழ் செல்லும் நிலை x i (இது ஒத்துள்ளது நான்-வது நெடுவரிசை) மாநிலத்திலிருந்து a j (இது ஒத்துள்ளது jth வரி) மாற்றம் அட்டவணை படம் 6.2 இல் காட்டப்பட்டுள்ளது

வெளியீட்டு அட்டவணைக்கு மூர் இயந்திர துப்பாக்கிஒரு நிரலை கொண்டுள்ளது. அட்டவணையின் வரிசைகள் இயந்திரத்தின் நிலைகளுக்கு ஒத்திருக்கும், அதாவது. இயந்திரத்தின் நிலைகள் உள்ளதைப் போலவே அட்டவணையில் பல வரிசைகள் உள்ளன. அட்டவணையின் எடுத்துக்காட்டு படம் 6.4 இல் காட்டப்பட்டுள்ளது

y 2

படம் 6.7 - மூர் இயந்திரத்தின் வரைகலை பிரதிநிதித்துவம்

படம் 6.8 - மிலி இயந்திரத்தின் வரைகலை பிரதிநிதித்துவம்

• 
  மாநிலங்களின் உள்ளீடு, வெளியீடு மற்றும் எழுத்துக்களின் வரையறை, மாற்றங்கள் மற்றும் வெளியீடுகளின் செயல்பாடுகள்;
• 
  ஆட்டோமேட்டன் வரைபடங்கள் மற்றும் மாற்றங்கள் மற்றும் வெளியீடுகளின் அட்டவணைகளைக் குறிப்பிடுதல்;
• 
  மாநிலங்களின் எண்ணிக்கையை குறைக்கிறது

8.1 டிஜிட்டல் இயந்திரத்தின் அமைப்பு

டிஜிட்டல் இயந்திரத்தின் உள் அமைப்பை படம் 8.1 இல் காட்டப்பட்டுள்ளபடி சித்தரிக்கலாம்.

படம் 8.1 – கட்டமைப்பு திட்டம்டிஜிட்டல் இயந்திரம்.

நினைவக தொகுதி என்பது குறியிடப்பட்ட நிலை எண்ணின் பிட்களை சேமிக்கும் ஃபிளிப்-ஃப்ளாப்களின் தொகுப்பாகும். தூண்டுதல்களின் எண்ணிக்கை இயந்திரம் இருக்கக்கூடிய நிலைகளின் எண்ணிக்கையைப் பொறுத்தது. மேலும் இது கணக்கிடப்படுகிறது:

N=log 2 M
M என்பது மாநிலங்களின் எண்ணிக்கை, மற்றும் N என்பது தூண்டுதல்களின் எண்ணிக்கை
காம்பினேஷன் சர்க்யூட் எண். 2 இயந்திரத்தின் வெளியீடுகளின் செயல்பாட்டை செயல்படுத்துகிறது மற்றும் அதன் வெளியீட்டில் இயந்திரத்தின் வெளியீட்டு மதிப்புகள் இதற்கு ஏற்ப அமைக்கப்படுகின்றன. தற்போதைய நிலைஇயந்திரம் மற்றும் உள்ளீட்டு மதிப்புகள்.

8.2 டிஜிட்டல் இயந்திரத்தின் நிலைகளின் எண்ணிக்கையைக் குறைத்தல்
பெரும்பாலும் நிகழ்த்தும் போது சுருக்க தொகுப்புதேவையற்ற நிலைகள் அறிமுகப்படுத்தப்படுகின்றன, இதன் சமன்பாடு தெளிவாக இல்லை. அதிக எண்ணிக்கையிலான மாநிலங்கள் தேவையற்ற தூண்டுதல்களைப் பயன்படுத்த வழிவகுக்கும், இது CS1 மற்றும் CS2 ஐ சிக்கலாக்கும். எனவே, அதன் கட்டமைப்பு தொகுப்புக்கு முன் மாநிலங்களின் எண்ணிக்கையைக் குறைப்பது மிகவும் முக்கியம்.

குறைத்தல் அல்காரிதம் என்பது மாநிலங்களின் முழு தொகுப்பையும் இணையான மாநிலங்களின் ஜோடிவரிசையில் பிரிக்கப்பட்ட வகுப்புகளாகப் பிரிப்பதை அடிப்படையாகக் கொண்டது மற்றும் முழு சமமான வகுப்பையும் ஒரு மாநிலத்துடன் மாற்றுகிறது. இதன் விளைவாக குறைக்கப்பட்ட ஆட்டோமேட்டன், அசல் மாநிலங்களின் தொகுப்பைப் பிரிக்கும் அளவுக்கு பல சமநிலை வகுப்புகளாக பல மாநிலங்களைக் கொண்டிருக்கும்.

வரையறை இரண்டு மாநிலங்கள் ஏ கள் மற்றும் ஏ மீ என்றால் சமமானவை
 (அ கள் , இ) = (அ மீ , E), எங்கே - மாற்றம் செயல்பாடு, E - தன்னிச்சையான நீளத்தின் உள்ளீட்டு சொல்.

வேறு வார்த்தைகளில் கூறுவதானால், இரண்டு மாநிலங்களில் எதுவாக இருந்தாலும், அதே உள்ளீட்டு வார்த்தைகளுக்கு பதிலளிக்கும் வகையில் ஒரே வரிசை மாநிலங்கள் உருவாக்கப்பட்டால், மாநிலங்கள் சமமானவை. அ கள் அல்லது அ மீஇயந்திரம் ஆரம்ப நேரத்தில் அமைந்திருந்தது. இரண்டு மாநிலங்கள் சமமாக இருந்தால், ஒரு மாநிலத்தை மற்றொரு மாநிலமாக மாற்றலாம்.

சமமான நிலைகளுக்கு கூடுதலாக, கே-சமமான நிலைகளின் கருத்து உள்ளது: 1-சமமான, 2-சமமான, முதலியன.

வரையறை இரண்டு மாநிலங்கள் ஏ கள் மற்றும் ஏ மீ உள்ளனகே - சமமான என்றால்
 (அ கள் , ஈகே) =  (அ மீ , ஈகே), எங்கே - மாற்றம் செயல்பாடு, ஈகே- உள்ளீடு வார்த்தை நீளம்கே .
குறைத்தல் அல்காரிதம்:

1. 
   சில K+1 படிகளில் P K சமமான பகிர்வு முற்றிலும் சமமான வகுப்புகளைக் குறிக்கும்.
2. 
   ஒவ்வொரு சமநிலை வகுப்பிலும், ஒரு நிலை தேர்ந்தெடுக்கப்பட்டது, இது குறைக்கப்பட்ட ஆட்டோமேட்டனின் புதிய நிலைகளை உருவாக்குகிறது.
3. 
   மாற்றங்கள் மற்றும் வெளியீடுகளின் செயல்பாடுகளை மறுவரையறை செய்ய, குறைக்கப்பட்ட ஆட்டோமேட்டனின் புதிய நிலைகளில் சேர்க்கப்படாத நிலைகளுடன் தொடர்புடைய வரிசைகள் கடக்கப்படுகின்றன, மேலும் மாற்றம் அட்டவணையின் மீதமுள்ள வரிசைகளில், அனைத்து நிலைகளும் அவற்றின் சமமானவற்றால் மாற்றப்படுகின்றன. புதிய தொகுப்பில் சேர்க்கப்பட்டுள்ள மாநிலங்கள்.
4. 
   ஒரு தொகுப்பில் ஒரு மாநிலம் இருந்தால், அதற்கு சமமான நிலைகள் இல்லை. அனைத்து மாநிலங்களும் ஒரு மாநிலத்தில் இருந்து தனித்தனி தொகுப்புகளில் சேர்க்கப்பட்டால், ஆட்டோமேட்டன் குறைக்க முடியாது.
5. 
   தொகுப்புகளாகப் பிரித்தல் 0-சமமான வகுப்பில் தொடங்குகிறது. IN இந்த வழக்கில்ஒரே மாதிரியான வெளியீட்டு சமிக்ஞைகளைக் கொண்ட மாநிலங்கள் ஒரே தொகுப்புகளில் விழும்.

வெளியீட்டில், இது வேறுபட்ட எழுத்துக்களின் குறியீடுகளை (பொதுவாக) உருவாக்குகிறது.

சுருக்க தானியங்கி

முறையாக, ஒரு சுருக்க ஆட்டோமேட்டன் ஐந்து என வரையறுக்கப்படுகிறது

ஒரு சுருக்க ஆட்டோமேட்டனின் அளவுருக்களின் எண்ணிக்கையை வரம்பிடுவது வரையறுக்கப்பட்ட ஆட்டோமேட்டனின் கருத்தை வரையறுக்கிறது.

ஆட்டோமேட்டனின் செயல்பாடு இரண்டு வரிசைகளை உருவாக்குவதைக் கொண்டுள்ளது: ஆட்டோமேட்டனின் அடுத்த நிலைகளின் வரிசை மற்றும் வெளியீட்டு குறியீடுகளின் வரிசை, இது தனித்தனி நேர தருணங்களில் t = 1, 2, 3, ... தனித்துவம் நேரத் தருணங்கள் கடிகாரச் சுழற்சிகள் எனப்படும்.

நேரத்தின் தனித்தனியான தருணங்களில் ஆட்டோமேட்டனின் செயல்பாட்டை மீண்டும் மீண்டும் வரும் உறவுகளின் அமைப்பால் விவரிக்கலாம்:

சுருக்க ஆட்டோமேட்டாவின் பண்புகளை தெளிவுபடுத்த, ஒரு வகைப்பாடு அறிமுகப்படுத்தப்பட்டுள்ளது.

சுருக்க ஆட்டோமேட்டா தனித்த மாதிரிகளின் அடிப்படை வகுப்பை உருவாக்குகிறது, அவை அவற்றின் சொந்த மாதிரியாகவும், டூரிங் இயந்திரங்கள், ஸ்டோர்-மெமரி ஆட்டோமேட்டா, ஃபைனைட் ஸ்டேட் மெஷின்கள் மற்றும் பிற தகவல் மின்மாற்றிகளின் அடிப்படைக் கூறுகளாகவும் உள்ளன.

விக்கிமீடியா அறக்கட்டளை. 2010.

• மாநில வரைபடம் (தானியங்கி கோட்பாடு)
• நாகோர்னோ-கராபாக்

பிற அகராதிகளில் "சுருக்கமான ஆட்டோமேட்டன்" என்ன என்பதைப் பார்க்கவும்:

சுருக்க தானியங்கி- abstraktusis automatas statusas T sritis automatika atitikmenys: engl. சுருக்க ஆட்டோமேட்டன் vok. abstrakter Automat, m rus. சுருக்க ஆட்டோமேட்டன், மீ பிராங்க். தன்னியக்க சுருக்கம், மீ … ஆட்டோமேடிகோஸ் டெர்மினிஸ் சோடினாஸ்

இயந்திரம்- விக்சனரியில் “தானியங்கி இயந்திரம்” என்ற கட்டுரை உள்ளது தானியங்கி இயந்திரம்: தானியங்கி சாதனம் என்பது சில செயல்களைச் சுதந்திரமாகச் செய்யும் ஒரு சாதனம் ... விக்கிபீடியா

அரசு இயந்திரம்- ஒரு வரையறுக்கப்பட்ட நிலை இயந்திரம் என்பது வெளியீடு ஸ்ட்ரீம் இல்லாத ஒரு சுருக்க இயந்திரமாகும், இதில் சாத்தியமான நிலைகளின் எண்ணிக்கை வரையறுக்கப்பட்டுள்ளது. இயந்திரத்தின் செயல்பாட்டின் முடிவு அதன் இறுதி நிலையால் தீர்மானிக்கப்படுகிறது. உள்ளது பல்வேறு விருப்பங்கள்வரையறுக்கப்பட்ட இயந்திர பணிகள். உதாரணமாக,... ... விக்கிபீடியா

டூரிங் மெஷின்- 1930 களில் பிரிட்டிஷ் கணிதவியலாளர் ஆலன் எம். டூரிங் கோட்பாட்டளவில் வகைப்படுத்தப்பட்ட ஒரு சுருக்கமான ஆட்டோமேட்டன் (அதாவது ஒரு கணினி அல்லது பிற துல்லியமான, வரையறுக்கப்பட்ட பொறிமுறை). அடிப்படையில், ஒரு டூரிங் இயந்திரம் ஒரு டேப் மற்றும் ஒரு ரீட் ஹெட் ஆகியவற்றைக் கொண்டுள்ளது. ரிப்பன்…… அகராதிஉளவியலில்

ஆட்டோமேட்டா கோட்பாடு

ஆட்டோமேட்டா கோட்பாடு- தனித்த சுழற்சிகளில் தனித்த தகவலைச் செயலாக்கும் உண்மையான அல்லது சாத்தியமான சாதனங்களின் கணித மாதிரிகள் (இங்கே ஆட்டோமேட்டா அல்லது இயந்திரங்கள் என அழைக்கப்படுகின்றன) ஆய்வு செய்யும் கோட்பாட்டு சைபர்நெட்டிக்ஸ் பிரிவு. முக்கிய... ... பொருளாதார மற்றும் கணித அகராதி

தானியங்கு கோட்பாடு- தனித்த சுழற்சிகளில் தனித்த தகவலைச் செயலாக்கும் உண்மையான அல்லது சாத்தியமான சாதனங்களின் கணித மாதிரிகள் (இங்கு ஆட்டோமேட்டா அல்லது இயந்திரங்கள் என அழைக்கப்படுகின்றன) ஆய்வு செய்யும் கோட்பாட்டு சைபர்நெட்டிக்ஸ் பிரிவு. இந்தக் கோட்பாட்டின் அடிப்படைக் கருத்துக்கள்..... தொழில்நுட்ப மொழிபெயர்ப்பாளர் வழிகாட்டி

ஆட்டோமேட்டா கோட்பாடு- ஆட்டோமேட்டா கோட்பாடு என்பது தனித்தனி கணிதத்தின் ஒரு கிளை ஆகும், இது சுருக்க ஆட்டோமேட்டா, கணினிகள், கணித மாதிரிகள் மற்றும் அவை தீர்க்கக்கூடிய சிக்கல்களின் வடிவத்தில் வழங்கப்படுகிறது. தன்னியக்கக் கோட்பாடு ... ... விக்கிபீடியாவுடன் மிக நெருங்கிய தொடர்புடையது

கணினி- திட்டம் தனிப்பட்ட கணினி: 1. மானிட்டர் 2. மதர்போர்டு 3 ... விக்கிபீடியா

முறையான முறைகள்- கணினி அறிவியல் மற்றும் பொறியியலில் Z குறியீட்டைப் பயன்படுத்தி முறையான விவரக்குறிப்புக்கான எடுத்துக்காட்டு மென்பொருள்முறையான முறைகள் என்பது ... விக்கிபீடியாவுக்கான கணித உபகரணங்களை அடிப்படையாகக் கொண்ட நுட்பங்களின் குழுவாகும்

சுய ஆய்வுசுற்று பொறியாளர்கள். சுருக்க தானியங்கி. பகுதி 2

• ஆரம்பநிலைக்கான மின்னணுவியல்

கட்டுரை எழுதப்பட்டது, சேகரிக்கப்பட்டது மற்றும் தீட்டப்பட்டது. அவருக்கு மிக்க நன்றி.
முந்தைய கட்டுரையில், இந்த கட்டுரையை முடிந்தவரை தெளிவாக்குவதற்கு அனைத்து அடிப்படை வரையறைகளையும் கொள்கைகளையும் கோடிட்டுக் காட்ட முயற்சித்தேன். எல்லாம் பொருந்தவில்லை, எனவே இந்த கோப்புகளுடன் உங்களைப் பழக்கப்படுத்திக்கொள்ள நான் கடுமையாக அறிவுறுத்துகிறேன்:
அடிப்படை, அடிப்படை2, குறைத்தல். இக்கட்டுரையில் பின்னர் சில விளக்கக் குறிப்புகளை சாய்வு எழுத்துக்களில் இட்டுள்ளேன்.

இந்த கட்டுரையில், சுருக்கமான ஆட்டோமேட்டன் என்றால் என்ன, அதை எவ்வாறு பிரதிநிதித்துவப்படுத்துவது என்பதை அணுகக்கூடிய மொழியில் விளக்க முயற்சிப்பேன். ஆட்டோமேட்டாவின் கோட்பாடு கணிதம் மற்றும் சிக்கலானது என்பதால், நாம் என்ன பேசுகிறோம் என்பதை ஆயத்தமில்லாத வாசகருக்கு புரியும்படி மனித மொழியில் எழுத முயற்சிப்பேன்.

மின்னணு டிஜிட்டல் சுற்றுகளை முறையாக 2 வகுப்புகளாகப் பிரிக்கலாம்:

• கூட்டு சுற்றுகள் (CC) - நினைவகம் இல்லை. வெளியீட்டு சமிக்ஞையைப் பொறுத்து உருவாக்கப்படுகிறது சேர்க்கைகள்ஒரு குறிப்பிட்ட நேரத்தில் உள்ளீடு தரவு (சிக்னல் மாற்றத்தின் தாமதம், அவற்றின் வகைகள் மற்றும் கட்டுமானக் கொள்கைகள் ஆகியவை ஒரு தனி கட்டுரைக்கான தலைப்பாக இருக்கலாம், மேலும் எடுத்துக்காட்டுகள் பின்வருமாறு: கட்டுப்படுத்தப்பட்ட பேருந்துகள், மல்டிபிளெக்சர்கள் மற்றும் டிமல்டிபிளெக்சர்கள், டிகோடர்கள் மற்றும் குறியாக்கிகள், குறியீடு மாற்றிகள், கூட்டு கவுண்டர்கள் மற்றும் சேர்ப்பிகள் போன்றவை.
• நினைவகத்துடன் சுற்றுகள் - அவற்றின் செயல்பாட்டின் வழிமுறை உள்ளீடுகளின் நிலையைப் பொறுத்தது மற்றும் நினைவு(முந்தைய புள்ளிகளில் என்ன நடந்தது). இந்த சுற்றுகள் வரையறுக்கப்பட்ட நிலை இயந்திரக் கோட்பாட்டைப் பயன்படுத்தி விவரிக்கப்பட்டுள்ளன. அவற்றைப் பற்றி மேலும் பேசுவோம்.

சுருக்க தானியங்கி

அல்லது, நாம் விளக்கத்திலிருந்து கணித விளக்கத்திற்குச் சென்றால்:
A=

பதவிகள்:

1. அமை (A) - இயந்திரத்தின் இயற்பியல் உள்ளீடுகளில் மதிப்புகளின் தொகுப்பைக் குறிக்கிறது. எங்கள் விஷயத்தில் உள்ளீட்டில் உயர் மற்றும் குறைந்த மின்னழுத்த நிலைகளின் சில வரிசைகள் இருக்கும், அவை தருக்க பூஜ்ஜியங்கள் மற்றும் ஒன்றை குறியாக்கம் செய்யும்.
2. தொகுப்பு (பி) - இயந்திரத்தின் இயற்பியல் வெளியீடுகளில் மதிப்புகளின் தொகுப்பைக் குறிக்கிறது.
3. அமை (C) - மற்றும் இயந்திரத்தின் உள் நிலையைக் குறிக்கும் தொகுப்பு நினைவகம். எதிர்காலத்தில், C0 என்பது ஆட்டோமேட்டனின் ஆரம்ப நிலையைக் குறிக்கும்.
4. δ = X × Z → Z என்பது ஆட்டோமேட்டனின் நிலைமாற்றச் செயல்பாடுகள் ஆகும்.
5. λ = X × Z → Y - வெளியீடு செயல்பாடுகள், அவை உள்ளீடுகள் மற்றும் உள் நிலையைப் பொறுத்து இயந்திரத்தின் வெளியீட்டில் என்ன என்பதை தீர்மானிக்கின்றன.

அத்தகைய ஆட்டோமேட்டன் சரியான நேரத்தில் தனித்தனியாக இயங்குகிறது, அதாவது உள்ளீடுகள், வெளியீடுகளின் மதிப்புகள் மற்றும் ஆட்டோமேட்டனின் உள் நிலை ஆகியவை குறிப்பிட்ட தருணங்களில் மாறுகின்றன.
எனவே சுருக்க ஆட்டோமேட்டன் என்றால் என்ன என்பதை நாங்கள் பொதுவாக விவரித்துள்ளோம். அத்தகைய ஆட்டோமேட்டனின் உதாரணம் தூண்டுதல், கணினி பதிவு அல்லது சேர்ப்பவராக இருக்கலாம்.

2 வகையான இயந்திரங்கள் உள்ளன:

1. மிலி இயந்திரங்கள். சமன்பாடுகளின் அமைப்பால் விவரிக்கப்பட்டது:
   c(t) = δ(a(t), c(t-1));
   b(t) = λ(a(t), c(t-1)).
2. மூரின் ஆட்டோமேட்டா. சமன்பாடுகளால் விவரிக்கப்பட்டது:
   c(t) = δ(a(t), c(t-1));
   b(t) = λ(a(t), c(t)).

அந்த. மீலி வகையின் ஒரு ஆட்டோமேட்டன் அதன் முந்தைய நிலையைப் பொறுத்து அதன் உள்ளீட்டு சமிக்ஞை மாறும்போது வெளியீட்டு சமிக்ஞையை உருவாக்குகிறது. இந்த வழக்கில், வெளியீட்டு சமிக்ஞையின் காலம் உள்ளீட்டு சமிக்ஞையின் கால அளவைப் பொறுத்தது அல்ல, ஆனால் அதன் இருப்பை மட்டுமே சார்ந்துள்ளது. மூர் வகை ஆட்டோமேட்டாவில், வெளியீட்டு சமிக்ஞை தற்போதைய நேரத்தில் ஆட்டோமேட்டனின் நிலையைப் பொறுத்தது, அதாவது. இயந்திரம் அதன் நிலையை மாற்றும் வரை ஒரு குறிப்பிட்ட வெளியீட்டு சமிக்ஞையை உருவாக்கும்.

ஆட்டோமேட்டாவைக் குறிப்பிடுவதற்கான முறைகள்

ஆட்டோமேட்டனை வரையறுக்க இரண்டு முக்கிய வழிகள் உள்ளன:

1. வரைபடங்களைப் பயன்படுத்துதல்.
2. மாற்றம் மற்றும் வெளியேறும் அட்டவணைகளைப் பயன்படுத்துதல்.

வரைபடங்கள்

மீலி வரைபடத்திற்கு, ஒத்த மற்றும் வெளியீட்டு எழுத்துக்கள் வளைவுகளில் குறிக்கப்படுகின்றன. வெளியீட்டு எழுத்துக்கள் வளைவுகளுக்கு மேலே எழுதப்பட்டுள்ளன, வெளியீட்டு நிலை முந்தைய நேரத்தில் இயந்திரத்தின் நிலையைப் பொறுத்தது என்பதைக் குறிக்கிறது.

மூர் ஆட்டோமேட்டன் வரைபடத்திற்கு, வளைவுகளில் உள்ளீட்டு எழுத்துக்கள் மட்டுமே எழுதப்படுகின்றன, அதே நேரத்தில் வெளியீட்டு எழுத்துக்கள் செங்குத்துகளுக்கு அருகில் குறிக்கப்படுகின்றன.

முக்கிய குறிப்பு: ஒவ்வொரு உச்சியிலிருந்தும் உள்ளீடு எழுத்துக்கள் உள்ள அளவு வளைவுகள் வெளிவரினால், ஆட்டோமேட்டன் என்று அழைக்கப்படுகிறது. முழுமை. வேறு வார்த்தைகளில் கூறுவதானால், ஒவ்வொரு உள்ளீட்டு கடிதத்திற்கும் ஒவ்வொரு உச்சியில் இருந்து மாற்றங்கள் வரையறுக்கப்பட்டால். எங்கள் உதாரணங்களில், இயந்திரம் மைல்கள் முடிந்தது, மற்றும் இயந்திரம் முரா - பகுதி.
மேலும் ஒரு விஷயம்: உள்ளீட்டு எழுத்துக்களை விட அதிக வளைவுகள் ஒரு உச்சியில் இருந்து வெளியேறினால் (அதாவது, ஒரே உள்ளீட்டு எழுத்துக்களைக் கொண்ட 2 அல்லது அதற்கு மேற்பட்ட வளைவுகள்), அத்தகைய ஆட்டோமேட்டன் என்று அழைக்கப்படுகிறது. தீர்மானமற்றது. முறைப்படுத்தப்பட்ட விளக்கத்தை உருவாக்கும்போது இது நிகழலாம், பின்னர் அதற்கு மாற்றுவது அவசியம் நிர்ணயிக்கப்பட்டதானாகவே, ஆனால் இது எப்போதும் சாத்தியமில்லை. இந்த செயல்முறையின் விளக்கத்தையும் நான் தவிர்க்கிறேன், உடனடியாக ஒரு உறுதியான ஆட்டோமேட்டனை வரைந்தேன்.
வரைபடங்களைப் பற்றியது அவ்வளவுதான்.

மாற்றம் மற்றும் வெளியேறும் அட்டவணைகள்.

கவுண்ட் மிலி TPV

ஏர்ல் மூரின் TPV

ஆட்டோமேட்டன் தொகுப்புக்கான எடுத்துக்காட்டு

உள்ளீடு மற்றும் வெளியீட்டு எழுத்துக்களை நாங்கள் குறியாக்கம் செய்கிறோம்:
A = (a0, a1), இதில் A0 என்பது தருக்க 1 உள்ளீடு R, a1 என்பது உள்ளீடு S இல் தருக்க 1 ஆகும்.
B = (b0, b1), இதில் b0 என்பது Q வெளியீட்டில் தருக்க 0, வெளியீடு Q இல் b1 தருக்க 1 ஆகும்.
மிலி இயந்திரத்திற்கான வரைபடத்தை நாங்கள் உருவாக்குகிறோம்:


இது ஒரு வேடிக்கையான செபுராஷ்கா :-). இப்போது நீங்கள் மாற்றங்கள் மற்றும் வெளியீடுகளின் அட்டவணையை உருவாக்கலாம்:

இந்த அட்டவணையை உண்மையான குறியீடுகளாக மாற்றுவதன் மூலம் எழுதினால், தூண்டுதல் மாற்றங்களின் அட்டவணை நமக்கு கிடைக்கும். பின்னர் அதை எளிமைப்படுத்தலாம்:

இதன் விளைவாக வரும் செயல்பாட்டை வீட்ச் வரைபடத்தில் பயன்படுத்துவோம் மற்றும் குறைக்கலாம்:

என்ன நடந்தது என்பதை எழுதுவோம்:

செயல்பாட்டின் அடிப்படையில் நாங்கள் ஒரு வரைபடத்தை உருவாக்குகிறோம் (உங்கள் வீட்டுப்பாடம் செய்தீர்களா?).

1.1 அடிப்படை கருத்துக்கள்

1.4 மீலி மற்றும் மூர் மாடல்களுக்கு இடையிலான உறவு

1.5 சமமான இயந்திரங்கள். ஆட்டோமேட்டாவின் சமமான மாற்றங்கள்

1.6 ஆட்டோமேட்டனின் உள் நிலைகளின் எண்ணிக்கையைக் குறைத்தல்

நூல் பட்டியல்

அறிமுகம்

"டிஜிட்டல் ஆட்டோமேட்டாவின் அப்ளைடு தியரி" என்ற பிரிவில் சோதனையின் தலைப்பு "சுருக்க டிஜிட்டல் ஆட்டோமேட்டா" ஆகும்.

வேலையின் நோக்கம் சுருக்க டிஜிட்டல் ஆட்டோமேட்டாவின் அடிப்படைக் கருத்துகளை நன்கு அறிந்திருக்க வேண்டும்; சுருக்க ஆட்டோமேட்டா வகைகள்; சுருக்க ஆட்டோமேட்டாவைக் குறிப்பிடுவதற்கான வழிகள்; மீலி மற்றும் மூர் மாதிரிகள் இடையே இணைப்பு; சமமான ஆட்டோமேட்டா மற்றும் ஆட்டோமேட்டாவின் சமமான மாற்றங்கள்; ஆட்டோமேட்டனின் உள் நிலைகளின் எண்ணிக்கை மற்றும் Aufenkamp-Hohn அல்காரிதம் ஆகியவற்றைக் குறைக்கிறது.

1. சுருக்க டிஜிட்டல் ஆட்டோமேட்டா

1.1 அடிப்படை கருத்துக்கள்

ஒரு டிஜிட்டல் இயந்திரம் என்பது ஒரு குறிப்பிட்ட வழிமுறையின்படி தனித்துவமான தகவலைப் பெறும், சேமித்து, மாற்றும் சாதனமாக விளங்குகிறது. ஒரு குறிப்பிட்ட கண்ணோட்டத்தில், உண்மையான சாதனங்கள் (கணினிகள்) மற்றும் சுருக்க அமைப்புகள் (கணித மாதிரிகள்) ஆகிய இரண்டையும் ஆட்டோமேட்டா என வகைப்படுத்தலாம்.

ஒரு ஆட்டோமேட்டன் என்பது பல்வேறு நிலைகளை ஏற்கும் திறன், உள்ளீட்டு சமிக்ஞைகளின் செல்வாக்கின் கீழ் ஒரு மாநிலத்திலிருந்து மற்றொரு மாநிலத்திற்கு மாறுதல் மற்றும் வெளியீட்டு சமிக்ஞைகளை உருவாக்கும் திறன் கொண்ட ஒரு தனித்துவமான தகவல் மாற்றி ஆகும்.

ஆட்டோமேட்டாவின் பொதுவான கோட்பாடு சுருக்கம் மற்றும் கட்டமைப்பு என பிரிக்கப்பட்டுள்ளது.

ஆட்டோமேட்டாவின் சுருக்கக் கோட்பாடு, ஆட்டோமேட்டனின் கட்டமைப்பிலிருந்து சுருக்கம் (அதாவது, அதன் கட்டுமான முறையில் ஆர்வம் இல்லை), வெளிப்புற சூழலுடன் தொடர்புடைய ஆட்டோமேட்டனின் நடத்தையை மட்டுமே ஆய்வு செய்கிறது. ஆட்டோமேட்டாவின் சுருக்கக் கோட்பாடு அல்காரிதம்களின் கோட்பாட்டிற்கு நெருக்கமாக உள்ளது, அடிப்படையில் அதன் மேலும் செயல்படுத்தல்.

சுருக்க ஆட்டோமேட்டா கோட்பாட்டிற்கு மாறாக, கட்டமைப்பு கோட்பாடுஆட்டோமேட்டா தன்னியக்கத்தின் கட்டமைப்பு மற்றும் உள்ளீடு தாக்கங்கள் மற்றும் ஆட்டோமேட்டனின் எதிர்வினைகளின் அமைப்பு ஆகிய இரண்டிலும் ஆர்வமாக உள்ளது. கட்டமைப்புக் கோட்பாடு ஆட்டோமேட்டாவை உருவாக்குவதற்கான முறைகள், உள்ளீட்டு தாக்கங்களை குறியாக்குவதற்கான முறைகள் மற்றும் அவற்றுக்கான ஆட்டோமேட்டனின் எதிர்வினைகள் ஆகியவற்றை ஆய்வு செய்கிறது. ஆட்டோமேட்டாவின் கட்டமைப்புக் கோட்பாடு சுருக்கக் கோட்பாட்டின் தொடர்ச்சி மற்றும் வளர்ச்சியாகும். பூலியன் செயல்பாடுகளின் கருவி மற்றும் ஆட்டோமேட்டாவின் சுருக்கக் கோட்பாட்டின் அடிப்படையில், உண்மையான கணினி தொழில்நுட்ப சாதனங்களின் வளர்ச்சிக்கான பயனுள்ள பரிந்துரைகளை கட்டமைப்புக் கோட்பாடு வழங்குகிறது.

ஒரு சுருக்க டிஜிட்டல் ஆட்டோமேட்டன் (DA) என்பது ஒரு தனித்த கட்டுப்பாட்டு சாதனத்தின் கணித மாதிரி ஆகும்.

சுருக்கம் TA ஆறு கூறுகளைக் கொண்ட ஒரு தொகுப்பால் வரையறுக்கப்படுகிறது:

X=(x 1, x 2,. x n) - உள்ளீட்டு சமிக்ஞைகளின் தொகுப்பு (உள்ளீடு எழுத்துக்கள்);

Y=(y 1, y 2, y m) - வெளியீட்டு சமிக்ஞைகளின் தொகுப்பு (வெளியீட்டு எழுத்துக்கள்);

A = ( a 0 , a 1 , a 2 , a N ) - மாநிலங்களின் தொகுப்பு (மாநிலங்களின் எழுத்துக்கள்);

a o - ஆரம்ப நிலை (a o

- - ஆட்டோமேட்டனின் மாற்றங்களின் செயல்பாடு, காட்சி (XxA) A ஐக் குறிப்பிடுகிறது, அதாவது. கார்ட்டீசியன் தயாரிப்பின் (XxA) எந்த ஜோடி உறுப்புகளையும் A தொகுப்பின் உறுப்புடன் தொடர்புபடுத்துகிறது;

Y, அல்லது காட்சி AY.

ஆட்டோமேட்டன் S, ஒரு குறிப்பிட்ட நிலையில் ஒரு j A, உள்ளீடு சமிக்ஞை x j X தோன்றும்போது, ​​ஒரு குறிப்பிட்ட நிலைக்குச் செல்கிறது a p A. இதை எழுதலாம்: (a i ,X j). வெளியீடு செயல்பாடு

X j).

மாநிலத்தின் கருத்து ஒரு ஆட்டோமேட்டனின் வரையறையில் அறிமுகப்படுத்தப்பட்டது, ஏனெனில் அதன் வெளியீடுகள் ஒரு குறிப்பிட்ட நேரத்தில் உள்ளீடுகளின் நிலையை மட்டுமல்ல, சில வரலாற்றுக்கு முந்தைய காலத்திலும் சார்ந்து இருக்கும் அமைப்புகளின் நடத்தையை விவரிக்க வேண்டிய அவசியம் உள்ளது. அதாவது கணினி உள்ளீடுகளில் முன்பு பெறப்பட்ட சமிக்ஞைகளிலிருந்து. ஒரு நிலை கடந்த காலத்தின் சில நினைவகத்துடன் துல்லியமாக ஒத்துப்போகிறது, இது நேரத்தை ஒரு வெளிப்படையான மாறியாக அகற்ற அனுமதிக்கிறது மற்றும் ஒரு குறிப்பிட்ட நேரத்தில் மாநிலங்கள் மற்றும் உள்ளீடுகளின் செயல்பாடாக வெளியீடுகளை வெளிப்படுத்துகிறது.

X, மற்றும் வெளியீட்டு சேனலில் y (t) = (a (t), x (t)) சமிக்ஞையை வெளியிடவும், a (t+1) = = (a (t),x (t)) . உள்ளீடு மற்றும் மாநிலத்தின் மீது வெளியீட்டு சமிக்ஞையின் சார்பு என்பது நினைவகத்தைக் கொண்டுள்ளது என்று பொருள்.

1.2 சுருக்க ஆட்டோமேட்டா வகைகள்

(a(t), x(t));

a (t+1) = δ (a (t), x (t)). (1-1)

(a(t));

a (t+1) = δ (a (t), x (t)). (1-2)

y 2 (a (t),x (t)); 2(a(t));

a (t+1) =δ (a (t),x (t)).

ஒரு தன்னிச்சையான சுருக்கமான மீலி அல்லது மூர் ஆட்டோமேட்டன் (படம். 1.1.) ஒரு உள்ளீடு மற்றும் ஒரு வெளியீட்டு சேனலைக் கொண்டுள்ளது. ஒரு தன்னிச்சையான சுருக்கமான சி-ஆட்டோமேட்டனில் ஒரு உள்ளீடு மற்றும் இரண்டு வெளியீடு சேனல்கள் உள்ளன (படம் 1.2.).

படம் 1.1 - சுருக்க ஆட்டோமேட்டன்

ஒரு சுருக்கமான மீலி அல்லது மூர் ஆட்டோமேட்டனின் உள்ளீடு, ஆரம்ப நிலை a o க்கு அமைக்கப்பட்டால், x (0), x (1) என்ற உள்ளீட்டு எழுத்துக்களின் குறிப்பிட்ட வரிசை எழுத்துக்களுடன் கடிதம் மூலம் கடிதம் வழங்கப்படுகிறது. என்பது உள்ளீட்டு வார்த்தையாகும், பின்னர் y (0), y (1) என்ற வெளியீட்டு எழுத்துக்களின் எழுத்துக்கள் இயந்திரத்தின் வெளியீட்டில் தொடர்ச்சியாக தோன்றும். - வெளியேறு வார்த்தை. சி-ஆட்டோமேட்டனைப் பொறுத்தவரை, அதன் வெளியீடுகளில் இரண்டு வரிசைகள் தோன்றும்: y 1 (0), y 1 (1),. மற்றும் y 2 (0), y 2 (1),. ஒரு சுருக்கமான C ஆட்டோமேட்டனில், வெளியீட்டு சமிக்ஞை y 2 (t) =

எனவே, சுருக்கக் கோட்பாட்டின் மட்டத்தில், டிஜிட்டல் இயந்திரத்தின் செயல்பாடு உள்ளீட்டு வார்த்தைகளை வெளியீட்டு வார்த்தைகளாக மாற்றுவதாக புரிந்து கொள்ளப்படுகிறது.

முழுமையாக வரையறுக்கப்பட்ட மற்றும் பகுதியளவு ஆட்டோமேட்டா உள்ளன.

முழுமையாக வரையறுக்கப்பட்ட சுருக்க டிஜிட்டல் ஆட்டோமேட்டன் என்பது, அதன் மாற்றம் செயல்பாடு அல்லது வெளியீட்டு செயல்பாடு அல்லது இந்த இரண்டு செயல்பாடுகளும், அனைத்து ஜோடி மாற்றங்களுக்கும் (x i ,a j) வரையறுக்கப்படுகின்றன.

ஒரு சுருக்க டிஜிட்டல் ஆட்டோமேட்டன் அதன் மாறுதல் செயல்பாடு அல்லது வெளியீட்டு செயல்பாடு அல்லது இந்த இரண்டு செயல்பாடுகளும் அனைத்து ஜோடி மாற்றங்களுக்கும் (x i ,a j) வரையறுக்கப்படவில்லை என்றால் பகுதி என்று அழைக்கப்படுகிறது.

ஒரு ஆரம்ப நிலை a o அதன் நிலைகளின் தொகுப்பில் வேறுபடுத்தப்பட்டால் ஒரு சுருக்க டிஜிட்டல் ஆட்டோமேட்டன் ஆரம்பம் என்று அழைக்கப்படுகிறது.

1.3 சுருக்க ஆட்டோமேட்டாவைக் குறிப்பிடுவதற்கான முறைகள்

வரையறுக்கப்பட்ட ஆட்டோமேட்டன் S ஐ வரையறுக்க, தொகுப்பின் அனைத்து கூறுகளையும் விவரிக்க வேண்டியது அவசியம்: S=( X,A,Y,

அட்டவணை முறையில், இயந்திரம் இரண்டு அட்டவணைகள் மூலம் குறிப்பிடப்படுகிறது: ஒரு மாற்றம் அட்டவணை மற்றும் ஒரு வெளியீடு அட்டவணை, அல்லது ஒரு இணைப்பு அணி. தன்னிச்சையான முழுமையாக வரையறுக்கப்பட்ட ஆட்டோமேட்டனின் மாற்றம் அட்டவணை பின்வருமாறு கட்டமைக்கப்பட்டுள்ளது: அட்டவணையின் வரிசைகள் ஆட்டோமேட்டனின் உள்ளீட்டு எழுத்துக்களின் எழுத்துக்களால் குறிக்கப்பட்டுள்ளன, மேலும் அட்டவணையின் நெடுவரிசைகள் மாநிலங்களின் எழுத்துக்களின் எழுத்துக்களால் குறிக்கப்படுகின்றன. தானியங்கி; உள்ளீட்டு சமிக்ஞை x i மற்றும் நிலை a j என குறிக்கப்பட்ட நெடுவரிசையால் குறிக்கப்பட்ட வரிசையின் குறுக்குவெட்டில் அமைந்துள்ள மாற்றம் அட்டவணையின் கலத்தில், a k நிலை வைக்கப்படுகிறது, இது a j கீழ் நிலையிலிருந்து இயந்திரத்தின் மாற்றத்தின் விளைவாகும். உள்ளீடு சமிக்ஞையின் தாக்கம் x i, இது ஒரு k = வெளிப்பாட்டால் தீர்மானிக்கப்படுகிறது