Кантэкстна-свабодная мова - гэта тып фармальнай мовы, які можа быць апісаны з дапамогай кантэкстна-свабоднай граматыкі. У галіне тэорыі складанасці вылічэнняў кантэкстна-свабодныя мовы гуляюць важную ролю ў разуменні складанасці праблем і межаў вылічэнняў. Каб цалкам зразумець канцэпцыю кантэкстна-свабоднай мовы, вельмі важна вывучыць яе вызначэнне і кампаненты кантэкстна-свабоднай граматыкі.
Кантэкстна-свабодная мова вызначаецца як набор радкоў, якія могуць быць згенераваныя кантэкстна-свабоднай граматыкай. Кантэкстна-свабодная граматыка складаецца з чатырох кампанентаў: набору нетэрмінальных сімвалаў, набору тэрмінальных сімвалаў, набору правілаў вытворчасці і пачатковага сімвала.
Нетэрмінальныя сімвалы ўяўляюць сабой абстрактныя сутнасці, якія могуць быць пашыраны або заменены іншымі сімваламі. Гэтыя сімвалы, як правіла, прадстаўлены вялікімі літарамі. Напрыклад, у кантэкстна-свабоднай граматыцы для арыфметычных выразаў у нас могуць быць нетэрмінальныя сімвалы, такія як E (прадстаўляючы выраз), T (прадстаўляючы тэрмін) і F (прадстаўляючы множнік).
Тэрмінальныя сімвалы, наадварот, з'яўляюцца элементарнымі адзінкамі мовы. Гэтыя сімвалы не могуць быць пашыраны і звычайна прадстаўлены малымі літарамі або іншымі сімваламі. У кантэксце арыфметычных выразаў тэрмінальныя сімвалы могуць уключаць лічбы (напрыклад, 0, 1, 2) і арыфметычныя аператары (напрыклад, +, -, *, /).
Правілы вытворчасці вызначаюць, як нетэрмінальныя сімвалы могуць быць пашыраны або заменены іншымі сімваламі. Кожнае вытворчае правіла складаецца з нетэрмінальнага сімвала з левага боку і паслядоўнасці сімвалаў (як нетэрмінальных, так і тэрмінальных) з правага боку. Гэтыя правілы вызначаюць магчымыя пераўтварэнні або паходжання, якія могуць прымяняцца для стварэння сапраўдных радкоў у мове. Напрыклад, у кантэкстна-свабоднай граматыцы для арыфметычных выразаў у нас могуць быць такія правілы вытворчасці, як E -> E + T (паказвае, што выраз можа быць пашыраны шляхам дадання члена) або T -> F (паказвае, што тэрмін можа быць замяняецца множнікам).
Пачатковы сімвал уяўляе сабой пачатковы нетэрмінальны сімвал, з якога пачынаецца генерацыя сапраўдных радкоў. Звычайна ён пазначаецца S. У кантэксце арыфметычных выразаў сімвал пачатку можа быць E, паказваючы, што стварэнне сапраўдных выразаў пачынаецца з выразу.
Каб праілюстраваць канцэпцыю кантэкстна-свабоднай мовы і яе кампанентаў, давайце разгледзім простую кантэкстна-свабодную граматыку для мовы, якая стварае збалансаваныя круглыя дужкі. Граматыка складаецца з наступных кампанентаў:
Нетэрмінальныя сімвалы: S (сімвал пачатку)
Сімвалы тэрміналаў: (, )
Правілы вытворчасці: S -> (S) | СС | ε (дзе ε ўяўляе сабой пусты радок)
У гэтай граматыцы нетэрмінальны сімвал S уяўляе сабой радок збалансаваных круглых дужак. Правілы вытворчасці вызначаюць, што S можа быць пашыраны шляхам заключэння іншага S у круглыя дужкі ((S)), аб'яднання двух S (SS) або стварэння пустога радка (ε).
Выкарыстоўваючы гэтую граматыку, мы можам генераваць правільныя радкі на мове збалансаваных круглых дужак. Напрыклад, пачынаючы з пачатковага сімвала S, мы можам прымяніць правілы вытворчасці для атрымання радка ((())). Гэты радок уяўляе сабой паслядоўнасць збалансаваных круглых дужак.
Кантэкстна-свабодная мова вызначаецца як набор радкоў, якія могуць быць згенераваныя кантэкстна-свабоднай граматыкай. Кампаненты кантэкстна-свабоднай граматыкі ўключаюць нетэрмінальныя сімвалы, тэрмінальныя сімвалы, правілы вытворчасці і сімвал пачатку. Нетэрмінальныя сімвалы ўяўляюць сабой абстрактныя сутнасці, якія можна пашырыць або замяніць, у той час як тэрмінальныя сімвалы з'яўляюцца элементарнымі адзінкамі мовы. Правілы вытворчасці вызначаюць магчымыя пераўтварэнні або вывядзення, а пачатковы сімвал уяўляе сабой пачатковы нетэрмінальны сімвал для генерацыі сапраўдных радкоў.
Іншыя апошнія пытанні і адказы адносна Мовы, якія адчуваюць кантэкст:
- Што значыць, што адна мова больш магутная за іншую?
- Ці заўсёды вырашальная нармальная форма граматыкі Хомскага?
- Ці існуюць сучасныя метады распазнання тыпу 0? Ці чакаем мы, што квантавыя кампутары зробяць гэта магчымым?
- Чаму ў прыкладзе мовы D уласцівасць перапампоўвання не выконваецца для радка S = 0^P 1^P 0^P 1^P?
- Якія два выпадкі трэба ўлічваць пры падзеле радка, каб прымяніць лему пра накачку?
- У прыкладзе мовы B, чаму ўласцівасць pumping не выконваецца для радка a^Pb^Pc^P?
- Якія ўмовы павінны быць выкананы, каб уласцівасць перапампоўвання захоўвалася?
- Як можна выкарыстоўваць лему пра накачку для CFL, каб даказаць, што мова не з'яўляецца кантэкстна-свабоднай?
- Якія ўмовы павінны быць выкананы, каб мова лічылася кантэкстна-свабоднай у адпаведнасці з лемай пра накачку для кантэкстна-свабодных моў?
- Растлумачце канцэпцыю рэкурсіі ў кантэксце кантэкстна-свабоднай граматыкі і тое, як яна дазваляе ствараць доўгія радкі.
Глядзіце больш пытанняў і адказаў у Кантэкстна-залежных мовах