மொழி B இன் எடுத்துக்காட்டில், a^Pb^Pc^P சரத்திற்கு பம்ப் செய்யும் பண்பு ஏன் இல்லை?
பம்பிங் லெம்மா என்றும் அழைக்கப்படும் பம்பிங் பண்பு, சூழல்-உணர்திறன் மொழிகளை பகுப்பாய்வு செய்வதற்கான கணக்கீட்டு சிக்கலான கோட்பாட்டின் துறையில் ஒரு அடிப்படை கருவியாகும். மொழியின் அனைத்து சரங்களுக்கும் தேவையான நிபந்தனையை வழங்குவதன் மூலம் ஒரு மொழி சூழல் உணர்திறன் உள்ளதா என்பதை தீர்மானிக்க உதவுகிறது. இருப்பினும், மொழி B மற்றும் சரம் a^Pb^Pc^P விஷயத்தில், பம்ப் செய்யும் பண்பு இல்லை.
இந்த குறிப்பிட்ட சரத்திற்கு பம்பிங் பண்பு ஏன் இல்லை என்பதைப் புரிந்து கொள்ள, முதலில் சூழல் உணர்திறன் மொழிகளுக்கான பம்ப் லெம்மாவை மதிப்பாய்வு செய்வோம். லெம்மாவின் படி, ஒரு மொழி L சூழல் உணர்திறன் கொண்டதாக இருந்தால், L இல் உள்ள எந்த சரமும் |w| உடன் n (உந்தி நீளம்) இருக்கும் ≥ n ஐ ஐந்து பகுதிகளாகப் பிரிக்கலாம்: w = uvxyz, பின்வரும் நிபந்தனைகளைப் பூர்த்தி செய்கிறது:
1. |vxy| ≤ என்
2. |vy| ≥ 1
3. அனைத்து i ≥ 0 க்கும், uv^ixy^iz என்ற சரம் L இல் உள்ளது.
இப்போது, சரம் a^Pb^Pc^P ஐக் கருத்தில் கொள்வோம், இங்கு P என்பது பகா எண். இந்த சரம் 'a' களின் வரிசையையும் தொடர்ந்து அதே எண்ணிக்கையிலான 'b' மற்றும் 'c'களையும் கொண்டுள்ளது. இந்த சரத்தை w = uvxyz என ஐந்து பகுதிகளாகப் பிரிக்கிறோம், அங்கு |vxy| ≤ n மற்றும் |vy| ≥ 1.
இந்த வழக்கில், உந்தி நீளம் n ஒரு மாறிலியாக இருப்பதால், உந்தி லெம்மாவின் நிபந்தனைகளை பூர்த்தி செய்யும் பகிர்வைத் தேர்வு செய்ய முடியாது. ஏனெனில் சரத்தில் உள்ள 'a'கள், 'b'கள் மற்றும் 'c'களின் எண்ணிக்கை நிலையானது மற்றும் P க்கு சமமானது, இது பகா எண்ணாகும். எனவே, பம்ப் செய்யப்பட்ட சரங்களில் உள்ள 'a's, 'b's மற்றும் 'c'களின் எண்ணிக்கை ஒரே மாதிரியாக இருக்கும் வகையில் சரத்தை ஐந்து பகுதிகளாகப் பிரிக்க முடியாது.
எடுத்துக்காட்டாக, vxy ஆனது 'a'களை மட்டுமே கொண்டிருக்கும் சாத்தியமான பகிர்வைக் கருத்தில் கொள்வோம். இந்த நிலையில், 'a' இன் அடுக்கு அதிகரிப்பதன் மூலம் பம்ப் செய்வது, 'b' மற்றும் 'c' உடன் ஒப்பிடும்போது, 'a' இன் வேறுபட்ட எண்ணிக்கையைக் கொண்ட ஒரு சரத்தை உருவாக்கும், இது அனைத்து பம்ப் செய்யப்பட்ட சரங்களும் மொழியில் இருக்க வேண்டும் என்ற நிபந்தனையை மீறும். இதேபோல், வேறு ஏதேனும் சாத்தியமான பகிர்வு பம்ப் லெம்மா நிபந்தனைகளை மீறுவதற்கு வழிவகுக்கும்.
எனவே, பி மொழியின் எடுத்துக்காட்டில் உள்ள சரம் a^Pb^Pc^P க்கு பம்ப் செய்யும் பண்பு இல்லை என்று நாம் முடிவு செய்யலாம். இதன் பொருள் A^Pb^Pc^P வடிவத்தின் சரங்களை உள்ளடக்கிய மொழி B, சூழல் உணர்திறன் மொழி அல்ல.
சரம் a^Pb^Pc^P 'a's, 'b's மற்றும் 'c'களின் நிலையான மற்றும் பிரதான எண் காரணமாக சூழல் உணர்திறன் மொழிகளுக்கான பம்ப் லெம்மாவின் நிபந்தனைகளை பூர்த்தி செய்யவில்லை. பம்பிங் சொத்தின் இந்த மீறல், இந்த சரத்தை உள்ளடக்கிய மொழி B, சூழல் உணர்திறன் மொழி அல்ல என்பதைக் குறிக்கிறது.
தொடர்பான பிற சமீபத்திய கேள்விகள் மற்றும் பதில்கள் சூழல் உணர்திறன் மொழிகள்:
- சாம்ஸ்கியின் இலக்கண சாதாரண வடிவம் எப்போதும் தீர்மானிக்கக்கூடியதா?
- Type-0 ஐ அங்கீகரிப்பதற்கான தற்போதைய முறைகள் உள்ளதா? குவாண்டம் கணினிகள் அதை சாத்தியமாக்கும் என்று எதிர்பார்க்கிறோமா?
- மொழி D இன் எடுத்துக்காட்டில், S = 0^P 1^P 0^P 1^P சரத்திற்கு பம்ப் செய்யும் பண்பு ஏன் இல்லை?
- பம்ப்பிங் லெம்மாவைப் பயன்படுத்த சரத்தைப் பிரிக்கும்போது கருத்தில் கொள்ள வேண்டிய இரண்டு நிகழ்வுகள் யாவை?
- பம்பிங் சொத்தை வைத்திருப்பதற்கு என்ன நிபந்தனைகளை பூர்த்தி செய்ய வேண்டும்?
- ஒரு மொழி சூழல் இல்லாதது என்பதை நிரூபிக்க CFLகளுக்கான பம்ப்பிங் லெம்மாவை எவ்வாறு பயன்படுத்தலாம்?
- சூழல்-இல்லாத மொழிகளுக்கான பம்ப் லெம்மாவின் படி ஒரு மொழி சூழல்-இல்லாததாகக் கருதப்படுவதற்கு என்ன நிபந்தனைகள் பூர்த்தி செய்யப்பட வேண்டும்?
- சூழல் இல்லாத இலக்கணங்களின் பின்னணியில் மறுநிகழ்வு என்ற கருத்தை விளக்கவும் மற்றும் நீண்ட சரங்களை உருவாக்குவதற்கு அது எவ்வாறு அனுமதிக்கிறது.
- பாகுபடுத்தும் மரம் என்றால் என்ன, சூழல் இல்லாத இலக்கணத்தால் உருவாக்கப்பட்ட சரத்தின் கட்டமைப்பைக் குறிக்க இது எவ்வாறு பயன்படுத்தப்படுகிறது?
- சூழல்-இலவச மொழி எவ்வாறு வரையறுக்கப்படுகிறது, மற்றும் சூழல் இல்லாத இலக்கணத்தின் கூறுகள் என்ன?
சூழல் உணர்திறன் மொழிகளில் மேலும் கேள்விகள் மற்றும் பதில்களைக் காண்க