Skip to main content
added 119 characters in body
Source Link
gnasher729
  • 31.6k
  • 35
  • 55

Just show that after processing $0^n$ and $0^{n’}$ with n != n’ you must have reached two different states. (Which is easy: In one state, processing $1^n$ leads to an accepting state, in the other state it doesn’t). Therefore there is no finite set of states.

Or you just take the pumping lemma, p arbitrary large, and w = $0^p 1^p$. Which makes y = $0^k$ for some k >= 1.

Just show that after processing $0^n$ and $0^{n’}$ with n != n’ you must have reached two different states. (Which is easy: In one state, processing $1^n$ leads to an accepting state, in the other state it doesn’t). Therefore there is no finite set of states.

Just show that after processing $0^n$ and $0^{n’}$ with n != n’ you must have reached two different states. (Which is easy: In one state, processing $1^n$ leads to an accepting state, in the other state it doesn’t). Therefore there is no finite set of states.

Or you just take the pumping lemma, p arbitrary large, and w = $0^p 1^p$. Which makes y = $0^k$ for some k >= 1.

Source Link
gnasher729
  • 31.6k
  • 35
  • 55

Just show that after processing $0^n$ and $0^{n’}$ with n != n’ you must have reached two different states. (Which is easy: In one state, processing $1^n$ leads to an accepting state, in the other state it doesn’t). Therefore there is no finite set of states.