# Push-down automaton for a language with number of 1s double than 0s [duplicate]

This questions is taken from a complexity theory course.

Design a push-down automaton that recognize $L = x \in \{0,1\}^*$ such that $x$ contains a number of ones double than a number of zeros.

Example: x = 011011, 100011111, 011011110.

My approach

I tried to push on the stack a symbol "A" every time I read "0", than pop "A" from the stack when I read two consecutive "1" but this approach works not for every string $x$ in the language. Maybe the final PDA is non-deterministic. Any hints?

## 3 Answers

Consider this algorithm:

• Initialize a variable $x := 0$.

• Scan the string, left to right. If you see $1$, set $x := x + 1$, if you see $0$, set $x := x - 2$.

• When you are done, accept iff $x = 0$.

It should be obvious that it recognizes your language. Can you figure out a way to implement it replacing the counter with the stack?

Here's an algorithm for what I think could be a solution:

program_recL(entry) is
stack: type_stack
while read(entry) != $do if read(entry) == 0 then if empty(stack) then push(stack, 0) push(stack, 0) else if top(stack) == 0 then push(stack, 0) push(stack, 0) else pop(stack) push(stack, 0) endif endif else if empty(stack) then push(stack, 1) else if top(stack) == 1 then push(stack, 1) else pop(stack) endif endif endif next(entry) endwhile if is_empty(stack) then accept() endif end  The basic idea here is that every 0 has x2 value for each 1, meaning we need to push two 0s every time we read a 0 on our entry. This will translate into needing two 1s to get a 0 popped from the stack, in other words, a number of 1s double than a number of 0s. You need a 2-stack PDA to solve this problem. Since the language you've given is non-context free, it's more powerful than a single stack PDA. More specifically, your language the union of many CFLs and non-CFLs. The inputs that seem to be working with your way can be recognized by a single stack PDA. e.g.: S -> 0A11 A -> S which is the language {0^n1^2n, n>=0} S -> 11A0 A -> S which is the language {1^2n1^n, n>=0} . . . However, there is no way to describe others with a context-free grammar. • No, you don't need a "2-stack PDA" (friends call him a Turing Machine, by the way). Consider this grammar:$S \rightarrow \varepsilon$,$S \rightarrow S0S1S1S\$ and cyclic variants. One arrow is obvious, the other is structural induction. – quicksort Nov 5 '17 at 2:17