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.
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
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP