Чаму мова U = 0^n1^n (n>=0) нерэгулярная?

/ / Апублікавана ў кібербяспека, Асновы тэорыі складанасці вылічэнняў EITC/IS/CCTF, Аўтаматы адціскання, КПК: Аўтаматы націску

Пытанне, ці мова U = \{0^n1^n \mid n \geq 0\} з'яўляецца фундаментальнай тэмай у галіне тэорыі складанасці вылічэнняў, асабліва пры вывучэнні фармальных моў і тэорыі аўтаматаў. Разуменне гэтай канцэпцыі патрабуе цвёрдага разумення азначэнняў і ўласцівасцей звычайных моў і вылічальных мадэляў, якія іх распазнаюць.

Рэгулярныя мовы і канчатковыя аўтаматы

Рэгулярныя мовы - гэта клас моў, якія можна распазнаць канечнымі аўтаматамі, якія з'яўляюцца абстрактнымі машынамі з канечным лікам станаў. Гэтыя мовы таксама могуць быць апісаны з дапамогай рэгулярных выразаў і могуць быць створаны звычайнымі граматыкамі. Ключавой характарыстыкай звычайных моў з'яўляецца тое, што іх можна распазнаць дэтэрмінаванымі канечнымі аўтаматамі (DFA) або недэтэрмінаванымі канечнымі аўтаматамі (NFA). DFA складаецца з канчатковага набору станаў, набору ўваходных сімвалаў, функцыі пераходу, якая адлюстроўвае пары стан-сімвал у станы, пачатковага стану і набору прымальных станаў.

Магутнасць канечных аўтаматаў абмежавана іх абмежаванай памяццю. Яны не могуць лічыць больш за фіксаваную колькасць, што азначае, што яны не могуць адсочваць адвольную колькасць уваходжанняў пэўнага сімвала, калі колькасць не абмежавана колькасцю станаў у аўтаматы. Гэта абмежаванне важна пры разглядзе такіх моў, як U = \{0^n1^n \mid n \geq 0\}.

Нерэгулярнасць U = \{0^n1^n \mid n \geq 0\}

Каб вызначыць, ці з'яўляецца мова звычайнай, можна выкарыстаць лему прапампоўкі для звычайных моў. Лема накачкі забяспечвае ўласцівасць, якой павінны задавальняць усе рэгулярныя мовы, і яна часта выкарыстоўваецца, каб паказаць, што пэўныя мовы нерэгулярныя, дэманструючы, што яны не задавальняюць гэтай уласцівасці.

Лема пра накачку сцвярджае, што для любой звычайнай мовы L, існуе даўжыня накачкі p \geq 1 такі, што любы радок s in L з даўжынёй |s| \geq с можна падзяліць на тры часткі, s = xyz, якія задавальняюць наступным умовам:
1. |xy| \leq с,
2. |у| \geq 1, і
3. для ўсіх i \geq 0, радок ху^із знаходзіцца ў L.

Каб паказаць гэта з дапамогай лемы пра накачку U = \{0^n1^n \mid n \geq 0\} не з'яўляецца рэгулярным, выкажам здагадку, што для супярэчнасці U з'яўляецца рэгулярным. Тады існуе даўжыня накачкі p такі, што любы радок s in U з |s| \geq с можна падзяліць на часткі х, у, г якія задавальняюць умовам лемы пра накачку.

Разгледзім радок s = 0^p1^p in U. Згодна з лемай пра накачку, s можна падзяліць на х, у, г такі, што |xy| \leq с і |у| \geq 1, з |xy| \leq с, падрадок y складаецца толькі з 0. Такім чынам, х = 0^а, у = 0^b, і z = 0^{pab}1^p дзе 1 \leq b \leq p.

Зараз разгледзім радок xy^2z = 0^a0^{2b}0^{pab}1^p = 0^{p+b}1^p. Колькасць 0 з'яўляецца р + б, што больш, чым p, пры гэтым колькасць 1с застаецца p, Такім чынам, xy^2z \notin U таму што лікі 0 і 1 не роўныя. Гэта супярэчнасць паказвае, што дапушчэнне, што U рэгулярны - ілжывы. Такім чынам, U = \{0^n1^n \mid n \geq 0\} не з'яўляецца звычайнай мовай.

Кантэкстна-свабодныя мовы і аўтаматы, якія расціскаюцца

Мова U = \{0^n1^n \mid n \geq 0\} аднак з'яўляецца кантэкстна-свабоднай мовай (CFL). Кантэкстна-свабодныя мовы распазнаюцца аўтаматамі адціскання (PDA), якія больш магутныя, чым канчатковыя аўтаматы, таму што яны могуць выкарыстоўваць стэк для захоўвання неабмежаванай колькасці інфармацыі. Гэтая дадатковая памяць дазваляе КПК адсочваць колькасць 0 і 1 у мове U.

КПК для U = \{0^n1^n \mid n \geq 0\} працуе наступным чынам:
1. Ён запускаецца ў пачатковым стане і счытвае 0 з уваходу, перамяшчаючы кожны 0 у стэк.
2. Пасля чытання першага 1 ён пераходзіць у новы стан і пачынае выскокваць нулі са стэка за кожны 0, прачытаны з уводу.
3. Калі стэк пусты, калі ўвод вычарпаны, КПК прымае ўвод, паказваючы, што колькасць нулёў супадае з колькасцю 0.

Гэты механізм выкарыстання стэка для супастаўлення колькасці 0 і 1 дэманструе здольнасць КПК распазнаваць мовы, якія не з'яўляюцца звычайнымі, але кантэкстна-свабоднымі.

Прыклады і далейшыя наступствы

Разгледзім прыклад радка s = 000111 ад мовы U. КПК будзе апрацоўваць гэты радок, падштурхоўваючы кожны 0 у стэк, калі ён іх счытвае. Пасля прачытання трох нуляў стэк будзе ўтрымліваць тры сімвалы, кожны з якіх уяўляе сабой 0. Калі КПК счытвае наступныя 0, ён выцягвае па адным сімвале са стэка на кожную 1. Калі ўвод цалкам прачытаны, стэк пусты, што паказвае што ўвод прыняты.

Наадварот, канечны аўтамат не зможа адсочваць колькасць нуляў і адзінак, бо яму не хапае механізму стэка. Без магчымасці захоўваць і атрымліваць неабмежаваную колькасць сімвалаў канечны аўтамат не можа гарантаваць, што колькасць нулёў роўная колькасці 0, што прыводзіць да яго няздольнасці распазнаваць мову U.

Адрозненне паміж звычайнымі і кантэкстна-свабоднымі мовамі важна ў тэарэтычнай інфарматыцы і мае практычныя наступствы ў такіх галінах, як праектаванне мовы праграмавання і аналіз. Кантэкстна-свабодныя граматыкі, якія ствараюць кантэкстна-свабодныя мовы, шырока выкарыстоўваюцца ў вызначэнні сінтаксісу моў праграмавання. Здольнасць эфектыўна распазнаваць кантэкстна-свабодныя мовы з дапамогай КПК ляжыць у аснове распрацоўкі аналізатараў, якія з'яўляюцца фундаментальнымі для кампілятараў і інтэрпрэтатараў.

Нерэгулярнасць U = \{0^n1^n \mid n \geq 0\} падкрэслівае абмежаванні канечных аўтаматаў і падкрэслівае неабходнасць больш магутных вылічальных мадэляў, такіх як аўтаматы з адцісканнем, каб распазнаваць больш шырокі клас моў. Гэта адрозненне не проста тэарэтычнае, але мае глыбокія наступствы ў практычным распрацоўцы і рэалізацыі моў праграмавання і інструментаў, якія іх апрацоўваюць.

Іншыя апошнія пытанні і адказы адносна Асновы тэорыі складанасці вылічэнняў EITC/IS/CCTF:

Больш пытанняў і адказаў глядзіце ў раздзеле "Асновы тэорыі вылічальнай складанасці" EITC/IS/CCTF

Яшчэ пытанні і адказы:

тэгі: , , , , ,