Différence entre la grammaire ordinaire et la CFG en générant des historiques de calcul et $ \ sigma ^ * $ $

Question

Je voudrais demander une intuition de comprendre la différence entre un CFG générant $ \ sigma ^ * $ et une grammaire régulière générant $ \ sigma ^ * $ .. j'ai eu les exemples ici de sipateur. Laissez $ all_ {cg} $ se référer à la langue qu'un CFG donné génère $ \ sigma ^ $ et laissez $ all_ {rex} $ se référer à la langue qu'une expression régulière donnée génère $ \ sigma ^ * $ <* / Span> (et puisque pour chaque expression régulière, il y a une grammaire régulière, nous pouvons également dire que la grammaire régulière équivalente génère $ \ sigma ^ * $ ).

De ce que j'ai eu, nous avons:

• $ all_ {cg} $ n'est pas décidable, il n'est pas non plus reconnaissable. Laisse $ \ overline {a_ {tm}} $ se référer à la langue d'une touche TM $ M $ Ne pas accepter le mot d'entrée $ w $ . Nous pouvons réduire $ \ overline {a_ {tm}} $ à $ all_ {cg} $ in polynomial temps en utilisant des histoires de calcul. La réduction construit un CFG qui génère tous les mots possibles où: 1) Les premiers caractères ne correspondent pas $ w $ , 2) Les derniers caractères ne correspondent pas à accepter les configurations et 3) Les caractères ne correspondent pas aux transitions valides de M $ M $ S. Ainsi, $ a_ {tm} $ $ n'accepte pas $ w $ iff le CFG génère $ \ sigma ^ * $ (c'est-à-dire qu'il n'y a pas d'historique de calcul acceptant). Depuis la réduction des cartes $ \ overline {a_ {tm}} $ to $ all_ {cg} $ , et $ \ overline {a_ {tm}} $ ne contient pas de diurning-reconnisable, $ all_ {cg} $ ne contient pas - reconnaissable.

• $ all_ {rx} $ $ est décidable car il est décidable si un automate fini accepte $ \ sigma ^ * $ . Cependant, le problème d'acceptation de toute langue ordinaire $ r $ peut être réduit polynomentiellement à la langue $ all_ {rex} - f (R_M) $ , où $ r_m $ est une TM qui décide $ r $ , et $ f (r_m) $ est une réduction similaire des antécédents de calcul tels que décrits ci-dessus. Plus en détail, $ f (r_m) $ est la grammaire ordinaire qui génère tous les mots possibles où 1) les premiers caractères ne correspondent pas $ w $ , 2) Les derniers caractères ne correspondent pas à des configurations de rejet, et 3) ne correspondent pas aux transitions valides de $ r_m $ configurations. Le débutant pour $ all_ {rex} - f (r_m) $ chèques s'il est vide (ce qui signifie que $ f ( R_m) $ est égal à $ \ sigma ^ * $ ). Si vide, alors il n'y a pas de rejeter les histoires de calcul et $ w \ in r $ . (Dans SIPSER, il a utilisé quelque chose comme ça pour afficher l'expansion de l'EXPACACE - pour $ ALL_ {REX} - F (R_M) $ )

Je voudrais demander:

d'en haut, les grammaires ordinaires et les CFG peuvent générer des histoires de calcul d'une TM, et les deux pourraient générer $ \ sigma ^ $ . Mais qu'est-ce que c'est avec le pouvoir fondamental de la grammaire de la CFG qui le rend valide pour réduire $ \ overline {a_ {tm}} $ to $ all_ {cfg} $ , mais il n'est pas possible pour $ \ overline {a_ {tm}} $ doit être réduit à $ ALL_ {REX} - F (A_ {TM}) $ ? Je sais que nous ne pouvons pas réduire $ \ overline {a_ {tm}} $ à $ all_ {rex} - f (a_ {Tm}) $ depuis $ all_ {rex} - f (a_ {tm}) $ est décidable, tandis que $ \ overline {a_ {tm}} $ ne contient pas de diuring-reconnaissable ... mais j'aimerais comprendre cela en termes de différence de génération de puissance entre les grammaires de la CFG et des grammaires régulières via leurs règles.

Par exemple, de ce que j'ai lu, le permis de CFG permet aux règles $ a \ droite bc $ , où $ B $ et $ C $ C $ sont des chaînes de variables et de terminaux. D'autre part, les grammaires régulières ne permettent que des règles sous forme de

