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.
$\begingroup$
$\endgroup$
2
-
$\begingroup$ I got a solution on stackowerflow, but thanks for trying to help. $\endgroup$– meightythreeNov 16, 2017 at 12:35
-
$\begingroup$ stackoverflow.com/questions/47288671/… $\endgroup$– meightythreeNov 16, 2017 at 12:35
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
answered Nov 14, 2017 at 21:23