Si

8

Nous avons deux langues: . Nous savons que est un langage régulier, donc ma question est de savoir si est régulier vers? $L_1,L_2$ $L_1L_2$ $L_2L_1$

J'essaie de trouver un moyen de le prouver ...

Je ne peux bien sûr pas supposer que $L_1,L_2$ sont réguliers ...
Je cherche donc un moyen de le prouver.

J'aimerais avoir un indice!

Je vous remercie!

formal-languages regular-languages closure-properties stud1
la source

Continuons cette discussion dans le chat .

Raphael

7

Non, $L_2L_1$ n'est pas nécessairement régulière.

Laisser $L_1 = \{0,1\}^*$ , qui est régulière, et $L_2 = \{1\} \cup \{0^n1^n\mid n\geq 1\}$ , qui n'est pas. alors $L_1L_2$ est l'ensemble de toutes les chaînes se terminant par $1$ , ce qui est régulier, mais $L_2L_1$ est l'ensemble de toutes les chaînes qui commencent par $1$ , commencez par un nombre différent de $0$ s suivi d'au moins autant $1$ s. Cette langue n'est pas régulière, car son intersection avec $\{0^m1^n\mid m,n\geq 1\}$ est $\{0^m1^n\mid 1\leq m\leq n\}$ , qui n'est pas régulière.

David Richerby
la source

Merci David, mais pourquoi le "

{1} \cup \dots

$\{1\}\cup \cdots$ " à

L_{2}

$L_2$ ? pourquoi nous en avons besoin? Je vous remercie!

stud1

1

@ stud1 Pour s'assurer que

L_{1} L_{2}

$L_1L_2$ est régulier.

David Richerby

Mais

L_{1} L_{2}

$L_1L_2$ (sans le

{1}

$\{1\}$ ) c'est toujours tous les mots qui finissent par

1

$1$ , droite? Donc, j'essaie toujours de comprendre pourquoi nous avons besoin du

{1}

$\{1\}$ , J'espère que ça va, je le demande :-) Merci!

stud1

1

@ stud1 Si vous supprimez

{1}

$\{1\}$ puis, par exemple,

1 \notin L_{1} L_{2}

$1\notin L_1L_2$ . Plus généralement, les seules chaînes qui seraient

L_{1} L_{2}

$L_1L_2$ seraient ceux se terminant par

0^{m} w^{n}

$0^mw^n$ pour

m \geq n \geq 1

$m\geq n\geq 1$ .

David Richerby

1

@ stud1 Correct.

David Richerby

13

Je ne publiais qu'un indice, puis j'ai vu d'autres réponses complètes, c'est donc une solution complète (cachée) succincte :-)

Laisser $L_1 = \{ 1^p \mid p \text{ is prime}\}$ , $L_2 = \{ 1^* 0 \}$ ; on a $L_1 L_2 = \{ 11^+ 0\}$ ce qui est régulier, mais $L_2 L_1 = \{ 1^* 0 1^p \mid p \text { is prime}\}$ ce qui n'est pas régulier.

Vor
la source

1

Solution élégante!

Anton Trunov

2

@AntonTrunov: assez élégant :-)

L_{2} = {1^{*} 0}

$L_2 = \{1^* 0\}$ peut être utilisé pour "masquer" tout UNARY non régulier

L_{1}

$L_1$ , mais dès qu'ils sont échangés

L_{1}

$L_1$ est à nouveau "exposé" :-)

Vor

Quel est le sens de

+

$+$ à

11^{+}

$11^+$ ?

stud1

1

@ stud1:

1^{+}

$1^+$ signifie "un ou plusieurs

1 s

$1s$ "; en d'autres termes, c'est un" raccourci "pour

{1^{n} ∣ n \geq 1}

$\{1^n \mid n \geq 1\}$ . Donc

{11^{+} 0} = {110, 1110, 11110, . . .}

$\{ 11^+0 \} = \{ 110, 1110, 11110, ...\}$

Vor

6

Ce n'est pas un indice, mais une réponse complète. Ne continuez pas à lire si vous essayez toujours de résoudre.

Il n'y a pas besoin de $L_2\cdot L_1$ être régulier.

Laisser $A$ être une langue unaire (non régulière) telle que $A\cdot A$ est régulier. Ces langues peuvent être trouvées dans la publication ici . Présumer $A$ est sur l'alphabet $\{a\}$ .

Définir $L_1=\{b\}\cdot A$ et $L_2=A\cdot \{b\}$ . Ensuite, vous obtenez $L_1\cdot L_2=\{b\}\cdot A^2\cdot \{b\}$ , ce qui est régulier. cependant, $L_2\cdot L_1=A\cdot \{bb\}\cdot A$ , qui peut être facilement prouvé comme non régulier, sur la base de $A$ être non régulier.

Shaull
la source

1

Les règles suivantes définissent le langage associé à toute expression régulière. Règle 1 La langue associée à l'expression régulière qui n'est qu'une seule lettre est ce mot à une seule lettre et la langue associée à A est juste {A}, une langue à un mot. Règle 2 Si r, est une expression régulière associée au langage L, et r 2 est une expression régulière associée au langage L2 alors,

(i) L'expression régulière (rl) (r2) est associée au langage L, multipliée par L 2. langage (r, r2) = L1L 2 (ii) L'expression régulière r, + r2 est associée au langage formé par le union des ensembles L1 et L2. langue (rl + r2) = L, + L2 (iii) La langue associée à l'expression régulière (rl) * est LI *, la fermeture Kleene de l'ensemble LI comme un ensemble de mots. langue (rl *) = L1 *

Shashi Kumar
la source

Si

Réponses: