Chiều dài bơm tối thiểu cho các ngôn ngữ thông thường sau đây

Question

Độ dài bơm tối thiểu cho các ngôn ngữ sau là gì?

1. Ngôn ngữ trống
2. (01)*
3. 10(11*0)*0
4. 1011
5. 011 U 0*1*

Dưới đây là giải pháp của tôi. Nêu tôi sai vui long chân chỉnh tôi.

1. p = 0 bởi vì ngôn ngữ không có dây bơm
2. p = 2 vì 01 là chuỗi ngắn nhất có thể được bơm
3. p = 5 vì 10100 là chuỗi ngắn nhất có thể được bơm
4. p = 0 vì chuỗi không thể được bơm
5. p = 1 vì chuỗi 0 có thể được bơm

Tôi không chắc chắn về câu trả lời của mình, vì vậy mọi trợ giúp đều được đánh giá cao. Cảm ơn rất nhiều!

Answer 1

Theo Patrick87, chiều dài bơm tối thiểu được xác định là số lần chuyển tiếp tối đa bạn có thể thực hiện trong DFA thu nhỏ mà không cần truy cập một số trạng thái hai lần. Sau đó, quy trình sẽ trở thành chuyển đổi biểu thức chính quy của bạn thành NFA, chuyển đổi NFA thành DFA, giảm thiểu DFA và đếm đường dẫn dài nhất dọc theo các cạnh được chỉ đạo mà không cần truy cập cùng một trạng thái hai lần. Để giới thiệu về chuyển đổi và giảm thiểu này, xem ví dụ miễn phí của Torben Mogensen, Basics of Compiler Design chương 2.6, 2.8.

Theo định nghĩa này,

1. p = 0, vì không có hiệu ứng chuyển tiếp trong DFA giảm thiểu cho ngôn ngữ trống rỗng.
2. p = 1. DFA thu nhỏ cho (01)* có hai trạng thái và bạn chỉ có thể thực hiện một chuyển đổi mà không phải kết thúc ở trạng thái chấp nhận ban đầu.
3. p = 3. DFA thu nhỏ cho 10(11*0)*0 sẽ có trạng thái phải được truy cập hai lần cho biểu thức con (11*0)* là một phần của đạo hàm.
4. p = 4. DFA thu nhỏ cho 1011 có chính xác 4 cạnh và không có đệ quy.
5. p = 1. Ngôn ngữ 011 là một tập hợp con của ngôn ngữ 0*1*, vì vậy 011 U 0*1* = 0*1*. Và kể từ khi không 0 hoặc 1 có thể được bơm, người ta chỉ có thể làm theo một cạnh không đệ quy.

Answer 2

Tôi nghĩ rằng câu trả lời của Simon có thể là một chút đi. Bạn làm, trên thực tế, cần phải đi một chu kỳ ở đâu đó. Bổ đề bơm yêu cầu rằng đường dẫn được thực hiện để nhận ra chuỗi bao gồm một chu trình (đây là 'y' của 'xyz' bơm của bổ đề).Chúng ta có thể thực hiện chu trình này nhiều lần tùy ý, mà bơm chuỗi.

1. Đây phải là 1. Độ dài bơm tối thiểu phải luôn lớn hơn 0, ngay cả khi không có chuỗi trong ngôn ngữ.
2. Điều này nên là 2. Nếu p = 1, chúng tôi không thể bơm 01 (vì y phải bằng 0 và 001 không phải là ngôn ngữ).
3. Điều này phải là 5.
4. Điều này cũng phải là 5. Nếu chúng tôi đặt p = 4, thì chúng tôi yêu cầu "1011" có thể bơm được (không phải vì nó là chuỗi duy nhất trong ngôn ngữ).
5. p = 1.