Біртұтас емес контекстсіз грамматикалардың (CFG) асимптоталық тығыздығы

бірмәнді емес CFG-лердің барлығы CFGs ?

Екі жиынтық теңдестірілген шексіз болғандықтан, қатынасы анық емес. Бірақ асимптоталық тығыздық туралы :

$$\lim_{n \mapsto \infty}\frac {\# \text{ ambiguous CFG of size} < n} {\# \text{ CFG of size} < n}$$

терминал мен терминал емес символдар тіркелген есептелетін жиынтықтан келеді.

Грамматиканың өлшемі грамматика өлшемдерінің кез келген ақылға қонымды ұғымы, мысалы:

  1. өндірістік ережелердегі айнымалылар мен терминалдардың жалпы саны немесе
  2. айнымалы көріністердің жалпы саны немесе
  3. өндірістік ережелердің жалпы саны немесе
  4. түрлі айнымалылардың саны.

(Мен өлшемнің анықтамасы жауапқа әсер етпейді деп ойлаймын).

9
@Martin, егер абай болмаса, шексіз көп мөлшерде синтаксистік түрде әртүрлі грамматикалар болуы мүмкін және бұл қатынас мағынасы болмайды. Қауіпсіз жолы - кейбір грамматиканың бекітілген кодтауының бит ұзындығын санау.
қосылды автор Swinders, көзі
Грамматика өлшемін анықтау сізге берілген өлшемдердің барлық грамматикаларын санауға мүмкіндік береді (бұл алфавит үшін әрине болады). Мысалы: сол қол өлшемдері мен оң жақ өлшемдеріндегі таңбалардың жалпы саны өлшемнің негізді анықтамасы болып табылады. Нәтижедегі жинақтарды қайдан алып тастағыңыз келетіні туралы сұрақ бар (S -> aS | b S -> aS | b сияқты грамматика T -> bT | c?), Бірақ бірнеше нұсқаларды зерттеуге және салыстыруға болады.
қосылды автор blntechie, көзі
@vzn Сіз CFL-лер әдетте шексіз нысандар болып табылатындықтан, кодтаудан алыстай алмайсыз, мысалы, CFG.
қосылды автор PKG, көзі
қосылды автор PKG, көзі
@vzn Асимптоталық тығыздығы есептеуге қабілеттілікпен байланысты емес. Бұл жай ғана нақты сандардың лимиті, дәлірек ықтималдығы. Сондықтан бұл нақты талдаудан тұратын тұжырымдама. Әрине, бұл шектеу есептелетін нақты сан болмауы мүмкін. Енді не? Бұл ортогоналды зат. Әрине, есептеу тығыздылығының иерархиясында қай жерлерде біз тығыздығын алатынымызды есепке ала отырып, қандай есептелетін күш тығыздығы бар екенін сұрай аласыз. Асимптоталық тығыздық және есептелетін санмен жиынтығы .
қосылды автор PKG, көзі
@vzn Сұрақ өте жақсы анықталған (CFG өлшемін қалай өлшеуге болатынын қоспағанда) және user18064-тің бастапқы сұрауы оның басылымдарына рандомизацияланған анықталмаған анықтамамен байланысты.
қосылды автор PKG, көзі
Рахмет, бұл тамаша нәрсе. Мен асимптоталық тығыздықтың 1 екендігіне көзім жетті. Бірақ мен келісемін, егер екі жиынтықтың өсу қарқыны экспоненталық болса, логарифмдік тығыздық неғұрлым нақтылы нәтиже болар еді. Меніңше, оны орнату қиынға соғар еді. Сізде қандай да бір түйсігі бар ма (немесе кем дегенде жақындастыра отырып)?
қосылды автор PKG, көзі
@vzn Түпнұсқалық сұрақтан user18064 талдауды қызықтырды және бұл CFG біркелкі емес немесе жоқ болса, жылдам (және жақындастыру) шешуге ұмтылатын «Монте-Карло» сияқты алгоритмдерді жазды. Бұл контексте CFL-лардың белгісіздігі туралы сұрақтар басқаша бағытқа әкелуі мүмкін.
қосылды автор PKG, көзі
@mouseusdumpling Логарифмдік тығыздықты қолдану қандай лимиттерге әсер етеді?
қосылды автор PKG, көзі
Дәлсіздіктің белгісіздігіне байланысты, бұл сұрақтың жауабы оңай емес. Мүмкін, бұл сұраққа жауап берудің бір жолы тұрақты өрнектердегі тұрақты емес өрнектердің тығыздығын қарауға мүмкіндік береді. Сонымен қатар, қалыпты өрнектер үшін өлшем түсінігін анықтаудың табиғи әдістерінің аз болуы мүмкін.
қосылды автор PKG, көзі
@vzn Алдыңғы нұсқасына қарағанда, оның бұрынғы нұсқасына ауысқанға дейін, user18064 тән белгісіздіктерге қызығушылық танытпайды, ал CFG-дағы біркелкі емес CFG тығыздығына байланысты емес деп ойлаймын. CFL-лерде немесе біркелкі емес CFL-дегі біркелкі емес тілдердің тығыздығы әр түрлі, бірақ қызықты мәселе.
қосылды автор PKG, көзі
Сонымен қатар әдебиетте CFG өлшемінің келесі ұғымдары қарастырылған: Әдебиетте грамматика мөлшері туралы түсінікке келсек: (1) Грамматикадағы барлық өндірістердің екі жағында айнымалылар мен терминалдардың жалпы саны. (2) Грамматикадағы барлық өндірістердің екі жағында айнымалылардың саны. (3) Грамматикадағы өндірістер саны. (4) грамматиканың түрлі айнымалы мәндерінің саны.
қосылды автор PKG, көзі
@Kaveh Ия, кодтаумен абай болу керек.
қосылды автор PKG, көзі
Қараңыз, мысалы: S. Ginsburg, N. Lynch, мәтінмәндіксіз грамматикалық пішіндердегі күрделілігі. Дж. Груска, контекстсіз грамматиканың өлшемі туралы. J. Gruska, контекстсіз грамматалар мен тілдердің күрделілігі мен айқындылығы. А.Келеменова, қалыпты формалардың грамматикасының күрделілігі.
қосылды автор PKG, көзі
Мен барлық CFG арасында бірдей емес CFG асимптоталық тығыздығы барлық төрт ұғымның өлшемі үшін бірдей екендігіне көзім жетті.
қосылды автор PKG, көзі
user18064 сәтсіз жоғалып кетті және күдікті/зерттеуші, бәлкім, бакалавриат, бәлкім, бәлкім, зерттелмеген ықтимал мазасыз дерексіз мәселені ұрып-соғып, күдікті (және ешқандай жауап жоқ/түсініктеме тым көп деп болжауға болмайды) мағыналы түрде тұжырымдалған. Монте-Карло симуляциясының идеясы қызықты және мүмкін бір-бірімен байланысты болса да, бір мәнді CFG-ті тану мүмкін емес екенін ескеріңіз!
қосылды автор vzn, көзі
Барлық ақпарат үшін жақсы thx. Сіз бұл нәтижелерді жазасыз деп үміттенесіз, осы зерттеулердің түрлері салыстырмалы түрде сирек кездеседі және өнердің жағдайын айқындауға өте құнды көрінеді. тек бір ғана ұсыныс CFG орнына CFL мәселесін зерттеу үшін кодтау туралы кейбір қарсылықтарды немесе әжімдерді алып тастамайды?
қосылды автор vzn, көзі
oops Әрі қарай ойланыңыз, CFG эквиваленттігін ұмытып кетуді ұмытып кету (бұл бірегей CFL-ді саралау үшін регдті болады). NV, басқа бір идея, «басқа бағытта» кейбір жағдайларда (керісінше) біржақтылықты дәлелдейтін CFG тестерлері болуы мүмкін және мүмкін, дәл осындай дәлдік өлшеулерін алу үшін, олар біркелкі емес пропермен біріктірілуі мүмкін бе?
қосылды автор vzn, көзі
NV коды, бастапқыда шығарылған CFG даналары бойынша parallel ішінде жұмыс істейтін сияқты көрінеді, және ол іске қосылған кезде, кейбір жиынтықтардың барлығы бірдей емес екені анықталған жоқ па? ол кейбір жағдайларда да біржола шеше ме? ал кейбіреулері «аяқталмаған/незамечен» және т.б. бұл шамамен кейбір жұмыспен қамтылған зерттеушілік алгоритмдердің қалай қалыптасқаны туралы әңгімеленеді ...
қосылды автор vzn, көзі
@ user18064/NV соңғы түсініктемеңіздегі ойыңыздағы «~ 90%» санының техникалық тұрғыдан бір-біріне байланысты емес тілдік санына байланысты төмен болуы мүмкін. кодты ұзағырақ ұзартады ма? бұл сіз айтып жатқан сияқты. егер солай болса, онда «қалдықтар» жұмыспен айналыстағы зерттеулерде, яғни шешілмеген/анықталмаған жағдайларда, «ұстау» ұғымына ұқсас.
қосылды автор vzn, көзі
@ user18064/NV, егер сізде барлық сияқты кішкентай тілдердің үлкен кездейсоқ үлгісі бар болса, біреуі бірдей емес/бір мәнді (кез келгенін жоққа шығармай) ретінде шешуге болады, бұл тек эксперименталды және, мүмкін, тіпті теориялық серпіліс ....! бос қобдишасы тіпті өте кішкентай даналары (машина кодтауы) мұқият емес екеніне назар аударыңыз. CFL-лердің белгісіздігінің талдауы үшін сіз білетін басқа эмпирикалық зерттеулер бар ма? кез келген нәрсені естідім .... мүмкін, сіздің жаңашылдық?
қосылды автор vzn, көзі
(«SWAG») гипотезасы, бір мәнді емес қарағанда «көбірек» біркелкі емес CFL бар, және бір мәнді емес «тығыздығы» шектеуде нөлге жақындайды. кейбір CFL-лар бірмәнді және бір мәнді грамматиктерді де қабылдайды! сондықтан мәселе ықтимал мәселе техникалық тұрғыдан алғанда түпнұсқалы екіқұжатсыз грамматикаға қайта бөлінуі керек.
қосылды автор vzn, көзі
@ user18064 бұл туралы Теориялық компьютерлік шеберлікпен сөйлесу мүмкін? Кейбіреулер түсінікті түсініктемелерге реакция жиі жауап қайтарады, бірақ кейде бұл негізсіз шешілмейтін мәселе бойынша дәлелсіз нәтижелерді қайтармайды, сондықтан эмпирикалық өлшенетін нәтиже жоқ па? сіз өз сайтыңыздағы слайдтарда/мақалаларда оның жарамсыздығын растайсыз ... (тек басқа да ықтимал мүмкіндік, мысалы, басқа да жолдарда жарамсыз немесе бұрмаланған жағдайлар өте «кішкентай» болып көрінеді, бірақ бұл екіталай емес сияқты ...)
қосылды автор vzn, көзі
MB ok thx, сіз айтқаныңыздай (ол rev4-дегі өзінің реферстерін жойып, cs.se тарихын жоққа шығарады) және оның computably құралы бар, ол екі жақты грамматиканы анықтайтын секілді жазады. ..! cs.se rev2 : «Менің эксперименттен алынған нәтижелер - бұл грамматикалық жиынтықтардан менің белгісіздікті тексеру құралын іске қосқан жерде - грамматиканың 90% -ы бірдей емес екенін көрсетеді. «
қосылды автор vzn, көзі
@Martin ??? мәселе шынымен де шиыршыққа арналған thx түзілді (және cs.se-тен т.б. көшу арқылы), бірақ rev1 «Randomized Uncertainty Detection» («Рандомизирленген анықталмаған анықтаулар бойынша оның басылымдары») және «cs.se» сайтындағы пайдаланушылар профилі ешқандай егжей-тегжейлі («оның» бірінші сұрағы) жоқ, басқа жерде кез-келген басқа мәселе (басқа сайт?) сол пайдаланушы арқылы? сондай-ақ, асимптоталық тығыздық тұжырымдамасының кез-келген данасы «тілге» қолданылатынын білмейді, бұл жағдайда жеке даналар есептелмеуі мүмкін, яғни рекурсивті түрде аударылатын тіл ...
қосылды автор vzn, көзі
сондықтан CFG анықталмағандықтығы анықталмаса, бұл мәселе кездейсоқ ТМ тоқтату ықтималдығы туралы сұрауға әбден ұқсайды! Chaitins тұрақты ...
  • , олардың кейбіреуі «күдікті емес» дегенді білдіреді.
  • қосылды автор vzn, көзі
    әрбір CFG тиісті CFL және «техникалық» әрбір CFL-да бірдей CFG бар (шын мәнінде көптеген/шексіз сияқты бірыңғай CFG) және сондықтан бұл сұрақтың мағыналық/келісілген түрде тұжырымдалғанына толық сенімді емеспін, басқаша айтқанда, бірдей CFL мәселе есепке алынбайтын әр түрлі жолдармен .... іздеуде «CFL-дегі тығыздықты» қарайтын күрделі қағаздар бар, бірақ осы CFL-ларда әлі күнге дейін барлық сөздердің саны/тығыздығы көрінеді .
    қосылды автор vzn, көзі
    @DavidRicherby, грамматиканың мөлшерін анықтайды, себебі түпнұсқа плакат $ \ le n $ өлшемді грамматика жиынтығына қарайтын түсініктеме ұсынды (екінші пікірді жоғарыдан қараңыз) - менің пікірім оған жауап. Сіз түсініктеме бергенімнің түсініктемесін түсіну үшін барлық түсініктемелерді оқып шығуыңыз қажет.
    қосылды автор Vatine, көзі
    @MartinBerger Мысалы, $ logdesity = log (\ # unambiguousCFGs)/log (\ # CFGs) $ мәнін анықтайтын болсақ, бұл тығыздығына әсер етеді. Мысалы, бір мәнді CFG саны $ 1.5 ^ n $ және CFG саны $ 2 ^ n $, ал лог-тығыздығы $ log_ {1.5} 2 $, асимптоталық тығыздығы 0 болғанда. асимптоталық тығыздығы 0 немесе 1 болады, бірақ асимптотикалық лог-тығыздық қызықты сан болуы мүмкін.
    қосылды автор mobius dumpling, көзі
    Сіз асимптоталық тығыздығын сәйкес шамалардың логарифмдерінің қатынасы ретінде анықтағыңыз келуі мүмкін, себебі екеуі де экспоненталық, әр түрлі негіздермен болуы мүмкін.
    қосылды автор mobius dumpling, көзі
    @vzn менің белгісіздікті тексеру құралы CFG даналарын анық емес деп шешеді. Мәселен, бұл бірдей немесе аяқталмаған.
    қосылды автор sirvile, көзі
    @vzn Ұсынысқа рақмет.
    қосылды автор sirvile, көзі
    @vzn Иә, бұл ~ 90% фигура төменгі шекпен. Егер мен бірнеше күн бойы жүгіріп шықсам, онда тек қана анықталмаған қате саны аз ғана артады. Жұмыспен айналысудың қиындықтарына сілтеме жасайды. Мен бұл мәселені білмедім.
    қосылды автор sirvile, көзі
    @vzn Мен тіпті кішігірім жағдайларда тіпті бірдейсіздіктің шешілмегендігін дәлелдеген грамматиктердің үлкен үлгілерін қамтитын эмпирикалық зерттеулер туралы білмеймін. Менің белгісіздікті тексеру құралы кездейсоқ грамматиктердің көпшілігінде біркелкі болмаса да, егер бірнеше күн бойы менің құралды қалдыратын болсам, ол екіұштылықты анықтайды. Сондықтан, кішігірім жағдайларда да проблема әлі де шешілмейтін деп қорқамын.
    қосылды автор sirvile, көзі
    @vzn Тс чатына сілтеме жасайды.
    қосылды автор sirvile, көзі
    @vzn Ия, анықталмаған мәселе - екібастылықты анықтау. Менің грамматиканы құрастыратын құралым кішкене болуы мүмкін. Яғни, бұл екіталай грамматиканы құру мүмкіндігінің жоғары болуы мүмкін. Менде бұл өлшемді өлшеудің мүмкіндігі жоқ. Мен осы әлсіздікті менің cs.se rev2 мекен-жайында мойындадым. Мүмкін, бұл құралдардың грамматикалық генерациялау әдістері бар (олар мен білмеймін).
    қосылды автор sirvile, көзі
    @vzn Түрлі өңдеулер үшін кешірім. Бұған жол бермеу керек еді. Мен грамматиканың көпшілігінің бірдей емес екені туралы ғана айтқан едім. Сондай-ақ, басқа белгісіздікті тексеру құралы ( AmbiDexter және AMBER ) ең ұқсас жұмыс нәтижесін тапты.
    қосылды автор sirvile, көзі

    1 жауаптар

    Сұрақ нақты кодтауға байланысты. Дегенмен, көптеген ақылға қонымды кодтауларда, ұзындық шексіздікке ұмтылғандай, $ S \ to a $ ($ S $ бастауыш таңбасын және $ a $ терминалын тиісті түсіндіру үшін) өндірістік ережелерінің саны көбірек болады жоғары ықтималдықпен салыстырғанда; мұнда мен бірдей терминалы $ a $ дегенді білдіремін. Егер біз мұны екіұштылық деп қарастыратын болсақ, онда мен «көпшіліктің» грамматикасын екіжақты деп есептеймін. Сондай-ақ, $ S \ - S $ және $ S \ to $ әрқайсысы кем дегенде бір рет пайда болатын ережелер сияқты ұқсас жағдайларды жасай аламыз.

    Бұл жалпы гипотезаны қарастырайық, әрбір (тіркелген) болжамды ереже ұзындығы шексіздікке ұмтылғандай жоғары ықтималдықпен пайда болуы керек деп есептей отырып, біз «көп» грамматиканы $ \ Sigma ^ * $ біртекті емес түрде жасай алатынын анықтаймыз.

    Мысал ретінде $ \ Sigma = \ {0,1 \} $ астам грамматикаға келесі кодтауды қарастырыңыз. Грамматикалық алфавит $ \ {0,1,;,. \} $ Таңбаларынан тұрады. Терминалдар терминалдар кемінде 2 ұзындығы екілік жолдармен индекстеледі. Ережелер толық тоқтаумен бөлінеді. Әрбір ереже - нүктелі үтірмен бөлінген екілік жолдардың реттілігі. Алғашқы екілік жол сол жақта терминал емес, ал қалғандары (егер бар болса) оң жақ бөлігін құрайды; егер екілік екілік жол терминал емес болса (яғни, $ \ epsilon $, 0,1) болса, онда бастапқы терминал болмайды. Бастапқы терминал әрқашан 00 болады.

    Осы кодтауда $ \ {0,1, |,. \} ^ * $ Әр жолдың кейбір грамматикасын сипаттайды. Кездейсоқ грамматика жоғары ықтималдықпен $ .00, 00. $ және $ .00, 0 $ көптеген көшірмелерін қамтиды, және, атап айтқанда, екіұштылыққа ие болады.

    4
    қосылды
    @ user18064 Егер сізде грамматикада нақты параметрдің ықтималдығын бөлу (ұзындық параметрімен параметрленген) болса, онда біз оны талдауға тырысамыз. Мүмкін, нақты мәселе контекстсіз грамматика бойынша жақсы таралу.
    қосылды автор Kevin, көзі
    @Martin Бұл кодтауға байланысты. Мүмкін, сіз шағымыңызды қолдайтын кодтауды ала аласыз, мысалы, әліпби өлшемі грамматикалық өлшеммен өссе. Менің кодтауым тұрақты әліпби өлшемін пайдаланады, сондықтан бұл әсер болмайды.
    қосылды автор Kevin, көзі
    @ user18064 Бағдарламалау тілдері әдетте тұрақты өлшемді алфавитті, көбінесе ASCII жиынын пайдаланады. Мен шектеусіз әліпби мөлшері бар практикалық тіл туралы білмеймін, бірақ оларды оңай анықтауға болады.
    қосылды автор Kevin, көзі
    @MartinBerger Мен өзімнің табиғи дистрибуция деп санайтын нәрсені ұсындым. Егер Сізде CFG-лерде басқа таратылым бар болса, онда оны ресми түрде ұсынуға болады және біз оны талдауға тырысамыз.
    қосылды автор Kevin, көзі
    Бірақ өлшемі (CFG) көбейген сайын, терминалдар мен терминалдардың саны әдетте көбейеді, сондықтан оларды көрсету үшін көп биттер қажет, сондықтан жеке ережелерді көрсету үшін көп биттар қажет. Осылайша, маңызды себептерге байланысты (мысалы, тек бір ереже шектелген мөлшерге сай) CFG саны да арта түседі.
    қосылды автор PKG, көзі
    @YuvalFilmus Бұл әсері $ \ {0,1 \} $ алфавиті ретінде жүреді. Неліктен $ \ sigma \ in \ {0,1 \} ^ * $ ұзындығы $ n $ жолын қарастыру керек. Содан кейін $ 00; \ sigma $ жолағы $ n + 3 $ мөлшеріндегі CFG болып табылады, бұл бір мәнді, өйткені ол тек бір ережеге ие. $ N + 3 $ мөлшерінде $ 2 ^ n $ бар. Бұл экспоненталық өсу. Тривиальды емес біртектес CFG-дың өсу қарқыны әрдайым тривиальды бір мәнді CGG-нің өсуіне кедергі келтіре ме? Кез-келген CFG тривиальды ережеге сәйкес, $ 00; 0 \ sigma; \ gamma $ бірдей өлшемде сәйкес CFG $ 00, 00 \ sigma 0 \ gamma $ бар, бірақ бір ереже аз.
    қосылды автор PKG, көзі
    @YuvalFilmus Сондай-ақ, бірнеше қысқа ережелері бар CFG-ді кодтайтын «артықшылықтары» бар: 00; 0,00; 1 -ден басқа CFG ретінде 00, 1,00, 0 саналады. Бірақ ереже тәртібіне ешқандай күмән туғызбайды, сондықтан бұйрықтың орындалуын талап ету керек. 0, 00, 0,00; 0 осы кодтау бойынша екі түрлі CFG деп есептеледі, тіпті «теориялық тұрғыдан» олар бірдей.
    қосылды автор PKG, көзі
    @YuvalFilmus Мен сіздің шифрын қолданамын. Мен айтқан нәрселердің бірі маған түсініксіз, бұл сізді кодсыздандыруда екіталай грамматиканы (шегінде) тривиально біржақты грамматиканы кодтауда.
    қосылды автор PKG, көзі
    Иә, грамматикада жарамды ретінде $ S \ to S $ және $ S \ to $ (бірнеше рет пайда болған) сияқты ережелерді қарастырамын. Шынында да, бұл грамматикалық тривиально біркелкі етеді. Көңілділер.
    қосылды автор sirvile, көзі
    @MartinBerger Бұл грамматикалық өлшемді көбейте отырып терминал мен терминал емес таңбалардың санын көбейту туралы жарамды нүкте. Бағдарламалау тілдері сияқты жағдайларды қолдану үшін мағынасы бар.
    қосылды автор sirvile, көзі
    @YuvalFilmus Менің ойымша, терминалдың санын көбейту туралы менің бұрынғы түсініктемеіммен грамматиканың мөлшері арта түсетіндіктен түсіндірмедім. Кешірім. Мен терминалдардың санына дейін PL граммалары үшін теңдестірілмеген терминдердің саны арасындағы теңгерім болғаны едім. Грамматика мөлшерін жоғарылату, терминалдардың санын және терминалдардың санын пропорционалды түрде арттыруға тиіс. PL грамматикасы үшін әртүрлі грамматикалық метрикаларды қарау бойынша менің байқауым санның (терминалдардың) қатынасы: сан (терминалдар) шамамен 1: 1 болып табылады. Сіз бұл кодты енгіздіңіз бе? Көңілділер.
    қосылды автор sirvile, көзі