PPT Slide

Theorem 2.2.3: for DFA A with N states(i) L(A) ° _ iff there is z_L(A) with len(z) < N(ii) L(A) is infinite iff there is z_L(A) with N Š len(z) < 2N.

Theorem 2.2.3 assures us that there are algorithmsto test each of the following properties of DFAs:

• L(A) = _ — check if z_L(A) for all len(z)

  • L(A) = _* — test _L(A) = _

  • L(A) infinite — check if z_L(A) for all NŠlen(z)<2N

  • L(A1) _ L(A2) — test if L(A1) _ _L(A2) = _

  • L(A1) = L(A2) — test if L(A1) _ L(A2) and  L(A2) _ L(A1)

  Previous slide

  Next slide

  Back to first slide

  View graphic version