1
$\begingroup$

I'm supposed to construct a pushdown automaton $A = \newcommand{\perm}[1]{\left\langle#1\right\rangle}\perm{ Q, \Sigma, \Gamma, \delta, q_0, F }$ that recognizes (via the accepting states $F$ and not necessarily via the emptying of the stack) the language $\newcommand{\lang}{\mathcal L} \lang = \newcommand{\set}[1]{\left\{#1\right\}}\set{ 0^m 1^n \mid m \leq n \leq 2m }$. In order to achieve this, I would somehow need to be able to keep track of two different counters using the single stack of the pushdown automaton: firstly, that there are at least as many ones as there are zeroes in a given word and secondly, that the number of ones does not exceed twice the number of zeroes.

To begin, the empty string is recognized, so we can set the initial state $q_0$ as an accepting state:

enter image description here

Next, should the input string not be empty, we initialize the stack with the base symbol $b$, by transitioning to the state $q_1$:

enter image description here

Now comes the tricky part, where I'm not sure how to proceed. I know how to calculate the minimum and maximum amount of $1$s to add at the end. In the first case, for every input $0$, PUSH a symbol such as an $m$ to the stack, and then if $1s$ are encountered, simply POP an $m$ from the stack:

enter image description here

In the second case, instead of PUSHing a single $m$ to the stack, PUSH $2$. If ones are read in, still POP only a single $m$ from the stack. In other words:

enter image description here

We are using the stack to limit the allowed transitions, so these two automata recognize words that contain exactly the same amount of $0$s and $1$s, or twice the amount of $1$s as there are $0$s, respectively. My issue is then finding out how to calculate whether there is an appropriate amount of $1$s between these two extremes.

An appropriate procedure has escaped me thus far, however. The problem is, conditionality can only be implemented using the symbol currently being read in, and the top of the stack. I would then somehow have to be able to insert maybe a different symbol $n$ somewhere in the middle of the stack, so that when $1$s are being read in and $m$s are POPped, if we encounter this symbol, a transition to the accepting state $q_4$ is allowed if $\epsilon$ (the end of the string) is encountered. Or maybe, instead of POPping $m$s, we should instead be POPing $n$s, but then we would somehow need to be able to decide when to start inserting $n$s when reading in $0$s.

Do any of you have ideas how this could be implemented? If you want to use images in your answer, the source for the last of my images is presented below.

\documentclass[tikz]{standalone}

\usetikzlibrary{arrows, calc, positioning, automata}

\begin{document}
  \begin{tikzpicture}[thick, ->, >=stealth, x=1cm, y=1cm, node distance = 1.5cm]
    \node (q0) [state, initial, accepting] { \(q_0\) };
    \node (q1) [state, right = of q0] { \(q_1\) };
    \node (q2) [state, right = of q1] { \(q_2\) };
    \node (q3) [state, right = of q2] { \(q_3\) };
    \node (q4) [state, accepting, right = of q3] { \(q_4\) };

    \draw (q0) edge node [above] { \(\epsilon, \epsilon / b\) } (q1);
    \draw (q1) edge node [above] { \(0, \epsilon / mm\) } (q2);
    \draw (q2) edge [loop above] node [above] { \(0, \epsilon / mm\) } (q2);
    \draw (q2) edge node [above] { \(1, m / \epsilon\) } (q3);
    \draw (q3) edge [loop above] node [above] { \(1, m / \epsilon\) } (q3);
    \draw (q3) edge node [above] { \(\epsilon, b / \epsilon\) } (q4);
  \end{tikzpicture}

\end{document}
$\endgroup$
10
  • $\begingroup$ Are you being asked for a deterministic PDA? $\endgroup$
    – rici
    Apr 8, 2020 at 14:24
  • $\begingroup$ @rici No, not necessarily. Are you by any chance suggesting I make this more modular? We did this with finite automata, where we would first construct an undeterministic one from deterministic components and then transform this modular automaton into a deterministic one via a certain algorithm. $\endgroup$
    – sesodesa
    Apr 8, 2020 at 14:31
  • 2
    $\begingroup$ if a non-deterministic PDA is acceptable, then you already have the solution. You don't have to choose between pushing one and pushing two. Do both. In some alternative reality, the parse will succeed. $\endgroup$
    – rici
    Apr 8, 2020 at 14:32
  • $\begingroup$ That's the coolest part of non-determinism. And the hardest part to wrap your head around if you're a programmer. :-) $\endgroup$
    – rici
    Apr 8, 2020 at 14:38
  • 1
    $\begingroup$ Sure. I can write a simple grammar, too. $S\to \epsilon\mid0S1\mid0S11$. Maybe that makes it easier to see. It's obvious why that grammar works, no? Of course, it's not that useful in the real world. Unless you have a quantum computer. The non-deterministic PDA implements that grammar. $\endgroup$
    – rici
    Apr 8, 2020 at 14:46

1 Answer 1

0
$\begingroup$

For the sake of completeness, I finished the picture above with the complete solution. I've replaced the base symbol $b$ with $\sqcup$, simply because I think it looks fancier.

enter image description here

To put it simply, I had mistakenly thought the operations on the stack could not be non-deterministic, but they can. This means we can add either one or two $m$s to the stack in the state $q_1$, as a result of reading in $0$s, and disassemble those in $q_2$ while reading in $1$s.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .