Fermeture de langages sans contexte sans ambiguïté sous pré et postfix.

L'ensemble est certainement sans contexte, mais je pense qu'il peut être intrinsèquement ambigu: considérez puis inclut le langage classique intrinsèquement ambigu et on peut prouver que est également intrinsèquement ambigu par le argument habituel (appliquer le lemme d'Ogden à la fois et pour déduire l'existence de deux arbres distincts pour ). $\mathit{ppc}(L)$

L = {a^{m} b^{m} c^{n} d ∣ m, n \geq 0} \cup {d a^{m} b^{n} c^{n} ∣ m, n \geq 0},

$L=\{a^mb^mc^nd\mid m,n\geq 0\}\cup\{da^mb^nc^n\mid m,n\geq 0\}\;,$

p p c (L)

$\mathit{ppc}(L)$

L^{'} = {a^{m} b^{m} c^{n} ∣ m, n \geq 0} \cup {a^{m} b^{n} c^{n} ∣ m, n \geq 0},

$L'=\{a^mb^mc^n\mid m,n\geq 0\}\cup\{a^mb^nc^n\mid m,n\geq 0\}\;,$

p p c (L)

$\mathit{ppc}(L)$

a^{n + n!} b^{n} c^{n}

$a^{n+n!}b^nc^n$

a^{n} b^{n} c^{n + n!}

$a^nb^nc^{n+n!}$

a^{n + n!} b^{n + n!} c^{n + n!}

$a^{n+n!}b^{n+n!}c^{n+n!}$

Sylvain
la source

Je vous remercie. C'était plus facile que moi. Pensez-vous que les variantes du problème (par exemple, les pré- et postfixes doivent être délimités (par de nouveaux symboles) présentent une perte de non-ambiguïté similaire?

Martin Berger

Voulez-vous dire quelque chose comme ? Ensuite, à partir de vous constaterez que a deux arbres distincts dans n'importe quelle grammaire pour . Je crains de ne pas avoir d'idée pour le moment sur la façon de modifier (de manière simple) l'opération afin de garantir la non ambiguïté: le préfixe ou le suffixe perdu dans l'opération pourrait être crucial pour la non ambiguïté de tenir.

{p p c}_{$} (L) = {w $ ∣ \exists w^{'}, w w^{'} \in L} \cup {$ w ∣ \exists w^{'}, w^{'} w \in L}

$\mathit{ppc}_\$(L)=\{w\$\mid\exists w',\,ww'\in L\}\cup\{\$w\mid\exists w',\,w'w\in L\}$

L = {d a^{m} b^{m} c^{n} ∣ m, n \geq 0} \cup {e a^{m} b^{n} c^{n} ∣ m, n \geq 0}

$L=\{da^mb^mc^n\mid m,n\geq 0\}\cup\{ea^mb^nc^n\mid m,n\geq 0\}$

$ a^{n + n!} b^{n + n!} c^{n + n!}

$\$a^{n+n!}b^{n+n!}c^{n+n!}$

{p p c}_{$} (L)

$\mathit{ppc}_\$(L)$

p p c

$\mathit{ppc}$

Sylvain

Oui, quelque chose comme ça. Comme cela ne fonctionne pas, je devrai repenser mon domaine d'application. Merci beaucoup pour votre contribution.

Martin Berger

Fermeture de langages sans contexte sans ambiguïté sous pré et postfix.

Réponses: