Register

GO Classes DPP | GATE CS | Theory of Computation | DFA as DPDA

65 views
1 1 vote

Let $L$ be a regular language accepted by a DFA $D=(Q,\Sigma,\delta,q_0,F)$. Which construction correctly proves that $L$ is a deterministic context-free language?

  1. Make a DPDA that simulates the DFA states and keeps the stack unchanged on every input symbol.
     
  2. Make an NPDA that guesses the middle of the string and accepts by empty stack.
     
  3. Make a DPDA that pushes every input symbol and accepts only when the stack becomes empty.
     
  4. Make a PDA that uses two stacks to simulate the DFA.

1 Answer

1 1 vote

Since $L$ is regular, some DFA accepts it. 

A DFA can be viewed as a DPDA that does not really use the stack. 

The DPDA keeps the same finite-state transitions as the DFA and leaves the stack unchanged. 

Since the computation has no nondeterministic choice, this is a valid DPDA. 

Therefore every regular language is a DCFL.
 

Answer : A

Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | GAT...Next → · GO Classes DPP | GAT...
← Previous in category · GO Classes DPP | GAT...Next in category → · GO Classes DPP | GAT...
Position:
Show:

Related questions

1 1 vote
1 1 answer
58
58 views
GO Classes asked Sep 15
58 views
GO Classes DPP | GATE CS | Theory of Computation | Empty-stack DPDA
A language accepted by a DPDA using empty-stack acceptance must have the prefix property, meaning no accepted string can be a proper prefix of another accepted string. Wh...
0 0 votes
1 answers 1 answer
756
756 views
Bikram asked Nov 26, 2016
756 views
Test by Bikram | Theory of Computation | Test 1 | Question: 12
Let $N(f) =$ the class of languages accepted by Non- deterministic Finite Automata,$N(p) =$ the class of languages accepted by Non- deterministic Push down Automata,$D(f...
1 1 vote
1 1 answer
92
92 views
GO Classes asked Sep 14
92 views
GO Classes DPP | GATE CS | Theory of Computation | DPDA Limitation
Consider $L=\{ww^R\mid w\in\{a,b\}^*\}$. Which statement is correct?It can be accepted by a DPDA because the stack automatically tells where the middle is. It needs nonde...
1 1 vote
1 1 answer
70
70 views
GO Classes asked Sep 14
70 views
GO Classes DPP | GATE CS | Theory of Computation | DPDA Design
A DPDA is constructed for $L=\{wcw^R \mid w\in\{a,b\}^*\}$. Which strings are accepted?$abcba$ $abbcbba$ $abccba$ $c$ $abca$