-Container "> $ a \ rightarrow AB $ , où $ a $ est un terminal. Je voudrais demander: pourquoi incorporer des règles de la forme $ a \ droite $ BC $ à une grammaire, donnez-lui suffisamment de puissance génératrice de telle qu'elle est déjà valide pour réduire $ \ Overline{A_ {tm}}} $ à la grammaire (c'est-à-dire au CFG).

Answer 1

Votre résumé de la preuve de la non-détériorie n'est pas précis. Votre spécification de $ \ overline {a_ {tm}} $ n'est pas correct.

Pour une exposition raisonnable de la preuve, voir https://liacs.leidenuniv .nl / ~ hoogeboomhj / second / codingcomputations.pdf en particulier le début de la section 1 et 3.

L'intuition n'est pas facile à transmettre, car la preuve n'est pas entièrement triviale. Mais voici le fait fondamental. Laissez $ v, w $ soit deux configurations d'une machine à Turing. Écrire $ n (v) $ Pour être la prochaine configuration de la machine Turing après une seule étape de calcul, si vous démarrez à la configuration $ v $ . Définir la langue

$$ l={v \ # w ^ r \ moyen n (v) \ ne w \}. $$

alors le fait clé est que $ l $ est sans contexte. Cela prend une preuve; prouver que c'est une étape clé dans la preuve. Cependant, c'est la réponse à votre question: $ l $ est sans contexte mais pas régulier. En conséquence, nous pouvons réduire le problème d'arrêt de $ all_ {cg} $ mais pas à $ all_ {rex} $ .

J'ai sauté de nombreuses étapes pour vous donner un aperçu de l'idée principale. Vous devrez lire la preuve complète pour remplir les détails. Je vous suggère que vous suivez et comprenez la preuve, avec cette perspective à l'esprit, puis revisitez ce que j'ai écrit ici. Espérons que cela vous aidera à comprendre pourquoi la preuve détient des langues sans contexte, mais échouerait pour des langues ordinaires.

Answer 2

La différence entre les modèles tiges, intuitivement, de la capacité des CFGS à compter . Plus précisément, les CFGS sont capables de générer des chaînes de la forme $ a ^ nb ^ n $ , où le nombre de $ a $ 's et $ B $ est le même.

Cette capacité accorde la puissance de comparer les chaînes, qui peuvent ensuite être utilisées pour indiquer une indécidabilité, car le CFG est capable de comparer le contenu d'une bande entre deux configurations consécutives.

Cela devient un peu plus évident si vous vous souvenez que le problème d'arrêt des machines à deux comptoirs (machines Minsky) est indécitable. Là, une configuration est donnée par les valeurs de deux comptoirs. Vous pouvez ceci en tant que TM avec une sorte d'alphabet unaire (bien que pas exactement). Dans deux machines de comptoir, la comparaison de deux configurations consécutives équivaut parfaitement à comparer les valeurs des compteurs dans des étapes consécutives, ce qui est à la hauteur de la ruelle des GFV.

En revanche, les langues ordinaires sont capturées par des automates finis de l'état, qui ont une mémoire finie et sont capables de compter uniquement jusqu'à un nombre fixe. Ainsi, ces automates peuvent simuler une TM tant que la longueur d'une configuration est bornée à l'avance. Pourquoi cela donne-t-il de la dureté PSPACE? Eh bien, vous pouvez simuler tout tm qui fonctionne dans l'espace délimité, il n'est pas nécessaire d'être polynomial dans l'entrée. Cependant, pour que la réduction elle-même soit polynomiale, vous avez besoin de la tenue de polynôme. Ainsi, vous obtenez exactement la dureté PSPACE.

En ce qui concerne le "type" des règles, ce n'est pas tant la $ A \ AVER $ Règles qui posent un problème, c'est plus dans les règles de la Formulaire $ A \ AAB $ (ou plus généralement, la capacité d'avoir cyclique règles). La raison est que $ A \ to bc $ a une structure "arborescente", et si $ B $ et $ C $ ne sont pas liés plus tard, il s'agit effectivement d'une opération syndicale, quelles langues ordinaires peuvent simuler.

Cependant, une règle de la forme $ A \ to AAB $ maintient le "contexte" $ a $ , qui est quelque chose de langages réguliers ne peut pas faire.

résumer:

sémantiquement, la puissance des CFGS réside dans leur capacité à compter.

syntaxiquement, la puissance des CFGS réside dans des règles cycliques.