Tại sao {a^nb^n | n> = 0} không thường xuyên?

Question

Trong một CS dĩ nhiên là tôi đang tham gia có một ví dụ về một ngôn ngữ mà không phải là thường xuyên:

{a^nb^n | n >= 0} 

tôi có thể hiểu rằng nó không phải là bình thường vì không có hữu hạn Nhà nước Automaton/Máy có thể được viết rằng xác nhận và chấp nhận đầu vào này vì nó thiếu một thành phần bộ nhớ. (Vui lòng sửa tôi nếu tôi sai)

wikipedia entry on Regular Language cũng liệt kê ví dụ này, nhưng không cung cấp bằng chứng (toán học) tại sao nó không phải là thường xuyên.

Ai có thể khai sáng cho tôi về điều này và cung cấp bằng chứng cho điều này hay chỉ cho tôi một tài nguyên tốt?

Answer 1

Điều bạn đang tìm kiếm là Pumping lemma for regular languages.

Dưới đây là một example với vấn đề của bạn chính xác:

Ví dụ:
Hãy L = {a m b ^m | m ≥ 1}.
Sau đó, L không thường xuyên.
Bằng chứng: Hãy để n được như trong Bơm Bổ đề.
Cho phép w = a ⁿ b ⁿ.
Hãy để w = xyz như trong Pumpma Lemma.
Do đó, xy z ∈ L, tuy nhiên, xy z chứa số tiền nhiều hơn số.

Answer 2

Vì bạn không thể viết một máy trạng thái hữu hạn sẽ 'đếm' các chuỗi ký tự 'a' và 'b' giống hệt nhau. Tóm lại, FSM không thể 'đếm' được. Hãy thử tưởng tượng một FSM như vậy: bạn sẽ đưa ra bao nhiêu trạng thái cho ký hiệu 'a'? Bao nhiêu 'b'? Điều gì xảy ra nếu chuỗi nhập liệu của bạn có nhiều hơn?

Lưu ý rằng nếu bạn có n < = X với X một giá trị số nguyên bạn có thể chuẩn bị FSM đó (bằng cách có một với nhiều trạng thái, nhưng vẫn là số hữu hạn); ngôn ngữ như vậy sẽ là thường xuyên.

Answer 3

Tự động hữu hạn Nhà nước không có cấu trúc dữ liệu (ngăn xếp) - bộ nhớ như trong trường hợp đẩy xuống tự động. Yeah nó có thể cung cấp cho bạn một số 'a's theo sau bởi một số' b nhưng không chính xác số tiền của 'a' theo sau là không 'b'.