2
$\begingroup$

In Sipser's "Introduction to the Theory of Computation" it states "A GNFA accepts a string $w$ in $Σ^{*}$ if $w = w_1 w_2 · · · w_k$ , where each $w_i$ is in $Σ^{*}$".

However, wouldn't a more precise definition be "A GNFA accepts a string $w$ in $Σ^{*}$ if $w = w_1 w_2 · · · w_k$ , where each $w_i$ is in $Σ$" ?

$\endgroup$
  • 1
    $\begingroup$ You only quote part of the definition. Please give the full one; it may be relevant. $\endgroup$ – Raphael Aug 13 '16 at 9:00
0
$\begingroup$

If a GNFA $A$ reconizes $\Sigma^{*}$, then $\epsilon \in \Sigma^{*}$ must be accepted. However $\epsilon \not\in \Sigma $.

$\endgroup$
  • $\begingroup$ WIth $k=0$ the proposed alternate definition admits $\varepsilon$ as well. $\endgroup$ – Raphael Aug 13 '16 at 9:01
  • $\begingroup$ How would it be true if the alphabet must contain a symbol? Or are you saying that it would be vacuously true? $\endgroup$ – Aristu Aug 13 '16 at 12:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.