TransWikia.com

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!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP