Skip to main content
Computer Science

Return to Question

added 2 characters in body
Source Link
D.W. ♦
D.W. ♦
  • 165.6k
  • 21
  • 230
  • 490

I am reading Michael Sipser's "Theory of Computation" 2nd edition, chapter 1 , Topic "Non determinism" ( Section 1.2 )

Let's use this E-NFA as an example

enter image description here

My question is, do we transition along "epsilon transition" before reading any input or after reading any input.?

assume input is "a"

Case 1: Before reading any input, in that case the machine would start in two states q1 and q3. Then it would read the input "a", q1 would transition to trap state and q3 would transition to q1 state, which is an accept state

enter image description here

Case 2: After reading any input, in that case the machine would start in state q1, it would read "a" and move to trap state + branch into 2 different states of epsilon transition i.e q1 and q3

I understand the fact that an "epsilon transition" just implies existence at both the states at the same time, but is that before reading the input or after reading the input?

enter image description here

Due to this, i am facing issues in the section "equivalence of DFAs and NFAs" in the same book.

Can someone explain me which is the correct case?

I am reading Michael Sipser's "Theory of Computation" 2nd edition, chapter 1 , Topic "Non determinism" ( Section 1.2 )

Let's use this E-NFA as an example

enter image description here

My question is, do we transition along "epsilon transition" before reading any input or after reading any input.

assume input is "a"

Case 1: Before reading any input, in that case the machine would start in two states q1 and q3. Then it would read the input "a", q1 would transition to trap state and q3 would transition to q1 state, which is an accept state

enter image description here

Case 2: After reading any input, in that case the machine would start in state q1, it would read "a" and move to trap state + branch into 2 different states of epsilon transition i.e q1 and q3

I understand the fact that an "epsilon transition" just implies existence at both the states at the same time, but is that before reading the input or after reading the input

enter image description here

Due to this, i am facing issues in the section "equivalence of DFAs and NFAs" in the same book.

Can someone explain me which is the correct case

I am reading Michael Sipser's "Theory of Computation" 2nd edition, chapter 1 , Topic "Non determinism" ( Section 1.2 )

Let's use this E-NFA as an example

enter image description here

My question is, do we transition along "epsilon transition" before reading any input or after reading any input?

assume input is "a"

Case 1: Before reading any input, in that case the machine would start in two states q1 and q3. Then it would read the input "a", q1 would transition to trap state and q3 would transition to q1 state, which is an accept state

enter image description here

Case 2: After reading any input, in that case the machine would start in state q1, it would read "a" and move to trap state + branch into 2 different states of epsilon transition i.e q1 and q3

I understand the fact that an "epsilon transition" just implies existence at both the states at the same time, but is that before reading the input or after reading the input?

enter image description here

Due to this, i am facing issues in the section "equivalence of DFAs and NFAs" in the same book.

Can someone explain me which is the correct case?

Source Link
Pratik Hadawale
Pratik Hadawale
  • 335
  • 4
  • 14

Confusion regarding the intuition behind epsilon transition in NFA

I am reading Michael Sipser's "Theory of Computation" 2nd edition, chapter 1 , Topic "Non determinism" ( Section 1.2 )

Let's use this E-NFA as an example

enter image description here

My question is, do we transition along "epsilon transition" before reading any input or after reading any input.

assume input is "a"

Case 1: Before reading any input, in that case the machine would start in two states q1 and q3. Then it would read the input "a", q1 would transition to trap state and q3 would transition to q1 state, which is an accept state

enter image description here

Case 2: After reading any input, in that case the machine would start in state q1, it would read "a" and move to trap state + branch into 2 different states of epsilon transition i.e q1 and q3

I understand the fact that an "epsilon transition" just implies existence at both the states at the same time, but is that before reading the input or after reading the input

enter image description here

Due to this, i am facing issues in the section "equivalence of DFAs and NFAs" in the same book.

Can someone explain me which is the correct case