tailieunhanh - Ngôn ngữ nhóm cô lập

Ngôn ngữ nhóm cô lập Điều khiển học chính thức trở thành một khoa học sau một cuộc gặp gỡ của các trí thức sau thế chiến 2, gồm có Norbert Wiener, John von Neumann, Warren McCulloch, Claude Shannon, Heinz von Forster, Gregory Bateson, . Northrop, Conrad Lorenz, W. Grey Walter và Mead Margaret từ năm 1946 đến 1953. | Tạp chí Tin học và Điều khiền học T. 19 s. 2 2003 101--109 NGÔN NGỮ NHÓM cô LẬP LÊ QUỐC HÁN NGUYỄN THỊ BÍCH Khoa Toán - Tin Trường Đại học Vinh Abstract. On isolate languages having a group as syntactic monoid. Languages mentioned in the title are considered. We describe syntactic monoids of such languages and when they are regular we provide different characterizations in terms of automata grammars and so on. Tóm tắt. Trong bài báo này chúng tôi khảo sát các ngôn ngữ cô lập có vị nhóm cú pháp là một nhóm và mô tả ôtômát của lớp ngôn ngữ này. Trong trường hợp chúng là ngôn ngữ chính qui chúng tôi đã mô tả được ôtômát văn phạm sinh ra ngôn ngữ đó. 1. MỞ ĐẦU Khái niệm ngôn ngữ nhóm được đưa ra bởi . Aniximov 1 vào năm 1971. Đó là những ngôn ngữ nghịch ảnh của đơn vị qua đồng cấu của vị nhóm các từ hữu hạn vào một nhóm. Trong bài báo này chúng tôi sẽ thay đơn vị nhóm bởi nhóm con rời rạc của nhóm . Lớp ngôn ngữ này thực sự chứa lớp ngôn ngữ trong 1 . Giả sử s là một nửa nhóm. Quan hệ p trên s được gọi là ổn định phải trái nếu Va b c s từ apb suy ra acpbc hoặc capcbỴ Một quan hệ tương đương phản xạ đối xứng và bắc cầu Ổn định phải trái trên s được gọi là một tương đẳng phải trái . Quan hệ p trên s được gọi là một tương đẳng nếu p vừa tương đẳng phải vừa tương đẳng trái. Giả sử s là một nửa nhóm và H là tập con của s. Ta xét quan hệ pH T s X s như sau íc y s X s uxv H uyv H Vu V s . Khi đó pH được gọi là tương đẳng chính hay tương đẳng cú pháp của H và vị nhóm thương S pH được gọi là vị nhóm cú pháp của H trong s. Tập con H được gọi là rời rạc trong s nếu tương đẳng pH là tương đẳng đồng nhất nghĩa là x ỳ pH X y. Ta còn xét tương đẳng một phía trên s như sau íc y s X s xu H yu H Vu s . Khi đó là tương đẳng phải trên s và được gọi là tương đẳng chính phải -Đuybrây sinh bởi H trong s. Giả sử X là một tập hợp tùy ý và X là vị nhóm tự do sinh bởi X với đơn vị là từ A khi đó mỗi phần tử khác đơn vị của X biểu diln được một cách duy nhất dưới dạng tích của hữu hạn các phần