புஷ்டவுன் ஆட்டோமேட்டா (PDA) என்பது கணக்கீட்டின் பல்வேறு அம்சங்களை ஆய்வு செய்ய கோட்பாட்டு கணினி அறிவியலில் பயன்படுத்தப்படும் ஒரு கணக்கீட்டு மாதிரி ஆகும். கணக்கீட்டு சிக்கலான கோட்பாட்டின் பின்னணியில் பிடிஏக்கள் மிகவும் பொருத்தமானவை, அங்கு அவை பல்வேறு வகையான சிக்கல்களைத் தீர்க்க தேவையான கணக்கீட்டு வளங்களைப் புரிந்துகொள்வதற்கான அடிப்படைக் கருவியாகச் செயல்படுகின்றன. இது சம்பந்தமாக, PDA ஒரு பாலிண்ட்ரோம் சரத்தின் மொழியைக் கண்டறிய முடியுமா என்ற கேள்வி இந்த கணக்கீட்டு மாதிரியின் திறன்கள் மற்றும் வரம்புகளை ஆராய்கிறது.
இந்தக் கேள்வியைத் தீர்க்க, பாலிண்ட்ரோம் சரம் என்றால் என்ன என்பதை முதலில் நிறுவ வேண்டும். பாலிண்ட்ரோம் என்பது முன்னும் பின்னும் ஒரே மாதிரியான எழுத்துக்களின் வரிசையாகும். எடுத்துக்காட்டாக, "ரேடார்" மற்றும் "நிலை" இரண்டும் பாலிண்ட்ரோம் சரங்களுக்கு எடுத்துக்காட்டுகள். பாலிண்ட்ரோம் சரங்களின் மொழி கொடுக்கப்பட்ட எழுத்துக்களின் மீது சாத்தியமான அனைத்து பாலிண்ட்ரோம்களையும் கொண்டுள்ளது. கொடுக்கப்பட்ட உள்ளீட்டு சரம் ஒரு பாலிண்ட்ரோமா என்பதை PDA அங்கீகரிக்க முடியுமா அல்லது கண்டறிய முடியுமா என்பதை தீர்மானிப்பது கையில் உள்ள பணியாகும்.
PDA களின் சூழலில், பாலிண்ட்ரோம் சரத்தை அடையாளம் காணும் திறன் PDA இன் கணக்கீட்டு சக்தி மற்றும் பாலிண்ட்ரோம் சரங்களின் குறிப்பிட்ட அம்சங்களைப் பொறுத்தது. பிடிஏக்கள் உள்ளீட்டு சின்னங்களைப் படிப்பதோடு கூடுதலாக ஒரு அடுக்கைக் கையாளும் திறனைக் கொண்டுள்ளன, இது வரையறுக்கப்பட்ட ஆட்டோமேட்டாவுடன் ஒப்பிடும்போது அதிக கணக்கீட்டு சக்தியை அளிக்கிறது. இந்த கூடுதல் திறன், வரையறுக்கப்பட்ட ஆட்டோமேட்டாவால் மட்டும் அங்கீகரிக்க முடியாத சில வகையான மொழிகளை அடையாளம் காண PDA களை அனுமதிக்கிறது.
பாலிண்ட்ரோம் சரங்களைப் பொறுத்தவரை, ஒரு பிடிஏ மூலம் பயன்படுத்தக்கூடிய முக்கிய சொத்து என்னவென்றால், பாலிண்ட்ரோமின் அமைப்பு சமச்சீராக உள்ளது. இந்த சமச்சீரானது PDA ஆனது உள்ளீட்டு சரத்தின் தொடக்கத்திலும் முடிவிலும் உள்ள எழுத்துக்களை ஒப்பிட்டு அதன் அடுக்கைப் பயன்படுத்தி இடையில் உள்ள எழுத்துக்களைக் கண்காணிக்க அனுமதிக்கிறது. எழுத்துகளை சேமிக்கவும் மீட்டெடுக்கவும் அதன் அடுக்கை சரியான முறையில் பயன்படுத்துவதன் மூலம், கொடுக்கப்பட்ட உள்ளீட்டு சரம் பாலிண்ட்ரோமா என்பதை PDA சரிபார்க்க முடியும்.
PDA ஐப் பயன்படுத்தி பாலிண்ட்ரோம் சரங்களைக் கண்டறிவதற்கான செயல்முறை பொதுவாக இரண்டு முனைகளிலிருந்தும் உள்ளீட்டு சரத்தை ஒரே நேரத்தில் கடந்து, எழுத்துக்களை ஒப்பிடுவதற்கு அடுக்கைப் பயன்படுத்துகிறது. ஒவ்வொரு அடியிலும், PDA ஆனது உள்ளீட்டு சரத்தின் இரு முனைகளிலும் உள்ள எழுத்துக்களைப் படித்து, அவை பொருந்துமா என்பதை உறுதிப்படுத்த அவற்றை ஒப்பிடலாம். பொருத்தமின்மை கண்டறியப்பட்டாலோ அல்லது முழு சரமும் செயலாக்கப்பட்டு ஸ்டாக் காலியாக இருந்தாலோ, PDA உள்ளீடு சரத்தை பாலிண்ட்ரோம் அல்ல என நிராகரிக்கலாம். மறுபுறம், பிடிஏ முழு உள்ளீட்டு சரத்தையும் வெற்றிகரமாக செயல்படுத்தி, ஸ்டேக் காலியாக இருந்தால், உள்ளீட்டு சரம் பாலிண்ட்ரோமாக ஏற்றுக்கொள்ளப்படும்.
ஒரு PDA ஆனது பாலிண்ட்ரோம் சரங்களின் மொழியை அதன் ஸ்டேக் அடிப்படையிலான திறன்களை பயன்படுத்தி சமச்சீர் முறையில் எழுத்துக்களை ஒப்பிடுவதன் மூலம் கண்டறிய முடியும். பாலிண்ட்ரோம்கள் போன்ற குறிப்பிட்ட கட்டமைப்பு பண்புகளை வெளிப்படுத்தும் சில வகையான மொழிகளை அங்கீகரிப்பதில் பிடிஏக்களின் கணக்கீட்டு ஆற்றலை இந்த செயல்முறை காட்டுகிறது.
தொடர்பான பிற சமீபத்திய கேள்விகள் மற்றும் பதில்கள் EITC/IS/CCTF கணக்கீட்டு சிக்கலான கோட்பாடு அடிப்படைகள்:
- சாம்ஸ்கியின் இலக்கண சாதாரண வடிவம் எப்போதும் தீர்மானிக்கக்கூடியதா?
- மறுநிகழ்வைப் பயன்படுத்தி வழக்கமான வெளிப்பாட்டை வரையறுக்க முடியுமா?
- FSM ஆக அல்லது பிரதிநிதித்துவம் செய்வது எப்படி?
- பல்லுறுப்புக்கோவை-நேரச் சரிபார்ப்பாளர்களுடனான முடிவெடுக்கும் சிக்கல்களின் வகுப்பாக NP இன் வரையறைக்கும், P வகுப்பில் உள்ள சிக்கல்களும் பல்லுறுப்புக்கோவை-நேர சரிபார்ப்பாளர்களைக் கொண்டிருப்பதற்கும் இடையே முரண்பாடு உள்ளதா?
- சரிபார்ப்பானது வகுப்பு P பல்லுறுப்புக்கோவைக்கானதா?
- ஃபயர்வால் உள்ளமைவில் நிலை மாற்றங்கள் மற்றும் செயல்களைப் பிரதிநிதித்துவப்படுத்த, ஒரு Nondeterministic Finite Automaton (NFA) பயன்படுத்த முடியுமா?
- மல்டிடேப் TN இல் மூன்று டேப்களைப் பயன்படுத்துவது ஒற்றை டேப் டைம் t2(சதுரம்) அல்லது t3(க்யூப்)க்கு சமமா? வேறு வார்த்தைகளில் கூறுவதானால், நேர சிக்கலானது டேப்களின் எண்ணிக்கையுடன் நேரடியாக தொடர்புடையதா?
- நிலையான புள்ளி வரையறையில் உள்ள மதிப்பு, செயல்பாட்டின் தொடர்ச்சியான பயன்பாட்டின் லிம் என்றால், அதை இன்னும் நிலையான புள்ளி என்று அழைக்கலாமா? காட்டப்பட்டுள்ள எடுத்துக்காட்டில், 4->4க்கு பதிலாக 4->3.9, 3.9->3.99, 3.99->3.999, … 4 என்பது நிலையான புள்ளியா?
- தீர்மானிக்கக்கூடிய மொழியை விவரிக்கும் இரண்டு டிஎம்கள் எங்களிடம் இருந்தால், சமமான கேள்வி இன்னும் தீர்மானிக்க முடியாததா?
- டேப்பின் தொடக்கத்தைக் கண்டறியும் விஷயத்தில், வலதுபுறமாக மாற்றுவதற்குப் பதிலாக புதிய T1=$T டேப்பைப் பயன்படுத்தி ஆரம்பிக்கலாமா?
EITC/IS/CCTF கணக்கீட்டு சிக்கலான கோட்பாடு அடிப்படைகளில் கூடுதல் கேள்விகள் மற்றும் பதில்களைக் காண்க