程序代写代做代考 ## Proof (by contradiction)

## Proof (by contradiction)

Assume GOOD-TM is regular.

Then exists a FA with N states which accepts

for w with more than N lettters

there exists strings x, y ≠ ε, and z s.t.

– w = xyz

– length(x) + length(y) ≤ N

– xyz, xyyz, .. , x$y^n$z are words in GOOD-TM

Because y repeating many times, if $y^i$ contains one row in TM, then $y^{2i}$ will have two same rows,

which is invalid and not GOOD-TM. Thus, it is a contradiction.