2 votes
Accepted

Why do we need empty string transitions in the NFA intended to accept this singleton language?

The $\epsilon$ edge is unnecessary: the NFA without it is equivalent. I'm not familiar with the text, but I suspect it emerged from a generalized recursive process for generating an NFA for the ...
TomKern's user avatar
  • 2,912
2 votes
Accepted

Finding a bound for existential quantification

Hint: I think you are aware of the fact that for $\gamma \in \Sigma^*$ and $m \in \omega$, $|\gamma^m| = m |\gamma|$. So if $\alpha^{(x-2)(|\alpha|-1)}=\beta^t$, ${(x-2)(|\alpha|-1)}|\alpha|=t|\beta|$....
Rob Arthan's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible