An n delay transducer in the context of the problem simply means that the output is same as the input but after waiting for 2 more symbols in the input.

2-delay transducer: We can't show any result till we see 2 symbols. So, to store in DFA we need states 00 01 10 11. But in order to create 00 01 10 11, we need another starting state: S0, state 0, state 1. That makes it 7 states.

The book says the following:

If input is a1a2... then output is (lambda)^n a1a2...

Construct a 2 day transducer over {a,b}

Prove that n delay transducer takes |{a,b}|^n states.

What I don't understand is that if we add the states that ultimately let us go to the states from where output can be given (for example, 00 01 10 11), then we get more than 2^n states for {a,b} alphabet.

Am I missing something or is the book not clear about this?

Question has been taken from peter linz's "An Introduction to Formal Languages and Automata" 5th Edition. Exercise 1.3 Problem No. 9

  • $\begingroup$ Why do you think the starting state needs to be different from the other 4? $\endgroup$
    – D.W.
    Aug 28, 2016 at 7:16
  • $\begingroup$ @D.W. Because we have to output empty string until 3 symbols are seen. If I use only 4 states, then I will have to output 00, 01, 10 or 11 for the first 2 symbols depending on which state is chosen as starting state. Please correct me if I'm wrong. $\endgroup$
    – aste123
    Aug 28, 2016 at 7:37


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.