Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Question: L={0^n1^n | n>=1}

I have found these transitions for the given language: 1)delta(q,0,Z)=(q,0Z) 2)delta(q,0,0)=(q,00) The above two rules will cause one 0 to be pushed onto the stack for each 0 read from the input.

3)delta(q,1,0)=(p,epsilon), when we see a 1 in the input go to state p and pop one 0 from the stack. 4)delta(p,1,0)=(p,epsilon), pop one 0 from stack, per 1 read from the input. 5)`delta(p,epsilon,Z)=(final state, Z), now the whole input is consumed and we reach the final state and the stack is empty and we have hit the bottom of the stack. Symbol 'Z' denotes the bottom of the stack.

Please tell me whether my solution to this problem is correct? Thank You

share|cite|improve this question
If you’re accepting by final state, it looks fine, provided that you specify that final state is an accepting state. – Brian M. Scott Oct 12 '12 at 10:03

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.