Gate1997_6.6

Which of the following language over {a,b,c} is accepted by a deterministic pushdown automata?

(A) \(\{ w \subset w^R |\ \ \in w\{a,b\}^* \} \)

(B) \(\{ w w^R |\ \ \in w\{a,b,c\}^* \} \) 

(C) \(\{ a^n b^nc^n | n\ge 0 \}\)

(D) \(\{w|w\ is \ a\ palindrom\ over \ \{a,b,c\} \}\)

Answer

Answer :-(A)
Exp:-

(A) {wwR|  ∈w{a,b}∗} - DPDA

(B) {wwR|  ∈w{a,b,c}∗} -NPDA

(C) {anbncnn≥ 0} -Context sensitive language (LBA)

(D) {w|w is a palindrom over {a,b,c}} - Not possible using DPDA because using PDA stack we cannot perform comparision for top of the stack element and the bottom one. so not possible using DPDA.

 

Option (A) is correct one.

1Comment
Amit Pal @amitpal101
29 Jul 2016 02:44 am

(A) {wwR|  ∈w{a,b}∗} - DPDA

 

(B) {wwR|  ∈w{a,b,c}∗} -NPDA

 

(C) {anbncn|n≥0} -Context sensitive language (LBA)

 

(D) {w|w is a palindrom over {a,b,c}} - Not possible using DPDA because using PDA stack we cannot perform comparision for top of the stack element and the bottom one. so not possible using DPDA.

 

Option (A) is correct one.

Pages