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$
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.
