Prouver que la langue est régulière ou non régulière

Laisser $L$ être une langue régulière. Prouve-le:

$L_{+--}=\left\{w: \exists_u |u|=2|w| \wedge wu\in L\right\}$

$L_{++-}=\left\{w: \exists_u 2|u|=|w| \wedge wu\in L \right\}$

$L_{-+-}=\left\{w:\exists_{u,v} |u|=|w|=|v| \wedge uwv\in L\right\}$

sont réguliers et:

$L_{+-+}=\left\{ uv:\exists_w |u|=|w|=|v| \wedge uwv\in L \right\}$

n'est pas régulier.

Cela me semble très difficile. Je suppose que 1-3 sont similaires (mais je peux me tromper), mais je ne sais pas comment aborder. L'idée générale est généralement de modifier la machine à états finis pour $L$ d'accepter une autre langue. Mais ces constructions sont souvent très sophistiquées et je ne peux toujours pas les imaginer seules.

regular-languages xan
la source

doublon possible de Comment prouver qu'une langue n'est pas régulière?

Bartosz Przybylski

Je ne suis pas sûr que vos affirmations soient correctes car il semble d'après le théorème de Myhill-Nerode que les trois premières langues ont une infinité de classes d'équivalence! pour le premier: prendre

w_{i}

$w_i$ être le i-ème

L_{+ - -}

$L_{+--}$ et

w_{i + 1}

$w_{i+1}$ être le (i + 1) -ème mot, puis pour tout ce que je peux choisir

u_{i}

$u_i$ pour montrer qu'il existe un mot qui sépare les classes de

w_{i}

$w_i$ et

w_{i + 1}

$w_{i+1}$

Fayez Abdlrazaq Deab

@Fayez Et si, par exemple,

L = Σ^{*}

$L=\Sigma^*$ ? alors

L_{+ - -} = Σ^{*}

$L_{+--} = \Sigma^*$ n'a qu'une seule classe d'équivalence. Passez en revue votre preuve et voyez ce qui ne va pas.

Yuval Filmus

@Bartek et tout autre votant pour clore: la moitié de la question est en fait de prouver que certaines opérations sur les langues conservent la propriété d'être régulières.

Yuval Filmus

Réponses:

Voici une preuve que la langue $L_0 = \{ w : \exists_u |u|=|w| \land uw \in L \}$ est régulier. Il peut être modifié pour montrer que les trois premiers de votre liste sont réguliers. (Notez que j'ai changé $wu$ à $uw$ .) Étant donné un DFA pour $L$ , nous construisons un NFA pour $L_0$ . La première chose que fait la NFA est de deviner (prendre un $\epsilon$ déplacer) un état $q$ , dont la sémantique est l'état selon lequel le DFA pour $L$ finit après avoir lu $u$ . Il exécute ensuite simultanément deux copies du DFA pour $L$ , l'un commençant à l'état de départ et l'autre commençant à $q$ . En lisant un symbole $a$ , il se déplace selon un symbole arbitraire sur le premier, et se déplace selon $a$ sur le second. Un état accepte si la première copie est à l'état $q$ et le second est dans un état acceptant.

Pour le dernier, considérez la langue $L= a^+ b^+ c^+$ et se croisent $L_{+-+}$ avec $a^+ c^+$ .

Yuval Filmus
la source

Je ne vois pas ça.

L = a^{+} b^{+} c^{+} \Rightarrow L_{+ - +} \cap a^{+} c^{+} = {a^{n} c^{m} : n + m \equiv_{2} 0}

$L=a^+b^+c^+ \Rightarrow L_{+-+} \cap a^+c^+=\left\{ a^n c^m: n+m\equiv_2 0 \right\}$ , qui est clairement une langue régulière. Mais je suppose que je me trompe :) Pouvez-vous me montrer la bonne direction?

xan

J'ai réussi à modifier votre construction de

L_{0}

$L_0$ et même retirer

ε

$\varepsilon$ se déplace pour devenir plus élégant (à mon avis). Donc les trois premiers problèmes résolus et merci pour ça! :) Mais la seule chose que je vous demande est de clarifier la dernière et mes préoccupations dans le commentaire ci-dessus. Je serais très reconnaissant.

xan

Quand je calcule

L_{+ - +} \cap a^{+} c^{+}

$L_{+-+} \cap a^+ c^+$ Je reçois autre chose. Notez que chaque mot

L

$L$ doit contenir un

b

$b$ .

Yuval Filmus

Désolé, mais je ne sais pas comment calculer

L_{+ - +} \cap a^{+} c^{+}

$L_{+-+}\cap a^+c^+$ . Je suppose que le résultat est

{a^{n} c^{n} : n \in N}

$\left\{ a^n c^n: n\in\mathbb{N}\right\}$ ce qui nous donne ce que nous voulons, mais je ne sais tout simplement pas comment le justifier.

xan

Ok, je peux voir maintenant :-)

xan