CSC 427: Theory of Computation 1
Wednesday, 31 March 2021 10:30–11:20 AM
There are 5 problems each worth 6 points for a total of 30 points.
As an important protocol for today?s test, please turn your camera?s on. This would help align this class? protocol with those of the other classes at UM. While situations differ, every student is responsible for insuring the integrity of the test, and must take all reasonable steps in support of insuring
the integrity.
No notes, no collaboration.
Please sign the cover page so show agreement with these directions.
Problem Credit 1
CSC 427: Theory of Computation 2
1. Give an DFA that accepts exactly the strings over the alphabet { 0, 1 } that contain the substring 00101.
Computer Science Tutoring
CSC 427: Theory of Computation 3
2. Give a Context Free Grammar for the language over the alphabet {a,b}∗ of strings of the form ai bj aj bi where i,j ≥ 0.
Code Help, Add WeChat: cstutorcs
CSC 427: Theory of Computation 4
Check ( ) the box if the operation (Union, Concatentation, etc.) is closed for the language class (Regular or CFL).
Reg. Lang. CFL’s
Union Concatenation Star Intersection Complement
(b) Are all Regular Languages also Context Free Languages?
(c) Is the intersection of a CFL with a Regular language necessarily (check all that apply),
Regular CFL neither
CSC 427: Theory of Computation 5
4. Give a Regular Expression for the language over { a, b }∗ for strings that contain an even number of a’s and an odd number of b’s.
Programming Help
CSC 427: Theory of Computation 6 5. Prove that the language,
a+bici ∪ b∗c∗
First show that the pumping lemma fails to show this language is non-
for i ≥ 0, is not regular.
regular, when applied in a straight forward manner.
Then take a step to distill the non-regularity and apply the pumping language to the derived problem.