1.4k views

Which of the following languages over $\left\{a,b,c\right\}$ is accepted by a deterministic pushdown automata?

1. $\left\{ wcw^R \mid w \in \left\{a,b\right\}^*\right\}$
2. $\left\{ ww^R \mid w \in \{a,b,c\}^*\right\}$
3. $\left\{ a^nb^nc^n \mid n \geq 0 \right\}$
4. $\left\{w \mid w \text{ is a palindrome over } \left\{a,b,c\right\} \right\}$

Note: $w^R$ is the string obtained by reversing $'w'$.

edited | 1.4k views

1. $\left\{ wcw^R \mid w \in \left\{a,b\right\}^*\right\}$ // Can be realized using DPDA cz we know the center of the string that is c here //Hence Option A is ANS

2. $\left\{ ww^R \mid w \in \{a,b,c\}^*\right\}$   // (set of even palindrom)NPDA bcz we can't find deterministically the center of palindrom string
cfg will $\rightarrow S \rightarrow aSa \mid bSb \mid cSc \mid \epsilon$

3. $\left\{ a^nb^nc^n \mid n \geq 0 \right\}$ // CSL

4. $\left\{w \mid w \text{ is a palindrome over } \left\{a,b,c\right\} \right\}$ // it is a cfl similar as option B
cfg will $\rightarrow S\rightarrow aSa \mid bSb \mid cSc \mid a \mid b \mid c \mid \epsilon$
edited by
+1
For option C, it would be more appropriate to say that it is not a CFL because a CSL can be CFL as well.
+1
@vishal goel it is well known CSL because it require two comparision at a time LBA is require for this
A. rest cannot be accepted by a DPDA.
–1 vote

A

Here centre is known which is c so there is no chance of CFL but 100% chance of DCFL

B

Centre is not known therefore there is no chance of DCFL.

C

It is CSL therefore not a being chance of CFL so no way of being DCFL.

D.

It can be accepted by LBA not even CFL or DCFL.

+1
For D) we can have NPDA,see the CFG given in selected answer.

1
2