Bổ sung DFA
Nếu (Q, ∑, δ, q 0 , F) là một DFA chấp nhận ngôn ngữ L, thì phần bổ sung của DFA có thể nhận được bằng cách hoán đổi các trạng thái chấp nhận của nó với các trạng thái không chấp nhận của nó và ngược lại.
Chúng tôi sẽ lấy một ví dụ và trình bày chi tiết điều này bên dưới -
DFA này chấp nhận ngôn ngữ
L = {a, aa, aaa, .............}
qua bảng chữ cái
∑ = {a, b}
Vì vậy, RE = a + .
Bây giờ chúng ta sẽ hoán đổi các trạng thái chấp nhận của nó với các trạng thái không chấp nhận của nó và ngược lại và sẽ nhận được như sau:
DFA này chấp nhận ngôn ngữ
Ľ = {ε, b, ab, bb, ba, ...............}
qua bảng chữ cái
∑ = {a, b}
Note - Nếu chúng ta muốn bổ sung một NFA, trước tiên chúng ta phải chuyển đổi nó thành DFA và sau đó phải hoán đổi các trạng thái như trong phương pháp trước.