Theoretical Foundations of Computing Spring

Due Date: March 24 (Wednesday), 2021
————————————————————————————————————————————————————

1. Read [Sip12] Chapter 0; you may need to review the prerequisite materials in discrete mathematics to have sufficient
   working knowledge for this course.
2. For each of the following languages, construct a finite automaton (deterministic, nondeterministic, or nondeterministic finite automaton with ǫ-transitions — unless unless specifically stated) that accepts the language.
   You need to give the key idea(s) for your construction, and brief and precise interpretations for the states of the
   machine.
   (a) [ Construction of “deterministic finite automaton” is required. ]
   {x ∈ {0, 1}
   ∗
   | #0(x) = #1(x) and every prefix of x has at most one more 0 than 1s and
   at most one more 1 than 0s }.
   (Note: #u(v) denotes the number of occurrences of a substring u in a string v.)
   (b) [ Construction of “deterministic finite automaton” is required. ]
   {a
   i
   b
   j
   | i, j ≥ 0, and i + j is even}.
   (c) [ Construction of “deterministic finite automaton” is required. ]
   {x ∈ {0, 1, 2}
   ∗
   | #1(x) + #2(x) is divisible by 3}.
   (d) {x ∈ {0, 1}
   ∗
   | there exist two 0s in x that are separated by a string of length 5k for some k ≥ 0 }.
   (e) The set of all strings over the alphabet {a, b, c} that yield the same value when evaluated from left to right
   as right to left by “multiplying” according to the following table in Figure 1.
   For examples: ((a ◦ b) ◦ b) = (c ◦ b) = a and (a ◦ (b ◦ b)) = (a ◦ a) = a, whereas ((a ◦ b) ◦ c) = (c ◦ c) = b and
   (a ◦ (b ◦ c)) = (a ◦ c) = c.
   ◦
   a b c
   a
   c
   b
   c b
   b c
   a
   a c c
   a
   Figure 1: A non-associative multiplication table for ◦.
3. Prove that there does not exist any deterministic finite automaton that accepts the following language:
   {abn
   a
   2n
   | n ≥ 1}.
4. Consider a nondeterministic finite automaton M1 = (Q, Σ, δ, q0, F1). Define a (new) nondeterministic finite automaton M2 = (Q, Σ, δ, q0, F2) with F2 = Q − F1.
   Prove, or disprove (with explicit counter-example and detailed explanation), the following statement: the language
   L(M2) is the complement of the language L(M1) (that is, L(M2) = Σ∗ − L(M1)).
   1
5. Let the alphabet Σ = {a}. Assume that that M is a nondeterministic finite automaton with m states such that
   M accepts every string x ∈ Σ
   ∗ with |x| ≤ m.
   Prove, or disprove (with explicit counter-example and detailed explanation), the following statement: L(M) = Σ∗
   .
6. Consider the following language operator, Dequeue as follows, for a given language L over an alphabet Σ
   Dequeue (L) = {w ∈ Σ
   ∗
   | w = vw ∈ L with |v| = 1}.
   That is, Dequeue (L) removes the leftmost symbol of every string in L. Show that Dequeue preserves regularity.
7. Let Σ be the alphabet {0, 1}. Denote by L the language {u ∈ Σ
   ∗
   | u = vv for some string v ∈ Σ
   ∗}. Prove or
   disprove that the language L can be expressed as the concatenation of two “non-trivial” languages L1 and L2 over
   Σ: L1 6= {ǫ} and L2 6= {ǫ} and L = L1L2.
   2