0
$\begingroup$

How can I construct a PDA which accepts the language $\{a^i b^j c^k \mid k\geq \min(i,j)\}$

I think about different solutions such as building a stack with two-state. one state is for $i < j$ and another is for $i > j$, But I think it doesn't work.

also, The idea of poping and pushing a and b is not good. I tried it. Can Someone give me a little hint?

$\endgroup$
2
  • $\begingroup$ Your basic idea looks like a good starting point. Try to think of how to implement the decision whether $i<j$ or vice versa, and how you could split the cases up. $\endgroup$
    – nir shahar
    May 8 at 21:48
  • $\begingroup$ @nirshahar I think about this. but the idea is related to pushing a and poping b, and when I do this I lost my data for c and I can't decide on that $\endgroup$
    – hermi
    May 8 at 21:51
1
$\begingroup$

Your idea to differentiate between $i<j$ and $i >j$ is good.

To help you building the PDA, note that $L = \{a^ib^jc^k | k \geq i\} \cup \{a^ib^jc^k|k\geq j\}$.

I hope that hint is enough.

$\endgroup$
1
  • $\begingroup$ Thanks, I got the point. $\endgroup$
    – hermi
    May 8 at 22:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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