ps -o pid,ppid,stat,exe -e | grep deleted has "(deleted)" appended to the executable path

On Linux, ps gets that information by doing a readlink("/proc/<pid>/exe").

$ ls -l /proc/self/exe
lrwxrwxrwx 1 chazelas chazelas 0 Dec 17 10:35 /proc/self/exe -> /usr/bin/ls

That file is a magic symlink to the file that the given process (or any of its ancestor as not all processes execute files) last executed. If the file has been deleted (and potentially replaced by a new version like after a package update), a (deleted) is appended to the string returned by readlink(). That symlink can still be followed to the actual deleted file (and in that way it is magic).

$ cp /bin/sleep .
$ ./sleep 1h &
[1] 17417
$ ls -ld "/proc/$!/exe"
lrwxrwxrwx 1 chazelas chazelas 0 Dec 17 10:38 /proc/17417/exe -> /home/chazelas/sleep*
$ rm sleep
$ ls -ld "/proc/$!/exe"
lrwxrwxrwx 1 chazelas chazelas 0 Dec 17 10:38 /proc/17417/exe -> '/home/chazelas/sleep (deleted)'

New version of sleep:

$ cp /bin/sleep .
$ ps -o exe -p "$!"
EXE
/home/chazelas/sleep (deleted)
$ ls -ld "/proc/$!/exe"
lrwxrwxrwx 1 chazelas chazelas 0 Dec 17 10:38 /proc/17417/exe -> '/home/chazelas/sleep (deleted)'
$ ls -iLd "/proc/$!/exe" sleep
3114951 /proc/17417/exe*  3114969 sleep*

With -L ls follows the link (by using stat() instead of lstat()) and it is able to get the corresponding inode number.

We see that's two different files (different inode number).

$! is still running the old deleted version of sleep, that file has no path on the filesystem other than that /proc/$!/exe magic symlink¹.

/home/chazelas/sleep is now a different executable, so removing that (deleted) would be wrong as it would refer to the wrong file. Here, since exe is the last field, you can remove it by piping the output to:

sed 's/ (deleted)$//'

$ ps -o pid,ppid,stat,exe
    PID    PPID STAT EXE
  18928   11196 Ss   /usr/bin/zsh
  18943   18928 SN   /home/chazelas/sleep (deleted)
  18967   18928 R+   /usr/bin/ps
$ ps -o pid,ppid,stat,exe | sed 's/ (deleted)$//'
    PID    PPID STAT EXE
  18928   11196 Ss   /usr/bin/zsh
  18943   18928 SN   /home/chazelas/sleep
  18968   18928 R+   /usr/bin/ps
  18969   18928 S+   /usr/bin/sed

But again, that would be a lie as /home/chazelas/sleep is not the executable that process 18943 is running, it's another sleep command that is now nowhere to be found as it has been deleted since that process executed it.

^{¹ and corresponding /proc/<pid>/exe for other processes potentially executing it or /proc/<pid>/fd/<fd> for processes having that file opened on some fd, or potentially some hard links to it.}