CSC 427: Theory of Computation 1
Friday, 3 March 2017 1:25–2:15 PM
There are five problems each worth five points for a total of 25 points. Show all your work, partial credit will be awarded. Space is provided on the test for your work; if you use a blue book for additional workspace, sign it and return it with the test. No notes, no collaboration.
Problem Credit 1
Programming Help, Add QQ: 749389476
CSC 427: Theory of Computation 2
1. Give an NFA accepting any string in {0, 1}∗ that contains the substring 10110111
浙大学霸代写 加微信 cstutorcs
CSC 427: Theory of Computation 3
2. Give a DFA accepting any string in {0, 1}∗ that contains the substring 10110111.
CSC 427: Theory of Computation 4
3. Write a Regular Expression that expresses the same language as the following FSA.
程序代写 CS代考 加QQ: 749389476
CSC 427: Theory of Computation 5
4. The language {(01)i(10)i | i ≥ 0} subset of {0, 1}∗ is accused of being non-regular. Show how the Prosecutor proceeds in the Court of Logic under all arguments by the Advocate to get a guilty verdict (i.e. show that the language is non-regular).
CSC 427: Theory of Computation 6
5. The language {(01)i(01)i | i ≥ 0} subset of {0, 1}∗ is accused of being not regular. Show how the Advocate proceeds in the Court of Logic under all arguments by the Prosecutor to get an acquittal (i.e. show that the language is regular).