Il existe un problème ouvert dans les langages formels connu sous le nom de problème de séparation; qui est brièvement indiqué comme étant donné deux chaînes distinctes de longueur , la taille d'un DFA est nécessaire pour les "séparer", ce qui signifie accepter une chaîne mais rejeter l'autre.nnn...
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...
Où puis-je trouver une introduction aux automates probabilistes et ce qu'ils reconnaissent (certaines fonctions des mots à )? Existe-t-il un terme standard pour ces fonctions qui sont reconnues par les automates probabilistes, analogue aux «langages normaux» pour ce que les automates déterministes...
P⊆ CSLP⊆CSLP\subseteq CSLP⊈ CSLP⊈CSLP\not\subseteq CSL PPP est l'ensemble de tous les langages décidables en temps polynomial sur une machine de Turing déterministe, et CSLCSLCSL est la classe des langages contextuels, connue pour être équivalente à , les langages décidés par des automates...
Un DFA ou un NFA lit une chaîne d'entrée avec une seule tête, se déplaçant de gauche à droite. Il semble naturel de s'interroger sur les machines à états finis qui ont plusieurs têtes , chacune se déplaçant à travers l'entrée de gauche à droite, mais pas nécessairement au même endroit dans l'entrée...
D'après mon expérience, les langages contextuels et les automates linéaires bornés sont souvent ignorés ou ignorés dans les cours de théorie de la calculabilité, et sont même exclus de certains manuels remarquables, bien que les automates finis et déroulants reçoivent beaucoup d'attention. Il doit...
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...
Les analyseurs de graphiques peuvent être implémentés sur la base de la forme normale de Chomsky ou directement sur la base des règles de production. Supposons pour le moment que nous avons un analyseur graphique CYK qui utilise la forme normale de Chomsky. La binarisation n'est pas définie de...
Je me demandais quels ensembles de langues sont générés par les restrictions des expressions régulières. Supposons que toutes les restrictions aient un symbole constant pour chaque élément de et de concaténation. Ensuite, huit classes peuvent être formées par la présence ou l'absence de complément...
J'apprends la théorie algébrique de l'analyse. Mon premier problème est d'identifier des exemples semi-spécifiques à la théorie formelle du langage. Voici une tentative de construire deux exemples. 1 Compte tenu de la grammaire CNF, les éléments de semiring sont des ensembles de symboles terminaux...
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
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...
Soit un alphabet fini. Pour un langage donné le monoïde syntaxique est une notion bien connue en théorie formelle du langage. De plus, un monoïde reconnaît un langage ssi il existe un morphisme tel que .L ⊆ A ∗ M ( L ) M L φ : A ∗ → M L = φ - 1 ( φ ( L ) ) )UNEAAL ⊆ A∗L⊆UNE∗L \subseteq A^{\ast} M(...
Il existe un certain nombre de modèles différents pour définir les transformations entre les langues. Les transducteurs à états finis et les transformations de graphes définissables par MSO sur des graphes à cordes sont les deux que je connais le mieux. Nous savons que les transducteurs à états...
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