Định lý Arden

Để tìm ra biểu thức chính quy của một Automaton hữu hạn, chúng tôi sử dụng Định lý Arden cùng với các thuộc tính của biểu thức chính quy.

Statement -

Để cho PQ là hai biểu thức chính quy.

Nếu P không chứa chuỗi rỗng, sau đó R = Q + RP có một giải pháp duy nhất đó là R = QP*

Proof -

R = Q + (Q + RP) P [Sau khi đặt giá trị R = Q + RP]

= Q + QP + RPP

Khi chúng ta đặt giá trị của R đệ quy lặp đi lặp lại, chúng ta nhận được phương trình sau:

R = Q + QP + QP 2 + QP 3 … ..

R = Q (ε + P + P 2 + P 3 +….)

R = QP * [Vì P * đại diện cho (ε + P + P2 + P3 +….)]

Do đó, đã chứng minh.

Các giả thiết để áp dụng định lý Arden

  • Sơ đồ chuyển tiếp không được có chuyển tiếp NULL
  • Nó phải chỉ có một trạng thái ban đầu

phương pháp

Step 1- Lập phương trình ở dạng sau cho tất cả các trạng thái của DFA có n trạng thái với trạng thái ban đầu q 1 .

q 1 = q 1 R 11 + q 2 R 21 +… + q n R n1 + ε

q 2 = q 1 R 12 + q 2 R 22 +… + q n R n2

…………………………

…………………………

…………………………

…………………………

q n = q 1 R 1n + q 2 R 2n +… + q n R nn

Rij đại diện cho tập hợp các nhãn của các cạnh từ qi đến qj, nếu không có cạnh như vậy tồn tại, thì Rij = ∅

Step 2 - Giải các phương trình này để có phương trình về trạng thái cuối cùng về Rij

Problem

Tạo một biểu thức chính quy tương ứng với dữ liệu tự động được cung cấp bên dưới:

Solution -

Ở đây trạng thái ban đầu và trạng thái cuối cùng là q1.

Các phương trình cho ba trạng thái q1, q2 và q3 như sau:

q 1 = q 1 a + q 3 a + ε (ε chuyển động là do q1 là trạng thái ban đầu0

q 2 = q 1 b + q 2 b + q 3 b

q 3 = q 2 a

Bây giờ, chúng ta sẽ giải ba phương trình này -

q 2 = q 1 b + q 2 b + q 3 b

= q 1 b + q 2 b + (q 2 a) b (Giá trị thay thế của q 3 )

= q 1 b + q 2 (b + ab)

= q 1 b (b + ab) * (Áp dụng Định lý Arden)

q 1 = q 1 a + q 3 a + ε

= q 1 a + q 2 aa + ε (Giá trị thay thế của q 3 )

= q 1 a + q 1 b (b + ab *) aa + ε (Giá trị thay thế của q 2 )

= q 1 (a + b (b + ab) * aa) + ε

= ε (a + b (b + ab) * aa) *

= (a + b (b + ab) * aa) *

Do đó, biểu thức chính quy là (a + b (b + ab) * aa) *.

Problem

Tạo một biểu thức chính quy tương ứng với dữ liệu tự động được cung cấp bên dưới:

Solution -

Ở đây trạng thái đầu là q 1 và trạng thái cuối là q 2

Bây giờ chúng ta viết ra các phương trình -

q 1 = q 1 0 + ε

q 2 = q 1 1 + q 2 0

q 3 = q 2 1 + q 3 0 + q 3 1

Bây giờ, chúng ta sẽ giải ba phương trình này -

q 1 = ε0 * [Như, εR = R]

Vì vậy, q 1 = 0 *

q 2 = 0 * 1 + q 2 0

Vì vậy, q 2 = 0 * 1 (0) * [Theo định lý Arden]

Do đó, biểu thức chính quy là 0 * 10 *.