Siurbimo savybė, dar žinoma kaip siurbimo lema, yra pagrindinė skaičiavimo sudėtingumo teorijos priemonė, skirta kontekstui jautrioms kalboms analizuoti. Tai padeda nustatyti, ar kalba yra jautri kontekstui, pateikdama būtiną sąlygą, kuri turi būti taikoma visoms kalbos eilutėms. Tačiau kalbant apie B ir eilutę a^Pb^Pc^P, siurbimo savybė negalioja.
Norėdami suprasti, kodėl siurbimo ypatybė negalioja šiai konkrečiai eilutei, pirmiausia peržvelkime į kontekstą jautrių kalbų siurbimo lemą. Pagal lemą, jei kalba L yra jautri kontekstui, tada egzistuoja pastovi n (siurbimo ilgis), kad bet kuri eilutė w L su |w| ≥ n gali būti suskirstytas į penkias dalis: w = uvxyz, tenkinant šias sąlygas:
1. |vxy| ≤ n
2. |vy| ≥ 1
3. Jei visi i ≥ 0, eilutė uv^ixy^iz taip pat yra L.
Dabar panagrinėkime eilutę a^Pb^Pc^P, kur P yra pirminis skaičius. Šią eilutę sudaro „a“ seka, po kurios eina toks pat skaičius „b“ ir „c“. Tarkime, kad šią eilutę padaliname į penkias dalis taip w = uvxyz, kur |vxy| ≤ n ir |vy| ≥ 1.
Šiuo atveju, kadangi siurbimo ilgis n yra pastovus, negalima pasirinkti pertvaros, kuri tenkintų siurbimo lemos sąlygas. Taip yra todėl, kad „a“, „b“ ir „c“ skaičius eilutėje yra fiksuotas ir lygus P, kuris yra pirminis skaičius. Todėl neįmanoma padalyti eilutės į penkias dalis taip, kad „a“, „b“ ir „c“ skaičius pumpuojamose eilutėse išliktų toks pat.
Pavyzdžiui, panagrinėkime galimą skaidinį, kuriame vxy susideda tik iš 'a'. Šiuo atveju, padidinus „a“ eksponentą, eilutė, kurios „a“ skaičius skiriasi nuo „b“ ir „c“, pažeidžia sąlygą, kad visos pumpuojamos eilutės turi būti kalba. Panašiai dėl bet kokios kitos galimos pertvaros būtų pažeistos siurbimo lemos sąlygos.
Todėl galime daryti išvadą, kad siurbimo savybė negalioja eilutei a^Pb^Pc^P kalbos B pavyzdyje. Tai reiškia, kad kalba B, kuri apima a^Pb^Pc^P formos eilutes, nėra kontekstui jautri kalba.
Eilutė a^Pb^Pc^P neatitinka siurbimo lemos sąlygų kontekstui jautrioms kalboms dėl jos fiksuoto ir pirminio skaičiaus „a“, „b“ ir „c“. Šis siurbimo savybės pažeidimas rodo, kad B kalba, kuri apima šią eilutę, nėra kontekstui jautri kalba.
Kiti naujausi klausimai ir atsakymai apie Jautrios kontekstui kalbos:
- Ar Chomsky gramatikos normalioji forma visada yra išsprendžiama?
- Ar yra dabartinių 0 tipo atpažinimo metodų? Ar tikimės, kad kvantiniai kompiuteriai tai padarys įmanoma?
- Kodėl D kalbos pavyzdyje siurbimo savybė negalioja eilutei S = 0^P 1^P 0^P 1^P?
- Į kokius du atvejus reikia atsižvelgti dalijant eilutę, kad būtų taikoma siurbimo lema?
- Kokios sąlygos turi būti įvykdytos, kad siurbimo turtas išsilaikytų?
- Kaip galima naudoti CFL siurbimo lemą siekiant įrodyti, kad kalba nėra be konteksto?
- Kokios sąlygos turi būti įvykdytos, kad kalba būtų laikoma be konteksto pagal bekontekstinių kalbų lemą?
- Paaiškinkite rekursijos sąvoką bekontekstinės gramatikos kontekste ir kaip ji leidžia generuoti ilgas eilutes.
- Kas yra analizavimo medis ir kaip jis naudojamas bekontekstinės gramatikos sugeneruotos eilutės struktūrai pavaizduoti?
- Kaip apibrėžiama bekontekstinė kalba ir kokie yra bekontekstinės gramatikos komponentai?
Peržiūrėkite daugiau klausimų ir atsakymų skiltyje Kontekstui jautrios kalbos