Question

PDA:

(b) {Oʻ11 2k | i, j, k > 0 and i = j or i = k}

please give me a PDA for the language.

You don't have to draw a diagram, but please illustrate the PDA something like this:

1.δ(q0,0, Z0)={(q0,0Z0)}

2.δ(q0,1, Z0)={(q0,1Z0)}

......

12.δ(q1, e, Z0)={(q2, Z0)}

Thank you!

Answer 1

The PDA for this will be non-deterministic. It will start with pushing a stack for every 0 that is sees. Then on seeing a 1, it will make a non-deterministic choice between matching 0s with 1s or with 2s. If it chooses to match 1s, it will start popping stack symbols, and accept if their numbers match. If it decides to match 2s, then it will wait till it sees 2s to match symbols, and accept if they match.

The machine is as follows: where $q_0$ is the start state. $\Sigma = \{0,1,2\}$ and $\Gamma = \{0,1,2,\bot\}$ where $\bot$ is the bottom of the stack. . The transitions are:
$\delta(q_0, 0, \bot) = (q_0, 0\bot)$ (push 0s)
$\delta(q_0, 0, 0) = (q_0, 00)$
$\delta(q_0, 1, 0) = \{(q_1, \epsilon), (q_2, 0)\}$ (this is the non-deterministic choice)
$\delta(q_0, 1, \bot) = (q_{2}, \bot)$ (this handles when there are no 0s)
$\delta(q_0, \epsilon, \bot) = (q_{acc2}, \epsilon)$   (this is to accept empty word, which belongs to the language)
$\delta(q_1, 1, 0) = (q_1, \epsilon)$
$\delta(q_1, \epsilon, \bot) = (q_{acc1}, \bot)$ (1s are matched)
$\delta(q_{acc1}, 2, \bot) = (q_{acc1}, \bot)$ (now 2s don't matter)
$\delta(q_{2}, 1, 0) = (q_2, 0)$ (ignore 1s)
$\delta(q_{2}, 1, \bot) = (q_2, \bot)$
$\delta(q_{2}, 2, 0) = (q_3, \epsilon)$ (start matching 2s)
$\delta(q_{2}, \epsilon, \bot) = (q_3, \bot)$
$\delta(q_{3}, 2, 0) = (q_3, \epsilon)$
$\delta(q_{3}, \epsilon, \bot) = (q_{acc2}, \epsilon)$ (2s are matched)

Comment in case of any doubts.