Description
Question 1 (20 points)
State whether the following are true or false. Explain your reasoning in one sentence. In case of unclear
interpretation of terms, refer to the lecture notes and recordings or the related sections from the textbook.
a) (5 points) All real numbers can be represented as strings over the alphabet Σ = {0, 1, 2, . . . , 9}.
b) (5 points) All languages are finitely representable.
c) (5 points) bba ∈ L = a
∗
b
∗a
∗
b
∗
d) (5 points) a
+b
+(a
S
b)
∗
represents the set of all strings over {a, b} that has ab as prefix.
Question 2 (40 points)
Give a DFA that recognizes the language;
{ω ∈ {a, b}
∗
: ω does NOT have aba as a substring}
a) (20 points) Formally define the DFA as a quintuple M = {K, Σ, δ, s, F}. Give each of K, Σ, δ, s, F.
K :
Σ :
s :
F :
δ :
b) (20 points) For this DFA trace the input abbaabab and write the computation. Does the DFA
accept the input?
1
Question 3 (40 points)
This question adheres to the notation used in the proof of Theorem 2.2.1 in the textbook.
a) (10 points) Consider the NFA M = {K, Σ, ∆, s, F} below. For each state q ∈ K calculate E(q).
start q0 q1 q2
q3 q4
b
e
a
e
b
a
e
a, b
e
e
b) (30 points) The following is a set of instructions to convert an NFA M into a DFA M′
. It is
known that M does not have any empty transitions from its starting state. Identify in which steps the
instructions go astray. State your reasons and correct the steps.
Let M = {K, Σ, ∆, s, F} and M′ = {K′
, Σ
′
, δ, s′
, F′}.
1. Define K′ as the set consisting of all subsets of K.
2. Define the alphabet Σ
′ as precisely the set Σ.
3. Define the set of starting states, s
′ as the set whose only element is s.
4. Define the set of final states, F
′ as those elements of K′ which consists of only the states q ∈ F.
5. Define the transition function δ as taking two inputs: an element Q of K′ and an element of a of
Σ
′
. The function returns the set whose elements are precisely those states p in K for which there
exists a q ∈ Q and (q, a, p) ∈ ∆.
Specifications
• Deadline: The deadline for this homework is strict and no late submissions will be accepted.
Submission deadlines are not subject to postponement.
• Grading: “sufficiently reasonable” solutions will get full credit for the subject question,
even if it is partially incorrect. Rough criteria for a solution to be sufficiently reasonable are being
the student’s original answer and at least partially relying on a correct approach/method even if the
application is not totally correct.
• Cheating: Any type of cheating or extensive collaboration is strictly prohibited. In case of cheating,
the cheater’s all homeworks will be graded zero (0); further, university regulations about cheating
will be applied.
• Updates: Follow the course page on ODTUClass for any updates and clarifications. Please ask your
questions on ODTUClass instead of e-mailing if they do not contain some part of the solution. Otherwise, you can send an email to “mduymus@ceng.metu.edu.tr” and/or “mferhata@ceng.metu.edu.tr”.
2
Submission
Submissions will be done via ODTUClass. You are expected to submit a single searchable/vectorized
PDF file named “hw1.pdf”.
3
