4 4 votes Theory of Computation theory-of-computation turing-machine + – junaid ahmad 1.9k views answer comment Share Follow Print See all 3 Comments 3 3 Comments reply junaid ahmad commented Oct 5, 2017 reply Follow flag Need some clarity On S1. 0 0 replyShare rahul sharma 5 commented Oct 5, 2017 reply Follow flag 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 1 replyShare sachin! commented Oct 5, 2017 reply Follow flag s1 and s2 both are true 0 0 replyShare Please log in or register to add a comment.
0 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 0 reply Please log in or register to add a comment.
