Bơm bổ đề (Ngôn ngữ thông thường)

Question

Tôi cần trợ giúp về vấn đề lemma bơm.

L = { {a,b,c}* | #a(L) < #b(L) < #c(L) } 

Đây là những gì tôi có cho đến nay:

y = uvw is the string from the pumping lemma. 

tôi để y = abbc^n, n là độ dài từ Bổ đề bơm. y nằm trong L vì số lượng a: s nhỏ hơn số b: s, và số lượng b: s nhỏ hơn số c: s.

Tôi cho u = a, v = bb và w = c^n. | uv | < y, như đã nêu trong bổ đề bơm. Nếu tôi "bơm" (bb)^2 thì tôi nhận được

y = abbbbc^n which violates the rule #b(L) < #c(L). 

Điều này có đúng không? Tôi đang trên "con đường đúng"?

Cảm ơn

Answer 1

Ý tưởng chính của việc bơm Bổ đề là để cho bạn biết rằng khi bạn có một ngôn ngữ thông thường L với vô số thuật ngữ có một mô hình bằng ngôn ngữ mà lặp đi lặp lại mãi mãi.

Cụm từ thông dụng được liên kết với ngôn ngữ đó sẽ chứa KLEENE-STAR (mẫu).

Tự động kết hợp với biểu thức chính quy (và ngôn ngữ) đó sẽ chứa một vòng lặp.

Bằng chứng được thực hiện bằng nguyên tắc chim bồ câu.

này rất gợi ý.

Lưu ý rằng tất cả các cụm từ phải bắt đầu bằng q0 và kết thúc bằng qn trong trường hợp này. Vì vậy, các automata xác định ngôn ngữ là hữu hạn (tối đa N tiểu bang), do đó, có một số giới hạn của các tiểu bang, nhưng các từ (tức là các điều khoản) có thể có> N chữ cái. Nguyên tắc chim bồ câu cho chúng ta biết rằng phải có một trạng thái đạt tới 2 lần, vậy tại trạng thái đó một vòng lặp sẽ xuất hiện.

Trong ký hiệu, bạn có thể làm cho sự tương ứng với hình ảnh như vậy:

• u của bạn là x từ hình ảnh

• v là y theo hình ảnh

• w là z từ hình ảnh

Để đến từ q0 đến qn, bạn có thể sử dụng bất kỳ chuỗi nào từ tập hợp: { uw , uvw, uvvw, uvvvw, ... }.

Trong trường hợp này mô hình P là y, tập X là {xz xyz xyyz xyyyz ...} và S là length(x)+length(y).