Geek asks and answers

How to find the intersection of two NFAs

In DFA, we can intersect two automata by performing a cross-product of the states of two automata and accepting the states that are accepted in both initial automata. Union is carried out in a similar way. Be that as it may, although I can make the union in NFA easy using the epsilon transition, how can I intersect them?

+3
source share
5 answers

You can use cross-product design on the NFA in the same way as DFA. The only changes to how you handle & epsilon; transitions. In particular, for each state (q i, r j) in the automaton with cross products you add a transition from this state to each pair of states (q k, r j), where there is a transition to the first machine from q i to q k and each pair of states (q i, r k), where there is a transition on the second machine from r j to r <sub> xub>.

Alternatively, you can always convert NFAs to DFAs and then calculate the cross product of these DFAs.

Hope this helps!

+5
source

there is a huge mistake in templatetypedef's answer.

automaton product L1 and L2, which are NFA:

new states Q = product of states L1 and L2.

now transition function :

a - symbol in the union of alphabets of automata

delta ((q_1, q_2), a) = delta_L1 (q_1, a) X delta_L2 (q_2, a)

, , resualt delta_L1 (q_1, a), , delta_L2 (q_1, a).

templatetypedef , (qk, rk) .

+2

De Morgan Laws: B = (A 'U B') '

NFA , .

0

Probabaly - , , , , . . , , e, e, .

:

  • m1 {w | w '11' }
  • m2 {w | w '00' }

Intiuitivly m = m1 ∩ m2 - , , "11", "00" . , .

.

m = (Q, Σ, Δ, q0, F)

  • m. , , m1 m2. , a1, a2 m1 b1, b2, m2, Q : a1b1, a2b1, a1b2, a2b2. , , m1, m2.

  • Σ, , , , m1 m2.

  • q0 Q, m1, m2. (a1b1, .)

  • F s IF IF, , s, m1, m2 .

  • , ​​ Δ; : Δ (a1b1, E) = Δ (m1) (a1, E) x Δ (m2) (b1, E), , . , a1b1 a1 b1 . "" , , E, , . . (a1, E) m1, Δ (b1, E) m2, m, - .

0

An alternative to constructing a product machine allows more complex acceptance criteria. Typically, the NFA accepts an input string when it reaches any of a set of host end states. This can be extended to Boolean state combinations. In particular, you are building an automaton for crossing, as you do for combining, but you think that the received automaton accepts the input line only when it is in (which corresponds to), accepting the final states in both automata.

-1
source

More articles:


All Articles