Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Các khía cạnh phân loại và hình thái học của ngôn ngữ hình thức
Tóm tắt
Bài báo này đặt công trình của H. Walter về phân loại ngữ pháp và ngôn ngữ thông qua hình thái học vào một khung tổng quát hơn và cung cấp các chứng minh ngắn gọn cho các kết quả chính của ông. Ngoài ra, bài báo cũng chứng minh rằng mọi ngữ pháp đều tương đương về mặt hình thái học với một ngữ pháp ở dạng chuẩn, rằng hình thái rời rạc có thể được hiện thực hóa trên mọi ngôn ngữ không ngữ cảnh, và rằng một ngôn ngữ là hữu hạn nếu và chỉ nếu mọi hình thái học trên nó đều có thể được hiện thực hóa như một trong các hình thái mà Walter đã đề xuất. Thêm vào đó, một phương pháp mới và rõ ràng được cung cấp để đem lại các kết quả cơ bản cần thiết, về sự chia hết và hủy bỏ trong các loại hình của các phép biến đổi, như đã được D. Benson và G. Hotz nghiên cứu.
Từ khóa
#ngữ pháp #ngôn ngữ không ngữ cảnh #hình thái học #phân loại ngôn ngữ #thuật toán #tính hữu hạnTài liệu tham khảo
D. B. Benson, The basic algebraic structure in categories of derivations.Inf. and Control 28, 1–29 (1975).
G. Birkhoff,Lattice Theory. AMS, Providence R.I. 1968.
T. V. Griffiths, Some remarks on derivations in general rewriting systems.Inf. and Control 12, 27–54 (1968).
G. Hotz, Eindeutigkeit und Mehrdeutigkeit formaler Sprachen.E.I.K. 2, 235–246 (1966).
S. MacLane,Categories for the Working Mathematician. Springer, 1971.
H. Walter, Topologies on Formal Languages.Math. Systems Theory 9, 142–158 (1975).