HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

in NFA is every state itself contained in set generated by transition function when considering epsilon transition from that state?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
itselfgeneratednfaepsiloneveryfunctioncontainedthatstatetransition

Problem

in $\epsilon$-NFA (NFAs involving $\epsilon$ transitions) when we have $\epsilon$ transitions, I understand it as where can we go if we don't read any symbol from the input tape, then I think every state $q$ from which we are considering transition must belong to $\delta(q,\epsilon)$ because if we don't read anything, we can of course stay in the state where we are at now, I am asking whether $\epsilon$ transition from state to itself is assumed? for example, if we have some state $q_i$ which has $\epsilon$ transition to state $q_j$ then is $\delta(q_i, \epsilon)$=$\{q_j, q_i\}$ or just $\{q_j\}$, I think it's just matter of convention and wouldn't make significant difference.

Solution

The answer depends on what you mean by $\delta(q,\epsilon)$.

First possibility is that $\delta$ specifies the transitions (the arrows in the state diagram). In that case we have $\delta(q_i,\epsilon) =\{q_j\}$ to indicate the single edge.

The other possibility is that $\delta$ specifies computations, sometimes called the extended transition function: $q\in \delta(p,w)$ iff there is a computation on the input word $w$ starting in state $p$ and ending in state $q$. In that case $\delta(q_i,\epsilon) =\{q_i,q_j\}$ is what we need.

Context

StackExchange Computer Science Q#167231, answer score: 4

Revisions (0)

No revisions yet.