PDA for $L= {w : n_a(w)+n_b(w) = 2n_c(w)}$

Computer Science Asked by MrOO7 on December 9, 2020

I’m pretty new to the PDA topic.

How do I construct an NPDA for the language $$L= {w : n_a(w)+n_b(w) = 2n_c(w)}.$$

I’ve tried all the possibilities, but I still somehow end up accepting all words.

One Answer

The idea is to store a counter $n_a(w) + n_b(w) - 2n_c(w)$ in the stack. If this number is positive, say $x$, we want to have $x$ many P's on the stack (and nothing else). If this number is negative, say $-y$, we want to have $y$ many N's on the stack (and nothing else). Otherwise we want to have a special indicator $O$ on the stack. At the end, we check that the stack consists of $O$.

I'll let you work out the details.

Answered by Yuval Filmus on December 9, 2020

Add your own answers!

Related Questions

Is $EVEN-SAT$ $NP$-hard?

2  Asked on November 23, 2021 by zur-luria


Proof of the undecidability of compiler code optimization

5  Asked on November 23, 2021 by stephen-mwangi


What is the reason for writing parallel programs?

1  Asked on November 17, 2021 by user123521


Convert the given NFA to DFA

2  Asked on November 5, 2021 by vinay-varahabhotla


Ask a Question

Get help from others!

© 2022 All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP