tự động đẩy xuống, có thể sử dụng hai ngôn ngữ (điều kiện HOẶC)

Question

Trong bài tập về nhà, chúng tôi phải xây dựng một ô tự động đẩy xuống cho 2 ngôn ngữ, nhưng theo tôi đây là hai bài tập mà ô tự động giống nhau cho cả hai ngôn ngữ.

Theo tôi hiểu, chúng tôi có thể xây dựng một ô tô tự động đẩy xuống không xác định và mỗi khi chúng tôi đọc ký tự a, chúng tôi có thể chèn một chữ A hoặc hai lần chữ A - tùy theo 'quyết định' của công cụ tự động.

Tiếp theo, một trạng thái được xây dựng cho nhân vật b, mỗi lần anh ta đọc A, anh ta sẽ kéo nó ra khỏi ngăn xếp. Bằng cách này, automaton biết cách xử lý cả hai ngôn ngữ trong đó số lượng a bằng số lượng b và các ngôn ngữ như a gấp đôi số lượng b.

Tôi nói đúng chứ? Hay tôi đang thiếu cái gì đó?

Nếu không, tôi rất muốn hiểu cách đối phó với điều kiện “hoặc” trong bài tập đầu tiên.

Cảm ơn bạn.

Answer 1

Từ $L_2\ne L_3$, chúng rõ ràng không thể được chấp nhận bởi cùng một tự động đẩy xuống. Có vẻ như bạn đã nghĩ đến một động cơ tự động nhận dạng$L_3$. Có lẽ là cách dễ nhất để thiết kế một để nhận ra$L_2$, là thiết kế hai ô tự động đẩy xuống xác định, một cho $\{a^nb^n:n\in\Bbb N\}$ và một cho $\{a^{2n}b^n:n\in\Bbb N\}$. Sau đó, kết hợp chúng thành một bộ tự động đẩy xuống duy nhất có chuyển tiếp$\langle q_0,\varepsilon,Z,q_1,Z\rangle$ và $\langle q_0,\varepsilon,Z,q_2,Z\rangle$, Ở đâu $q_0$ là trạng thái ban đầu của PDA kết hợp, $Z$ là ký hiệu ngăn xếp ban đầu và $q_1$ và $q_2$là trạng thái ban đầu của hai ô tự động đẩy xuống công ty con. Nói cách khác, điều đầu tiên mà PDA kết hợp làm là 'chọn' xem có tìm kiếm một từ thuộc loại$a^nb^n$ hoặc một từ thuộc loại $a^{2n}b^n$, và sau đó nó theo đuổi lựa chọn đó một cách xác định.