patternMinor
Is language $\{a,b\}^*$ same as language $\{xy \in \{a,b\}^* \mid |x|_a = |y|_b \}$?
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.
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.
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.