Nhập 3 ngữ pháp tạo ngôn ngữ thông thường. Đây là những ngôn ngữ có các tính năng như bắt đầu bằng "xxx", chứa "xxx", kết thúc bằng "xxx", chứa số lẻ của y, v.v. Tự động hữu hạn (xác định hoặc không) nhận ra các ngôn ngữ này.
Nhập 2 ngữ pháp tạo ngôn ngữ không có ngữ cảnh. Đây là những ngôn ngữ có các tính năng như một số x được theo sau bởi ít hơn, hoặc nhiều hơn, hoặc bằng số của y, hoặc một từ được theo sau bởi cùng một từ, nhưng bị đảo ngược. Pushdown automata nhận ra những ngôn ngữ này ... nghĩ automaton hữu hạn với một ngăn xếp.
Nhập 1 ngữ pháp tạo ngôn ngữ nhạy cảm với ngữ cảnh. Đây là rất gần với loại 0 ngữ pháp mà nó thường là khó để tìm thấy một sự khác biệt giữa chúng. LBA (tự động hóa tuyến tính) nhận ra những ngôn ngữ này, cho rằng máy Turing có nguồn lực hạn chế ... hãy nghĩ đến một máy tính hiện đại.
Nhập 0 ngữ pháp tạo ngôn ngữ Turing, đôi khi được gọi là ngôn ngữ đếm ngược đệ quy. Đây là cơ bản bất kỳ ngôn ngữ mà bạn có thể viết một chương trình máy tính để nhận ra, nhưng họ thực sự pha trộn với Type 1, kể từ khi máy tính thực thường có một số loại giới hạn bộ nhớ.
Tự động hữu hạn và tự động đẩy xuống là rất quan trọng trong việc giải quyết các vấn đề nảy sinh khi viết trình biên dịch. Tuy nhiên, đó không phải là lý do tại sao bạn nghiên cứu chúng, bạn nghiên cứu chúng để tìm hiểu các giới hạn của những gì có thể/không thể được tính toán. Nhiều lập trình viên nghĩ rằng bạn có thể giải quyết mọi vấn đề với máy tính. Lý thuyết tính toán dạy bạn cách khác.
Sửa bởi "Dude" - OK, đây là một cách dễ hiểu (và nổi tiếng) vấn đề mà không thể được giải quyết bằng bất kỳ máy Turing hoặc máy tính hoặc lập trình viên hoặc thiên tài người ngoài hành tinh ...
Hãy tưởng tượng bạn có một số domino ... nhưng thay vì các mẫu chấm, bạn có một số từ ngắn ở trên và dưới, nói những từ như "aba" và "cab". Nếu tôi cung cấp cho bạn 5 hoặc 10 hoặc 50 trong số các domino này, bạn có thể sắp xếp chúng để các từ trên cùng, tất cả được nối với nhau hay không, khớp chính xác với các từ được ghép nối ở phía dưới. Bạn có thể tạo bao nhiêu bản sao tùy thích và mỗi bản sao.
Ví dụ domino (contrived :) (a/aab), (aba/ac), (cab/ab) là tập hợp 3 domino nơi đỉnh (a + aba + cab) chính xác bằng đáy (aab + ac + ab).
Dễ như điều này nghe có vẻ không thể giải quyết được.
BTW, khi lần đầu tiên tôi đọc/hiểu vấn đề này ... Tôi đã suy nghĩ .... ooooh, n! đang bắt đầu nhìn tốt!
a) Tôi biết cấu trúc phân cấp được tạo thành từ các bộ với 0 là bộ chứa tất cả. Những gì tôi yêu cầu là các tính năng tạo ra một ngôn ngữ thuộc về mức 1 và không phải là cấp 2. Xin lỗi nếu ngữ pháp của câu hỏi là mơ hồ. +1 – andandandand
Tôi trộn các số. Chúng tôi không sử dụng chúng tại trường đại học của tôi. – ebo
Tôi không biết về vấn đề Word. Cảm ơn, tôi thấy nó thú vị. – andandandand