edited by
10,564 views
25 votes
25 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'$.

edited by

4 Answers

Best answer
34 votes
34 votes
  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 ANSWER
     
  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
0 votes
0 votes
(A) w⊂wR, can be realized using DPDA because we know the centre of the string that is c here.
(B) wwR, is realized by NPDA because we can't find deterministically the center of palindrome string.
(C) {anbncn | n ≥ 0} is CSL.
(D) {w | w is palindrome over {a,b,c}},
is realized by NPDA because we can't find deterministically the center of palindrome string.
–1 votes
–1 votes

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.

Answer:

Related questions

34 votes
34 votes
4 answers
1
34 votes
34 votes
3 answers
4
Kathleen asked Sep 29, 2014
10,944 views
Dirty bit for a page in a page tablehelps avoid unnecessary writes on a paging devicehelps maintain LRU informationallows only read on a pageNone of the above