கொடுக்கப்பட்ட சரம் சூழல் இல்லாத இலக்கணத்தால் ஏற்றுக்கொள்ளப்படுகிறதா என்பதை தீர்மானிக்க முடியுமா? இந்த பிரச்சனை தீர்க்கப்படுமா?

/ / வெளியிடப்பட்ட சைபர், EITC/IS/CCTF கணக்கீட்டு சிக்கலான கோட்பாடு அடிப்படைகள், தீர்மானித்தல், சூழல் இல்லாத மொழிகள் தொடர்பான சிக்கல்கள், தேர்வு ஆய்வு

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

சூழல் இல்லாத இலக்கணம் என்பது ஒரு மொழியில் சரங்களை எவ்வாறு உருவாக்குவது என்பதை விவரிக்கும் உற்பத்தி விதிகளின் தொகுப்பைக் கொண்ட ஒரு முறையான அமைப்பாகும். இது ஒரு டூப்பிள் (V, Σ, R, S) மூலம் வரையறுக்கப்படுகிறது, அங்கு V என்பது முனையமற்ற குறியீடுகளின் தொகுப்பாகும், Σ என்பது முனையக் குறியீடுகளின் தொகுப்பாகும், R என்பது உற்பத்தி விதிகளின் தொகுப்பு மற்றும் S என்பது தொடக்கக் குறியீடு. சூழல் இல்லாத இலக்கணத்தால் உருவாக்கப்பட்ட மொழி என்பது உற்பத்தி விதிகளைப் பயன்படுத்தி தொடக்கக் குறியீட்டிலிருந்து பெறக்கூடிய அனைத்து சரங்களின் தொகுப்பாகும்.

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

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

பின்வரும் எடுத்துக்காட்டைக் கவனியுங்கள்: உற்பத்தி விதிகளுடன் சூழல் இல்லாத இலக்கணம் எங்களிடம் உள்ளது என்று வைத்துக்கொள்வோம்:
எஸ் -> ஏபி
A -> a
பி -> பி

இந்த இலக்கணத்தால் "ab" சரம் ஏற்றுக்கொள்ளப்பட்டதா என்பதை நாம் தீர்மானிக்க விரும்பினால், நாம் CYK அல்காரிதத்தைப் பயன்படுத்தலாம். உள்ளீட்டு சரத்தில் உள்ள ஒவ்வொரு எழுத்துக்கும் ஒன்று என இரண்டு கலங்களைக் கொண்ட அட்டவணையை அல்காரிதம் உருவாக்குகிறது. அட்டவணை பின்வருமாறு தெரிகிறது:

| 1 | 2 |
—+—+—+
1 | A | எஸ் |
—+—+—+
2 | | பி |
—+—+—+

கீழ் வரிசையில் இருந்து தொடங்கி, கலத்தில் (2,2) முனையம் அல்லாத B இருப்பதைக் காணலாம், இது உற்பத்தி விதி B -> b மூலம் உருவாக்கப்படுகிறது. மேல் வரிசை வரை நகரும் போது, ​​செல் (1,2) இல் டெர்மினல் அல்லாத S இருப்பதைக் காண்கிறோம், இது S -> AB என்ற உற்பத்தி விதியால் உருவாக்கப்படுகிறது. இறுதியாக, கலத்தில் (1,1) முனையம் அல்லாத A உள்ளது, இது உற்பத்தி விதி A -> a மூலம் உருவாக்கப்படுகிறது. தொடக்கக் குறியீடு S மேல் வலது கலத்தில் தோன்றுவதால், "ab" சரம் இலக்கணத்தால் ஏற்றுக்கொள்ளப்பட்டது என்று நாம் முடிவு செய்யலாம்.

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

தொடர்பான பிற சமீபத்திய கேள்விகள் மற்றும் பதில்கள் தீர்மானித்தல்:

மேலும் கேள்விகள் மற்றும் பதில்களை Decidability இல் பார்க்கவும்

மேலும் கேள்விகள் மற்றும் பதில்கள்:

குறித்துள்ளார்: