Greibach célèbre défini un langage , que l'on appelle la version non - déterministe de , de telle sorte que toute la LCF est une image inverse de morphique . Existe-t-il une déclaration similaire avec DCFL, éventuellement avec une certaine restriction sur les morphismes autorisés?D 2 HHHHD2D2D_2HHH...
Les langages Dyck sont définis par la grammaire suivante S → S SDyck(k)Dyck(k)\mathsf{Dyck}(k) sur l'ensemble des symboles { ( 1 , … , ( k , ) 1 , … , ) k } . Langues Intuitivement Dyck sont les langues de parenthèses équilibré de k genre différent. Par exemple,
Je comprends que les affirmations suivantes sont vraies: Deux dérivations distinctes d'une chaîne dans un CFG donné peuvent parfois attribuer le même arbre d'analyse à la chaîne. Lorsqu'il existe des dérivations d'une chaîne dans un CFG donné qui attribuent différents arbres d'analyse, le CFG est...
Soit un nombre . Considérons la langue suivante L n = {nnn .Ln= {w w|w ∈ { 0 , 1 }n}Ln={ww|w∈{0,1}n}L_n = \{ \; ww \; \vert \; w \in \{0,1\}^{n} \; \} En termes, est l'ensemble des chaînes de copie de longueur 2 n .LnLnL_n2 n2n2n Considérons la fonction de complexité d'état suivante telle que s ( n...
S'il y a des résultats sur la résolution des problèmes de langage formel en utilisant l'analyse mathématique, les mathématiques continues. Par exemple, résoudre le problème de non-vacuité d'intersection pour une langue sans contexte et une langue
Quel est le rapport entre les CFG ambigus et tous les CFG ? Étant donné que les deux ensembles sont infiniment dénombrables, le rapport n'est pas bien défini. Mais qu'en est-il de la densité asymptotique : limn↦∞# ambiguous CFG of size<n# CFG of size<nlimn↦∞# ambiguous CFG of size<n# CFG...
Considérons une grammaire arbitraire sans contexte sur l'alphabet { 0 , 1 , ¯ 0 , ¯ 1 } . Aux productions de cette grammaire, ajoutez deux productions fixes non contextuelles P : ¯ 0 0 → ϵ et ¯ 1 1 → ϵ . Appelons la grammaire résultante G P pour " G augmenté des productions P ".gGG{ 0 , 1 , 0¯¯¯,...
Je voudrais savoir pourquoi pour la reconnaissance des langues sans contexte, seuls les automates déroulants non déterministes (DPA = NPDA) fonctionnent. Pourquoi les automates déterministes push-down (DPDA) ne reconnaissent-ils pas ces
Existe-t-il des permutations et une grammaire sans contexte de taille polynomiale (dans | w | = n ) qui décrivent le langage fini { w π 1 ( w ) π 2 ( w ) } sur l'alphabet { 0 , 1 } ?π1, π2π1,π2\pi_1,\pi_2| w | =n|w|=n|w|=n{ w π1( w ) π2( w ) }{wπ1(w)π2(w)}\{w \pi_1(w) \pi_2(w)\}{ 0 , 1...