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

Is language $\{a,b\}^*$ same as language $\{xy \in \{a,b\}^* \mid |x|_a = |y|_b \}$?

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

Problem

I need to prove or disprove if these two languages are same.
So I assume that these lanaguages are same because I think that every word from $\{a,b\}^$ could be concatenated from two words $x$ and $y$ where $|x|_a = |y|_b$. So $x$ and $y$ must belong to $\{a,b\}^$, too. Then I can write and prove this:

$\{a,b\}^ \subseteq \{xy \in \{a,b\}^ \mid |x|_a = |y|_b \} \wedge \{xy \in \{a,b\}^ \mid |x|_a = |y|_b \} \subseteq \{a,b\}^$

So I assume that $z \in \{a,b\}^*$. Then $z = z_1z_2...z_i$ where $z_1,z_2,...,z_i \in \{a,b\}$

Here I stucked and I don't know (1) how to continue, (2) if the way of proving i choose is correct or not.

Solution

We want to show that every string $z\in \{a,b\}^*$ is of the form $xy$ with $|x|_a=|y|_b$, as follows.

Make a graph of the value $|x|_a - |y|_b$ for every composition $x,y$ of $z = xy$, letting $x$ run over the prefixes of $z$. The value starts at $-|z|_b$ for $x=\varepsilon$ and ends in $|z|_a$ for $x=z$. Carefully argue it will be zero somewhere on the way.

Context

StackExchange Computer Science Q#71221, answer score: 4

Revisions (0)

No revisions yet.