Skip to main content
3 votes

Determining if a word of specific length exists that is not accepted by a NFA

In the following paper, a regular expression $r$ over some alphabet $\Sigma$ is constructed that accepts the set $INVALC_{M,w}$ of invalid computations of a deterministic in-place Turing machine $M$ ...
Hermann Gruber's user avatar

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