The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+14 votes

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'$.

asked in Theory of Computation by Veteran (52.1k points)
edited by | 1.4k views

3 Answers

+18 votes
Best answer
  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$
answered by Boss (23.4k points)
edited by
For option C, it would be more appropriate to say that it is not a CFL because a CSL can be CFL as well.
@vishal goel it is well known CSL because it require two comparision at a time LBA is require for this
+9 votes
A. rest cannot be accepted by a DPDA.
answered by Boss (19.9k points)
–1 vote


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


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


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


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

answered by Loyal (9.7k points)
For D) we can have NPDA,see the CFG given in selected answer.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,808 questions
54,489 answers
74,658 users