nullability (Regular Expressions)

Question

Trong "Dẫn xuất của Regular Expressions" Brzozowski và ở những nơi khác, hàm δ (R) trở λ nếu R là nullable, và ∅ khác, bao gồm các điều khoản như sau:

δ(R1 + R2) = δ(R1) + δ(R2) 
δ(R1 · R2) = δ(R1) ∧ δ(R2) 

rõ ràng, nếu cả hai R1 và R2 là nullable sau đó (R1 R2 ·) là nullable, và nếu một trong hai R1 hoặc R2 là nullable sau đó (R1 + R2) là nullable. Tuy nhiên, điều không rõ ràng với tôi là những mệnh đề trên có nghĩa là gì. Suy nghĩ của tôi đầu tiên, lập bản đồ (+), (·), hoặc các toán tử Boolean để bộ thường xuyên là vô nghĩa, vì trong trường hợp cơ sở,

δ(a) = ∅ (for all a ∈ Σ) 
δ(λ) = λ 
δ(∅) = ∅ 

và λ không phải là một bộ (cũng không phải là một tập hợp các kiểu trả về của δ, đó là một biểu thức chính quy). Hơn nữa, ánh xạ này không được chỉ ra, và có một ký pháp riêng biệt cho nó. Tôi hiểu tính vô dụng, nhưng tôi bị mất về định nghĩa tổng, sản phẩm và các phép toán Boolean theo định nghĩa của δ: are hoặc ∅ được trả về từ δ (R1) δ δ (R2), ví dụ , trong định nghĩa tắt δ (R1 · R2)?

Answer 1

Tôi nghĩ rằng bạn đang bị cuốn hút bởi các quyền tự do phi lý của tác giả. Kiểu trả về của δ (R) chắc chắn là một tập hợp, hay đúng hơn là một ngôn ngữ. Nếu bạn nhìn vào định nghĩa:

bạn có thể thấy rằng có một sự mâu thuẫn trong kiểu trả về, chính thức λ là một yếu tố, nhưng ∅ là ngôn ngữ trống rỗng ... Những gì nó nên nói là:

thực tế mà tác giả sử dụng λ cho cả chuỗi rỗng cũng như ngôn ngữ chỉ chứa các chuỗi rỗng là tiếp tục chứng minh theo định nghĩa của ông về điều hành sao Kleene:

Rõ ràng, phần cuối cùng phải là nếu chúng ta muốn trở thành thực thể.

Cho biết kiểu trả về của δ (R) là một tập hợp, hoặc đúng hơn là một ngôn ngữ, các phương trình bạn đưa ra có ý nghĩa hoàn hảo và thể hiện chính xác những gì bạn mô tả.

Answer 2

Tôi nghĩ rằng bạn đã đúng bản đồ + và ^ thành boolean or và and tương ứng. Nó trông giống như hai dòng bạn trích dẫn thỏa thuận với luân phiên (tổng hợp) và nối (sản phẩm):

δ(R1 + R2) = δ(R1) + δ(R2) 

Các luân phiên của R1 và R2 là nullable nếu R1 là nullable, R2 là nullable, hoặc cả hai số R1 và R2 đều không thể thực hiện được.

δ(R1 · R2) = δ(R1) ∧ δ(R2) 

Các nối của R1 và R2 chỉ nullable nếu cả hai R1 và R2 là nullable.

Xem here để thực hiện Haskell các quy tắc này.

Answer 3

(Tôi không thể xem bài viết của Brzozowski để hiểu rõ hơn ý nghĩa của nó), nhưng tôi có thể đề xuất 2 cách diễn giải ký hiệu này (ngoài việc ký hiệu với ký hiệu, tôi thấy, không có câu hỏi: ý nghĩa định nghĩa của định nghĩa này được hiểu rõ):

1) Ở bên trái định nghĩa, chúng tôi chỉ có các mẫu "cú pháp" cho các cụm từ thông dụng. Ở bên phải, chúng tôi sản xuất các bộ; hãy nhớ rằng, biểu thức chính quy là cách biểu thị ngôn ngữ (tập hợp) và cách này để viết định nghĩa trở nên dễ hiểu: ở bên phải, chúng tôi chỉ đơn giản sử dụng một số biểu thức chính quy (đơn giản) như một cách ngắn để tham chiếu bộ. Tức là, ∅ nghĩa là ngôn ngữ trống (tập rỗng) và λ (nếu diễn giải là cụm từ thông dụng) nghĩa là ngôn ngữ chỉ chứa từ trống (tập hợp với phần tử này).

Các thao tác chỉ hoạt động trên các bộ: có thể là công đoàn và giao lộ.

Nếu ký pháp được diễn giải theo cách này, không có mâu thuẫn với ký pháp được sử dụng để xác định trường hợp cơ sở: một lần nữa, "a" là cụm từ thông dụng.

2) Chúng tôi xây dựng biểu thức chính quy ở bên phải, ngay từ đầu, nhưng tác giả đã mở rộng các hoạt động xây dựng cụm từ thông dụng với nêm, có ngữ nghĩa giao điểm của ngôn ngữ.