Designing PDAs to Accept Languages

Question

I want to design PDAs to accept the following two languages:

1. $L_1 = \{a^ib^jc^k \mid i=j \text{ or } j=k\}$
2. $L_2 = $ The set of all strings with twice as many $0$s as $1$s.

I am especially clueless on the second one. I don't even know how to begin to approach it. Can anyone help me out?

Answer 1

Hint:

• $L_1 = \{a^kb^k\}\{c^*\} \cup \{a^*\}\{b^kc^k\}$, i.e. try nondeterministically guess wheter you are in the left or right part of the sum.
• In a language of properly-parenthesized expressions you keep on stack the surplus of opened parentheses.
• In a language $L_3=\{w \mid \#_aw = \#_bw\}$ you would need to do the same, but the surplus could be negative, i.e. you need one symbol to represent $+1$ and the other to represent $-1$. Then, you try to cancel the expressions first, so that the stack keeps only $+1$'s or only $-1$'s (that is, their respective symbols $a$'s and $b$'s).
• Try to modify the language above into language that was obtained by substituting $cc$ for all the $a$, i.e. $L_4 = \{ w[a \mapsto cc] \mid w \in L_3\}$, and then try to keep the stack counter with respect to $c$'s, not $b$'s.
• Now, with $L_2$ you do a similar thing, only now the letters of the double symbols (there $cc$, now $aa$) does not need to be together.

I hope this helps $\ddot\smile$