In the sol of exam 2013Ba, the answers for the closed questions in part A.3 (Q11- Q14) were omitted. Can you please mention only the answer for each these questions? (Of course it'll be great if you can also give the equivalent language, specifically in Q12 and Q13, but only final answers would be fine also…)

11 - b : $L_2 = \{ 0^n 1^n \}$

12 - c : $L_1 = L_2 = \{ 0^m 1^n | m \geq n \}$

13 - c : $L_1 = L_2 = a^* b^*$

14 - c : $L_1 = L_2 = \Sigma^* 11 \Sigma^*$, where $\Sigma^* = \{0,1\}$

Hi,

in Q 4, I didn't understand the answer.what is M and what is P?what's the difference?

thanks

It's indeed a bit of a mess there,

P is the polynomial which bounds M's running time, i.e, on any input x, M runs at most P(|x|) steps.

hey,

could you please explain what do they mean by saying: M accepts in n steps when given (x,c) as input..

what's an input (x,c)? does it mean that M gets 2 words, x & c and stops within n steps on each one of them?

thanks

Q4 as well:

hey,

could you please explain what do they mean by saying: M accepts in n steps when given (x,c) as input..

what's an input (x,c)? does it mean that M gets 2 words, x & c and stops within n steps on each one of them?

thanks