CSC 427: Theory of Computation 1
Wednesday, 4 March 2020 9:10–10:00 AM
There are 5 problems each worth 6 points for a total of 30 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
CSC 427: Theory of Computation 2
1. Give an NFA that accepts exactly the strings over the alphabet { 0, 1 } such that the number of 01 substrings equals the number of 10 sub- strings. (Exactly means, those string and only those strings. The empty string happens to be such a string, by the way.)
Next, give a machine with the fewest number of states. Do not worry if you believe your first answer had the minimum number of states. This is just a problem to come back to later, to see if you can improve your otherwise correct solution.
CSC 427: Theory of Computation 3
2. Write a Regular Expression that expresses the same language as the following FSA.
浙大学霸代写 加微信 cstutorcs
CSC 427: Theory of Computation 4
3. Show that the language
{ai#bj#ck#dn| wherei,j,k≥0andi+j+k=n}
is not regular.
Github
CSC 427: Theory of Computation 5
4. Give a Context Free Grammar for the language, {aibjck |i = j or i = k}
Then show that the CFG is ambiguous by giving two parse trees in you grammar of the string aaabbbccc.
Programming Help, Add QQ: 749389476
CSC 427: Theory of Computation 6
5. Give a Context Free Grammar for the Regular Expression: ab∗ (a|b)(c(a|b))∗
Give a Regular Expression for the following Context Free Grammar, or give a proof or a concise logical argument why an equivalent Regular Expression does not exist,
A −→ aA|a X −→ ε|abXc