# 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.

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

## Related Questions

### Solving the Knapsack problem in $O(n^2P)$, where P is the maximum weight of all items

1  Asked on November 28, 2021 by user2207686

### Number of words of length n for special language

0  Asked on November 28, 2021

### Intuition for Church-Turing thesis for Turing machines

2  Asked on November 28, 2021

### Global-input-local-output p-time algorithms

0  Asked on November 25, 2021

### Does a regular expression exist for any number that contains no more than two 5s and no 6 twice in a row?

2  Asked on November 25, 2021 by hish

### 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

### Counting circuits with constraints

1  Asked on November 23, 2021 by judy-l

### Uncurrying and Polymorphism

3  Asked on November 21, 2021

### Algorithm suggestion to order data with specific condition

0  Asked on November 21, 2021 by user3862410

### If $A$ is context-free then $A^*$ is regular

1  Asked on November 21, 2021

### Which is the best approach to solve Turing machines exercises?

2  Asked on November 17, 2021 by ocram

### What is the reason for writing parallel programs?

1  Asked on November 17, 2021 by user123521

### Are all Recursively Enumerable languages which are not Recursive also Undecidable?

1  Asked on November 17, 2021 by dshri

### Is English Turing-complete?

3  Asked on November 15, 2021

### If factor isn’t found in P-1 algorithm, should upper bound be increased linearly (i.e. +1)

0  Asked on November 13, 2021 by northerner

### Can map-reduce speed up the count-min-sketch algorithm?

1  Asked on November 11, 2021 by pragya

### Maximization problem on finite collection of finite sets

1  Asked on November 11, 2021 by yuezato

### Do there exist fast multiplication algorithms for two integers with one of them being static?

1  Asked on November 8, 2021 by john-flemin

### Convert the given NFA to DFA

2  Asked on November 5, 2021 by vinay-varahabhotla