6 votes 6 votes Theory of Computation theory-of-computation turing-machine + – junaid ahmad asked Oct 5, 2017 junaid ahmad 1.4k views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply junaid ahmad commented Oct 5, 2017 reply Follow Share Need some clarity On S1. 0 votes 0 votes rahul sharma 5 commented Oct 5, 2017 reply Follow Share S1.I think by first it means that Turing machine goes only in one direction(Right).As we read input from left to right and machine is not allowed to write on the left side means machine can write in one direction turing machine which makes it One way turing machine and hence same power as FA,making S1 as true. S2:- True. Can be handled by LBA S3:- It is used to prove that language is not regular. Only 2 are true 1 votes 1 votes sachin! commented Oct 5, 2017 reply Follow Share s1 and s2 both are true 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes https://gateoverflow.in/75866/madeeasy-test-series Only S3 differ from this question. Pumping lemma is used as negativity test, i.e, it can only tell us that given language is not regular. So S3 should be false. ♥_Less answered Oct 7, 2017 ♥_Less comment Share Follow See all 0 reply Please log in or register to add a comment.