$L = \{x \in(a,b,c,d)^* \mid -10 \leq ( |x|_a + |x|_b) - ( |x|_c + |x|_d) \leq 10 \}$

I don't have any idea. Can someone help me.

  • 1
    $\begingroup$ I notice you've asked about 7 questions like this, about 7 different languages. I don't think it's useful to have an unending list of these types of questions. As has been suggested before (and also here), I suggest that you study our reference questions on this subject: cs.stackexchange.com/q/18524/755, cs.stackexchange.com/q/265/755. $\endgroup$ – D.W. Feb 11 '19 at 23:52
  • 1
    $\begingroup$ If you're still stuck, it would be best to show us in the question how you tried to apply those techniques, what progress you made, and where you got stuck. We'd like you to try those routes before asking here. See also here for tips on asking questions about exercise problems. $\endgroup$ – D.W. Feb 11 '19 at 23:54
  • $\begingroup$ Sinc you "don't have any idea", here is a hint. Can you construct PDA for a simpler language $\{x \in\{a,c\}^* \mid -1 \leq |x|_a-|x|_c \leq 1 \}$? For an even simpler language $\{x \in\{a,c\}^*\mid |x|_a-|x|_c =0 \}$? As requested by @D.W., it will be nice of you to show your work. $\endgroup$ – John L. Feb 12 '19 at 1:32
  • $\begingroup$ imgur.com/7aKDFEl I change a little bit. Now should be good $\endgroup$ – PoliteMan Feb 12 '19 at 2:29
  • $\begingroup$ so for my task in this question it will be the same for a, b I will put away one stacking symbol, let's say "AB" (this "a" in your example), and for c, d (your "c" from example) "CD" will be stacked and at the end the fork will have to have an additional 9 states to remove the CD and 9 additional states to remove AB? $\endgroup$ – PoliteMan Feb 12 '19 at 2:36

If anyone would be interested, here is my pda to $L = \{x \in(a,b,c,d)^* \mid -1 \leq ( |x|_a + |x|_b) - ( |x|_c + |x|_d) \leq 1 \}$

enter image description here


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.