The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+14 votes
1.1k 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'$.

asked in Theory of Computation by Veteran (59.6k points)
edited by | 1.1k 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 (23k points)
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.
0
@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.7k points)
–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.

answered by Loyal (9.1k points)
+1
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

42,685 questions
48,649 answers
156,437 comments
63,960 users