For option C, it would be more appropriate to say that it is not a CFL because a CSL can be CFL as well.

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+14 votes

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

- $\left\{ wcw^R \mid w \in \left\{a,b\right\}^*\right\}$
- $\left\{ ww^R \mid w \in \{a,b,c\}^*\right\}$
- $\left\{ a^nb^nc^n \mid n \geq 0 \right\}$
- $\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'$.

+18 votes

Best answer

- $\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

- $\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$

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

- $\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$

- All categories
- General Aptitude 1.5k
- Engineering Mathematics 7.1k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.3k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4k
- Non GATE 1.4k
- Others 1.5k
- Admissions 556
- Exam Queries 551
- Tier 1 Placement Questions 23
- Job Queries 69
- Projects 18

47,894 questions

52,260 answers

182,164 comments

67,677 users