tailieunhanh - Một số tính chất của lớp siêu ngôn ngữ phi ngữ cảnh.

Một số tính chất của lớp siêu ngôn ngữ phi ngữ xây dựng được quy trình công nghệ phun phủ hồ quang điện chế tạo lớp phủ hợp kim NiCr20 trên nền gang xám, ứng dụng làm lớp phủ bảo vệ chống ăn mòn. | Tạp chí Tin học và Điều khiển học T. 16 s. 2 2000 5-8 MỘT SỐ TÍNH CHẤT CỦA LỚP SIÊU NGÔN NGỮ PHI NGỮ CANH ĐẶNG HUY RUẬN PHÙNG VĂN Ổn Abstract. In this paper we show some properties of context free languages words we call context free hyper language and its relation with pushdown automata. 1. MỞ DAU Có nhiều công trình của nhiều tác giả nghiên cứu về lớp ngôn ngữ chính quy với từ vô hạn siêu ngôn ngữ chính quy đã được công bố Ịl-3 . Một cách tự nhiên nảy sinh vấn đề nghiên cứu các tính chất lớp ngôn ngữ phi ngữ cảnh với tù vô hạn được gọi là siêu ngôn ngữ phi ngữ cảnh . Cũng đã có một số kết quả nghiên cứu về lớp ngôn ngữ này 4 5 . Bài báo này trình bày một số kết quả về vấn đề nêu trên. 2. MỘT SỐ KIẾN THỨC CHU Ẩn bị . Siêu ngôn ngữ Cho s là tập hữu hạn không rỗng các chữ cái. Ký hiệu s s là tập hợp tất cả các dãy vô hàn hữu hạn các chữ cái trong E. Các phần tủ của s E được gọi là siêu từ từ hay từ hữu hạn . Với tù p 6 s ký hiệu IJF là độ dài của p tức là số chữ cái xuất hiện trong p. Cho L C s ta định nghĩa hai siêu ngôn ngữ sau L p ẹ s I p PỵP . mà Pi L và Pj 1 vói mọi i 1 limL P G E I p . mà P1 p2 . Pi G L với mọi i 1 . Siêu từ Ps s được gọi là tận cùng tuần hoàn nếu p P1P20 với Pl P2 G s . . Siêu ngôn ngữ phi ngữ cảnh Cho văn phạm phi ngữ cảnh G s V X P trong đó E a ỏ V X y p X YX Y ayí aò . Xét dẫn xuất trái nhất vô hạn X yx abX abYX ababX - . 1 ta nhận được siêu từ ab . Nếu dùng dẫn xuất trái nhất vô hạn mà sứ dụng vô hạn lần biến y với quy tấc y aYb trong mỗi lần thay thế X YX abX - abYX - abaYbX abaaYbbX - . 2 ta nhận được siêu từ ab a . Trong trường hợp này phần vô hạn ờ bên phải được bổ qua. Như vậy có hai cách sinh ra siêu ngôn ngữ phi ngữ cảnh tùy thuộc vào việc sử dụng dẫn xuất trái nhất 1 hoặc các biến được dùng vô hạn lần được xác định 2 . Định nghĩa 1. Cho văn phạm phi ngữ cảnh G S V X P . a Siêu ngôn ngữ L C E được gọi là đại số nếu có một văn phạm phi ngữ cảnh G thỏa mân L bao gồm tất cả các siêu từ của E mà chúng