aşağı açılır otomat, iki dil mümkündür (OR koşulu)

Aug 16 2020

Ev ödevinde 2 dil için bir pushdown otomat inşa etmeliyiz, ancak bence bunlar otomatın her ikisi için de aynı olduğu iki alıştırma.

Anladığım kadarıyla, deterministik olmayan bir aşağı itme otomatı oluşturabiliriz ve a karakterini her okuduğumuzda, otomatın 'takdirine' tek bir A veya iki A ekleyebiliriz.

Daha sonra, karakter b için bir durum oluşturulur ve bu, her A'yı okuduğunda onu yığından çıkarır. Böylelikle otomat, a'nın miktarının b miktarına eşit olduğu her iki dili ve ayrıca a'nın b'nin iki katı olduğu dilleri nasıl kullanacağını bilir.

Haklı mıyım Yoksa bir şey mi kaçırıyorum?

Değilse, ilk alıştırmada “veya” durumuyla nasıl başa çıkılacağını anlamayı çok isterim.

Teşekkür ederim.

Yanıtlar

2 BrianM.Scott Aug 16 2020 at 09:32

Dan beri $L_2\ne L_3$, açıkça aynı aşağı açılan otomat tarafından kabul edilemezler. Aklınızda bir otomat varmış gibi geliyor$L_3$. Muhtemelen birini tanımanın en kolay yolu$L_2$, iki deterministik aşağı itme otomatı tasarlamaktır. $\{a^nb^n:n\in\Bbb N\}$ ve biri için $\{a^{2n}b^n:n\in\Bbb N\}$. Ardından bunları geçişleri olan tek bir aşağı açılan otomatta birleştirin$\langle q_0,\varepsilon,Z,q_1,Z\rangle$ ve $\langle q_0,\varepsilon,Z,q_2,Z\rangle$, nerede $q_0$ kombine PDA'nın başlangıç ​​durumudur, $Z$ ilk yığın sembolüdür ve $q_1$ ve $q_2$iki bağlı aşağı itme otomatının başlangıç ​​durumlarıdır. Başka bir deyişle, birleşik PDA'nın yaptığı ilk şey, bu türden bir kelimeyi arayıp aramayacağınızı 'seçmektir'.$a^nb^n$ veya türünde bir kelime $a^{2n}b^n$ve sonra bu seçimi deterministik olarak sürdürür.