-2
$\begingroup$

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.

$\endgroup$
2
3
$\begingroup$

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.

$\endgroup$

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