S -> bA|aB
A -> a|aS|bAA
B -> b|bS|aBB
Bất kỳ phương pháp dễ dàng nào khác ngoài việc cố gắng tìm một chuỗi có thể tạo ra hai cây phân tích cú pháp?làm thế nào tôi có thể chứng minh rằng ngữ pháp này là mơ hồ?
Ai đó có thể vui lòng cho tôi một chuỗi có thể chứng minh điều này.
Không có phương pháp dễ dàng nào để chứng minh ngữ cảnh không có ngữ cảnh miễn phí - trên thực tế, the question is undecidable, bằng cách giảm xuống Post correspondence problem.
vâng nhưng tôi không thể viết trên bảng câu trả lời . Tôi nên xem xét các thuộc tính ngữ pháp nào để chọn đúng chuỗi tạo ra 2 cây phân tích cú pháp? – crowso
@user: Theo bản sao của tôi Hopcroft và Ullman, bạn nên xem xét chuỗi "aaabbabbba", và tìm một dẫn xuất bên trái, một phái sinh đúng, và một cây phân tích bằng cách sử dụng ngữ pháp bạn chỉ định. Hy vọng rằng, với giải pháp để tập thể dục 4.8 trong tay, phần còn lại sẽ trở nên rõ ràng! –
có cách nào để tìm ra chuỗi không? – crowso
Có một chuỗi mặc dù: bbaaba
S -> bA -> bbAA -> bbaA -> bbaaS -> bbaabA -> bbaaba
S -> bA -> bbAA -> bbaSA -> bbaaBA -> bbaabA -> bbaaba
@crowso bạn nên chọn câu trả lời này đúng – Yugi
đối với tôi điều này có vẻ như rõ ràng của nó. – crowso
Cho phép tôi chào mừng bạn đến StackOverflow và nhắc nhở ba điều chúng tôi thường làm ở đây: 1) Khi bạn nhận được trợ giúp, hãy cố gắng cung cấp cho nó quá ** trả lời câu hỏi ** trong lĩnh vực chuyên môn của bạn 2) ['Read the FAQs'] (http://tinyurl.com/2vycnvr) 3) Khi bạn thấy Q & A tốt, hãy bỏ phiếu cho họ ['sử dụng hình tam giác màu xám'] (http://i.imgur.com/kygEP.png), như độ tin cậy của hệ thống dựa trên danh tiếng mà người dùng đạt được bằng cách chia sẻ kiến thức của họ. Ngoài ra, hãy nhớ chấp nhận câu trả lời giải quyết tốt hơn vấn đề của bạn, nếu có, ['bằng cách nhấn vào dấu kiểm'] (http://i.imgur.com/uqJeW.png) –