Thông thường là gì?

Question

Đây là một câu hỏi khoa học máy tính nhiều hơn một câu hỏi lập trình, nhưng tôi cho rằng đây là nơi tốt nhất trong số tất cả các trang liên quan để hỏi điều này.

Khi tôi phát hiện Cụm từ thông dụng và tra cứu thuật ngữ tôi giả định rằng thuộc tính "thông thường" này đề cập đến thực tế là ngôn ngữ của biểu thức có cấu trúc có thể xác định rõ ràng. Tuy nhiên, khi đọc về chủ đề và lý thuyết đằng sau điều này tôi đã học được rằng có nhiều loại ngôn ngữ không thường xuyên, và từ cách chúng được định nghĩa rõ ràng là một mẫu có thể được ghép với chúng. Một ngôn ngữ như vậy là (a^n) (b^n). Rõ ràng đây là một mẫu, nhưng đây không phải là một ngôn ngữ thông thường. Vì vậy, bây giờ tôi đang tự hỏi nó là gì về ngôn ngữ thông thường mà làm cho họ thường xuyên, và ngôn ngữ này không?

Answer 1

Từ nguyên của tên xuất phát từ tác phẩm năm 1950 của Kleene mô tả bộ thông thường sử dụng ký pháp toán học của mình được tạo cho mục đích. Xem this.

Answer 2

Từ regular trong regular expression đề cập đến khái niệm Toán học thường xuyên, không phải khái niệm tiếng Anh. Cũng giống như cách từ prime trong toán học ít liên quan đến thủ công thịt bò.

Nó thừa hưởng bởi CS (mà là một chi nhánh của toán học) để chỉ một khái niệm cụ thể hơn: http://en.wikipedia.org/wiki/Regular_language

Answer 3

biểu thức chính quy là không thực sự bình thường, tên của nó là từ nguyên.

Answer 4

Có lẽ bài viết trên Wikipedia số regular languages có thể giải thích tốt hơn chúng ta có thể. Tuy nhiên, tôi sẽ cho nó một shot.

Từ quan điểm lý thuyết, ngôn ngữ thông thường (bộ chuỗi) là một ngôn ngữ có thể được tạo bằng cách sử dụng finite state automaton. Trong thuật ngữ lập trình, điều này tương đương với việc nói rằng nó có thể được tạo ra bằng cách sử dụng regular expressions. Do đó, tất cả các ngôn ngữ hữu hạn (bộ chuỗi) là thông thường, nhưng có một số ngôn ngữ vô hạn, chẳng hạn như ⁿ b ⁿ (ngôn ngữ của tất cả các chuỗi của na theo sau là n b) không thể nhận dạng được bằng cách sử dụng một FSA hoặc các biểu thức chính quy. Có nhiều thiết bị tính toán mạnh hơn (chẳng hạn như máy tính hiện đại, được mô hình hóa bằng cách sử dụng Turing Machines) mà có thể nhận ra những ngôn ngữ đó.

Lý do biểu thức chính quy được sử dụng rất nhiều trong lập trình để tìm chuỗi là chúng có thể nhận ra phần lớn các chuỗi quan trọng đối với chúng tôi lập trình và đồng thời có thể được thực hiện để tìm kiếm rất nhanh chóng sử dụng hữu hạn nhà nước automata.

Answer 5

Giải thích trực quan khoa học máy tính là ... phức tạp. Tôi sẽ cung cấp cho nó một shot, nhưng hãy nhớ rằng một số điều này sẽ là "đủ gần" nhưng không phải về mặt lý thuyết nghiêm ngặt.

Ngôn ngữ thông thường là ngôn ngữ có thể được quyết định bởi một máy tính tương đương tính toán với một automata hữu hạn (DFA/NDFA). Một automata hữu hạn có thể được coi là một máy hoạt động hoàn toàn ở các trạng thái, không có lưu trữ. Vì vậy, bạn có thể thấy rằng ⁿ b ⁿ không thể thường xuyên vì nó yêu cầu máy có thể đếm số lượng của a và b (và do đó phải có dung lượng lưu trữ vô hạn *) để so sánh chúng.

Để so sánh, (abc) ⁿlà thường xuyên, bởi vì số lần lặp lại là không thích hợp.

Để có chế độ xem nghiêm ngặt hơn (và tương đối dày hơn), hãy kiểm tra wikipedia article và các trang được liên kết.

_{* Vô hạn không quan trọng ở đây, nhưng tôi đề cập đến nó để hoàn thành. Nó có thể được dễ dàng hơn để nghĩ về nó như là "may mắn, luôn luôn chỉ đủ" lưu trữ.}