0

Here is the problem:

Consider a NFA, M = (K, Σ, Δ, s, F) with (p, a, q) ∈ Δ. Prove that (pʹ, aw) ⊢∗ (qʹ, w) for any w ∈ Σ∗, q′ ∈ E(q) and p′ with p ∈ E(p′).

Thanks in advance.

Kudayar Pirimbaev
  • 319
  • You need to be more explicit about the details of the formalism you're working in. What is the $E$ that appears only in the conclusion and not in any of the assumptions? What are the various components of the NFA tuple in the formalism you're using? Is $\Delta$ both the set of states and the alphabet, or should the assumption have been $a\in\Sigma$? If not, when what does $(p',aw)\vdash*(q',w)$ even mean? – hmakholm left over Monica Mar 21 '13 at 13:39
  • @Henning: $K$ is the state set, $\Sigma$ the alphabet, $\Delta$ the set of transitions, $s\in K$ the initial state, and $F$ the set of final (acceptor) states. There is an $a$-transition from state $p$ to state $q$, and $(p',aw)\vdash^*(q',w)$ should mean that if $M$ is in state $p'$ reading $aw$, there is a sequence of transitions leaving $M$ in state $q'$ reading $w$. At a guess $E(q)$ is the equivalence class of $q$ with respect to some equivalence relation on $K$, and the problem is to prove that equivalent states can be substituted for one another in computations, but we really need ... – Brian M. Scott Mar 21 '13 at 14:27
  • ... to know how $E$ is defined. – Brian M. Scott Mar 21 '13 at 14:28
  • @BrianM.Scott thanks, was on lectures, couldn't answer myself earlier – Kudayar Pirimbaev Mar 21 '13 at 18:13
  • E(q) is the set of states that have e-transitions from q, so since q' is an element of E(q), there is a transition (q, e, q') – Kudayar Pirimbaev Mar 21 '13 at 18:15

1 Answers1

0

Since $p'\in E(p)$ and $q'\in E(q)$, $(p',aw)\vdash(p,aw)\vdash(q,w)\vdash(q',w)$, using the transitions $(p',\epsilon,p),(p,a,q)$, and $(q,\epsilon,q')$ in that order.

Brian M. Scott
  • 616,228