CSC 427: Theory of Computation 1
Monday, 7 March 2022 10:30–11:20 AM
There are 5 problems each worth 6 points for a total of 30 points. No notes, no collaboration. Please respect and uphold the integrity of the examination process. Sign the cover page to show agreement with these instructions.
Problem Credit 1
Programming Help
CSC 427: Theory of Computation 2 1. Give an DFA that accepts the language,
{s ∈ {0,1}∗ |s does not contain the substring 101}
You must draw the diagram of the DFA, making sure to indicate the start and accept states and all necessary arrows.
CSC 427: Theory of Computation 3
2. (a) Use the pumping lemma to show that the language {s ∈ {0,1}∗ |s = (01)i(10)i for i ≥ 0}
is not regular.
(b) Show that the language
is regular.
{s ∈ {0,1}∗ |s = (01)i(01)i for i ≥ 0}
程序代写 CS代考 加QQ: 749389476
CSC 427: Theory of Computation 4
3. Write a Regular Expression that expresses the same language as the following NFA. Although it is not necessary to take all the states de- manded by the textbook’s approach (there are shortcuts), you must show the relevant work.
CSC 427: Theory of Computation 5
4. Write a Context Free Grammar that expresses the same language as a Regular Expression,
CSC 427: Theory of Computation 6
Check ( ) the box if the operation is closed for the language class,
Context Free
Union Concatenation Star Intersection Complement
Are all Regular languages also Context Free languages?
Given a Context Free language and a Regular language, their in- tersection can be (check all that apply),
Regular Context Free neither