# Pushdown automaton for language with “or” [duplicate]

Find a pushdown automaton accepting the language $$L=\{A^i B^j C^k \mid 2k \le i \le 3k \text{ or } j \neq i+k \}.$$

I can't construct the automaton because I can only imagine it with multiple stacks or with set-theoretic intersections.

## 1 Answer

Presumably you are able to construct PDAs for the following languages: $$\{ A^i B^j C^k : 2k \leq i \leq 3k \}, \\ \{ A^i B^j C^k : j < i+k \}, \\ \{ A^i B^j C^k : j > i+k \}. \\$$ Now you can use non-determinism to construct a PDA which non-deterministically chooses which of the three PDAs to apply.