Why no DPDA can accept Palindrome? (according to this proof)

This proof is from the book “Introduction to Languages and the Theory of Computation” by John C. Martin.

My question is from the pink part at the second page:

It follows in particular that no sequence of moves can cause M to empty its stack.

and further, it talks about $ y_x$ that is my second question. I can’t understand what $ y_x$ is.

I’ll appreciate it if someone please describe me the whole proof.

First page of the proof Second page of the proof

How to accept only user identity keys of type ed25519 on OpenSSH Linux server?

I want to force all users to use only ed25519 type keys when logging in via SSH / SFTP to a Linux server which is running a recent version* of OpenSSH.

The reasons include:

In many cases, SSH keys have been completely overlooked in identity and access management planning, implementation, and audits. Users have been able to create and install keys without oversight and controls. This has led to violations of corporate access policies and dangerous backdoors.

Information security starts from controlling who is given access to systems and data. If there is no control over access, there is no security, no confidentiality, no integrity, and no guarantees of continued operation

Source: https://www.ssh.com/iam/ssh-key-management/

However, I do not wish to remove the ability for a user to manage their own SSH keys (including adding, removing, changing the keys). My only objective is to mandate that the key used is of type ed25519.

How can this be accomplished while maintaining the above user privileges and while maintaining this setting?

AuthorizedKeysFile  .ssh/authorized_keys 

The main (non-default) sshd_config settings I’m using on this server include:

The only host key enabled: HostKey /etc/ssh/ssh_host_ed25519_key  PermitRootLogin no PasswordAuthentication no ChallengeResponseAuthentication no UsePAM yes AuthorizedKeysFile  .ssh/authorized_keys KexAlgorithms curve25519-sha256@libssh.org MACs hmac-sha2-512-etm@openssh.com Ciphers chacha20-poly1305@openssh.com AllowUsers user@host ... 

However, with those settings a user can still select an older user identity key type and use it to log in. My only objective now is to stop a user from getting access except via an ed25519 user identity key. How?

*Actually running: OpenSSH_8.1p1, OpenSSL 1.1.1d

Regular expression for language that does not accept x string (3 letters, |x|=3)

The language I am interested in is $ L=\{w∈\{a,b,c\}^*| w$ contains “$ bac$ ” but not “$ cab$ $ \}$ . I am thinking that the result will have the form $ L=X_1X_2X_3$ , where $ X_1=\{w∈\{a,b,c\}^*| w$ does not contain “$ ca$ ” at the end nor “$ cab$ ” anywhere$ \}$ , $ X_2=$ $ bac$ ” and $ X_3=\{w∈\{a,b,c\}^*| w$ does not contain “$ ab$ ” at the start nor “$ cab$ ” anywhere$ \}$ . What I find difficult to express is that “$ cab$ ” does not appear anywhere in $ X_1, X_3$ (the situation for “ca” and “ab” is simple because they consist only of 2 letters, we can split $ X_1, X_3$ so that the “cab” problem remains). I have tried creating a NFA for this purpose but the automata needs to have quite a few loops (thus it is hard to find the regular expression). My question is whether there is a clever way to find the representation of non-existance of “cab”, other than counting all the possibilities in the NFA that accepts such strings. If there is no such way, how can I find the regular expression of L from the start?

Why do intuitionists accept the nonconstructive proof that the halting problem is undecidable?

On the intuitionism page at Stanford Encyclopedia of Philosophy (SEP), it’s said in Section 3.3 that

Because of the finiteness of a natural number in contrast to, for example, a real number, many arithmetical statements of a finite nature that are true in classical mathematics are so in intuitionism as well. For example, in intuitionism every natural number has a prime factorization; there exist computably enumerable sets that are not computable

This uncomputability result must necessarily use the halting problem, whose uncomputability is proved unconstructively, as it relies on the law of the excluded middle: TM $ M$ of input $ \langle M\rangle$ either halts or not. This is not constructive because it might be impossible to know whether the TM runs forever. If you can prove for every case that the TM runs forever when it indeed does, then the collection of such proofs results in an algorithm that decides haltingness. So this proof is not constructive. But SEP says that intuitionists accept it! Isn’t intuitionism a constructive theory? Or are there other constructive proofs of the halting problem that I don’t know?