Pourquoi L={wxw^R| w, x appartient à {a,b}^+ } est un langage régulier
À l'aide de pompage lemme, on peut facilement prouver que la langue L1 = {WcW^R|W ∈ {a,b}*}
est pas un langage régulier. (l'alphabet {a,b,c}; W^R représente l'inverse de la chaîne W)
Cependant, Si l'on remplace le caractère c
avec "x"(x ∈ {a,b}+)
, disons, L2 = {WxW^R| x, W ∈ {a,b}^+}
, puis L2 est un langage régulier.
Pourriez-vous me donner quelques idées?
Que voulez-vous précisément? Je vous suggère de réviser votre question "Pourriez-vous me donner quelques idées?" à quelque chose de plus concis et constructifs.
OriginalL'auteur henry | 2013-01-25
Vous devez vous connecter pour publier un commentaire.
Oui,
L2
est Régulier de la Langue :).Vous pouvez écrire une expression régulière pour
L2
trop.Langage L2 = {WXWR| x, W ∈ {a,b}+} signifie:
a
etb
qui estW
et à la fin avec l'inverse de la chaîne WR.a
oub
)a
etb
dans le milieu qui estX
. (en raison de+
, longueur deX
devient supérieure à une|X| >= 1
)Exemple de ce type de chaînes de caractères peuvent être les suivants:
aabababa, comme suit:
ou il peut être aussi:
babababb, comme suit:
Voir la longueur de
W
n'est pas une contrainte dans la définition de langage.de sorte que toute la chaîne de WXWR peut être prise en charge est égale à
a(a + b)
+a
oub(a + b)
+b
ou
Et d'Expression Régulière pour cette langue est:
a(a + b)
+a
+
b(a + b)
+b
Ne pas mélanger
WXW
R avecWCW
R, sonX
avec+
qui fait de la langue ordinaire. Pensons ici notammentX
qui est(a + b)*
nous pouvons avoir finis choix pourW
qui esta
etb
(fini est normal).Langue
WXW
R peut-être dire: si le début aveca
se termine aveca
et si commencer avecb
fin avecb
. donc, en conséquence nous avons besoin de deux états finaux.W
esta
W
estb
Son DFA est donnée ci-dessous.
Signifie-t-il, nous ne pouvons pas simplement en choisir un de x cordes? Comme l'exemple que vous mentionnez ci-dessus, Si nous suffit de sélectionner x = “ababab” et w = a^n, alors nous obtenons wxw^R = (a^n)ababab(a^n). Cependant, si nous utilisons le lemme de pompage, il semble que cet exemple échoue. C'est la partie que je suis confus. Quand doit-on choisir une couterexample avec le lemme de pompage. Pour l'exemple wxw^R, nous ne pouvons pas résoudre x, x = dire des chaînes de caractères spécifiques, si nous corriger, nous ne parviennent pas à passer lemme de pompage.
Pas de
W
est juste unique symbolea
oub
Je sais pourquoi je suis confus. Nous pouvons appliquer le lemme de pompage dans la deuxième langue, dire, xy^(2)z = a^(n+|y|) baaba^(n) (nous choisissons au hasard x=baab). Nous notons que xy^(2)z = a^(n)^(|y|)baab a^(n). C'est encore dans le langage L, pas de contradiction. Précédente, je me trompe cela comme une contradiction. Il n'en est rien à voir avec le fait que nous fixons x ou pas. Peu importe ce que les chaînes de nous sélectionner à partir de x, nous pouvons toujours obtenir les chaînes qui appartiennent à la langue L. Merci @Grijesh 🙂
-1, DFA est faux. Ne peut pas générer
aaba
. RE regarde, à droite.OriginalL'auteur Grijesh Chauhan
Une chaîne dans la langue avec |W| > 1 peut être interprété comme une chaîne de caractères dans la langue où |W| = 1. Ainsi, une chaîne est dans la langue, s'il commence et se termine avec le même symbole. Il y a deux symboles: a et b. De sorte que la langue est l'équivalent de la langue
a(a+b)(a+b)*a + b(a+b)(a+b)*b
. Pour prouver cela, vous devez formaliser l'argument que "si y est dans la WxW, puis y en a(a+b)(a+b)*a + b(a+b)(a+b)*b; et si y en a(a+b)(a+b)*a + b(a+b)(a+b)*b, alors y est dans WxW".Il ne fonctionne pas dans l'autre cas, puisque c est un symbole, et ne peut pas inclure tous les mais les caractères sur les extrémités. Dès que vous avez lié la longueur de "x" dans votre exemple, le langage devient non-régulière.
OriginalL'auteur Patrick87
La question dit que W ∈ {a,b}^+ , de sorte que a^n(a+b)^n doivent être dans la langue L2. Maintenant, il n'y a pas une telle DFA qui acceptera la chaîne a^n(a+b)^n, parce que, après avoir accepté un nombre n de a et (a+b)^+, il n'y a aucun moyen pour le tfd à rappeler combien un il a accepté au début, de sorte que L2 ne doit pas être régulier.........Mais, en tous lieux, je recherche pour cette réponse, il dit que c'est normal.....ce qui me dérange
OriginalL'auteur user2035158