Is this proof right??

Claim: Let #0(w) and #1(w) be the number of 0s and 1s in w,
respectively. Then
A = {uv ∈ {0, 1}∗ : |u| = |v|, #0(u) = #1(v), and #0(v) = #1(u)}
is not a regular language.

Proof : Say there is some pumping length p.
Choose w = 0^k 1^k 0^k 1^k ∈ A where k = p .

Consider the division w = xyz where x = ε, y = 0^j for 0 < j ≤ k,
and z = 0^(k−j) 1^k 0^k 1^k . This is consistent with the pumping criteria
since y = ε and |xy| ≤ p. Then the string xy^0 z = 0^(k−j) 1^k 0^k 1^k is
not in A. Note that j must be even, since xy^0 z would have odd
length otherwise, so xy^0 z can be written as uv with |u| = |v|.
Then
u = 0^(k−j) 1^k 0^(j/2) and v = 0^(k− j/2) 1^k , but #1(u) is not equal to #0(v) since
k is not equal to k − j/2 .
Because w cannot be pumped, A is not regular by the pumping lemma.

ok i got it
thanks to nobody!! :)

It was k = lower bound(p/2)...my mistake

i mean floor(p/2)

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.