0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – quicksort Nov 5 '17 at 2:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.