HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Are these two languages regular?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
thesearelanguagesregulartwo

Problem

Let $\operatorname{value}(x)$ be the result when the symbols of $x$ are multiplied from left to right according to

$\qquad \displaystyle\begin{array}{c|ccc}
\times & a & b & c \\
\hline
a & a & a & c \\
b & c & a & b \\
c & b & c & a
\end{array}$

Is $L=\{xy \mid |x|=|y| \land \operatorname{value}(x) = \operatorname{value}(y)\}$ regular?

Is $L=\{xy \mid \operatorname{value}(x)= \operatorname{value}(y)\}$ regular?

Solution

Hint for (1): consider a different type of value, $\mathrm{value}(s) = 1$ if $s$ ends with $z$, and $\mathrm{value}(s) = 0$ otherwise. Define the language $L$ as in your case, and consider $L \cap x^ z y^ z$.

Hint for (2): consider the language $L_\alpha = \{xy : \mathrm{value}(x) = \mathrm{value}(y) = \alpha \}$. What is the relation between $L_\alpha$ and $M_\alpha = \{ x : \mathrm{value}(x) = \alpha \}$? Is $M_\alpha$ regular?

Context

StackExchange Computer Science Q#10251, answer score: 6

Revisions (0)

No revisions yet.