Bài tập ngôn ngữ hình thức và otomat
LÝ THUYẾT AUTOMAT VÀ NGÔN NGỮ HÌNH THỨC được thiết kế với mục đích giới thiệu cho sinh viên trong chương trình đào tạo khoa học máy tính ở bậc đại học, đặc biệt là các sinh viên năm thứ hai, thứ ba. Chương 1 Giới thiệu Chương 2 Automat hữu hạn Chương 3 Ngôn ngữ chính qui và văn phạm chính qui Chương 4 Các tính chất của ngôn ngữ chính qui Chương 5 Ngôn ngữ phi ngữ cảnh Chương 6 Đơn giản hóa văn phạm phi ngữ cảnh và các dạng chuẩn Chương 7 Automat đẩy xuống Chương 8 Các tính chất của ngôn ngữ phi ngữ cảnh Chương 9 Máy turing 5 , 1 Đánh giá54000 -54000 5 , 1 Đánh giá44000 -44000 5 , 1 Đánh giá53000 -53000 5 , 1 Đánh giá32000 -32000 5 , 1 Đánh giá29000 -29000 5 , 1 Đánh giá155000 -155000 5 , 1 Đánh giá35000 -35000 5 , 1 Đánh giá22000 -22000 5 , 1 Đánh giá69000 -69000 5 , 1 Đánh giá18000 -18000
.png) Địa chỉ: 268 Lý Thường Kiệt, P.14, Q.10, TP.HCM Tel: 38647256 ext. 5419, 5420 Email: [email protected] Dưới đây là bài tập + lời giải môn Ngôn ngữ hình thức gồm 7 chương: Chương 1: Văn phạm Chương 2: DFA và NFA Chương 3: Biểu thức chính quy Chương 4: Cực tiểu hoá Otomat Chương 5: Khử sự nhập nhằng của văn phạm Chương 6: Otomat đẩy xuống PDA Chương 7: Máy Turing Link Post navigationGiả sử L là ngôn ngữ chính quy. Khi đó sẽ tồn tại một DFA M chấp nhận cho ngôn ngữ L. Gọi n là số trạng thái của DFA M đó. Xét chuỗi z = anb1c1dn . Ta có độ dài của chuỗi z là: |z| = 2n + 2 n . Theo bổ đề bơm, ta có thể đặt z = uvw , trong đó u, v, w là các chuỗi con của z với điều kiện như sau: |uv| ≤ n, |v| ≥ 1 và với mọi i ≥ 0 ta có uviw ϵ L |