Is the language {xyx, where x,y are arbitrary strings over {0,1}} a regular set?
I'm not sure on this, but I think it is regular. Let $x=\epsilon$ then $xyx=y$ and $y=\{0,1\}^*$.
$\begingroup$
$\endgroup$
New contributor
Elijah Heimsoth is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
Yes, the language is regular and your idea is correct.
You can formally prove it by showing that $L = \{xyx \mid x,y \in \{0,1\}^*\}$ is equivalent to the language $\{0,1\}^*$, which is clearly regular.
By definition, we have that $L \subseteq \{0,1\}^*$ since every language is a subset of the set of all strings (over the same alphabet). To prove that $\{0,1\}^* \subseteq L$, consider any string $w \in \{0,1\}^*$. Then, we have that $w = \varepsilon w \varepsilon$, concluding that $w \in L$. Therefore, $L = \{0,1\}^*$.
New contributor
Simone Bianco is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
-
$\begingroup$ What about expecting the string represented by the left $x$ to be the same as the one represented by the right $x$? $\endgroup$greybeard– greybeard2025-12-07 11:54:59 +00:00Commented 5 hours ago
-
$\begingroup$ @greybeard Every word of the form $x_1 y_1 x_1$ where $x_1 \neq \varepsilon$ can also be written as $x_2 y_2 x_2$ where $x_2 = \varepsilon$ and $y_2 = x_1 y_1 x_1$, which is basically the sentence before last of Simone Bianco's answer. $\endgroup$Jasmijn– Jasmijn2025-12-07 14:45:06 +00:00Commented 2 hours ago
