CS/ECE 374 A (Spring 2022) Homework 1 Solutions
Problem 1.1: Let L ⊆ {0, 1}∗ be the language defined recursively as follows:
The empty string ε is in L.
For any string x in L, the strings 0101x and 1010x are also in L.
Copyright By PowCoder代写 加微信 powcoder
For any strings x, y such that xy is in L, the strings x00y and x11y are also in L. (In other words, inserting two consecutive 0’s or two consecutive 1’s anywhere to a string in L yields another string in L.)
The only strings in L are those that can be obtained by the above rules. Define Lee = {x ∈ {0, 1}∗ : x has an even number of 0’s and an even number of 1’s}.
(a) Prove that L ⊆ Lee, by using induction. (You should use strong induction.) (b) Conversely, prove that Lee ⊆ L, by using induction.
Solution: Let #0(x) denote the number of 0’s in x, and #1(x) denote the number of 1’s in x.
(a) It suffices to prove the following claim:
Claim 1. For every string w ∈ L, the numbers #0(w) and #1(w) are both even.
Proof. The proof is by (strong) induction on the length |w|.
Base case: |w| = 0. Here, w = ε and #0(w) = #1(w) = 0, so the claim is trivially true.
Induction hypothesis. Suppose n ≥ 1. Assume that for every string w′ ∈ L with |w′| < n, the numbers #0(w′) and #1(w′) are both even.
Induction step. Let w ∈ L with |w| = n. We want to prove that #0(w) and #1(w) are both even.
By the recursive definition of L, we know that one of the following cases must hold:
Case1: w=0101xforsomestringx∈L. Since|x|=|w|−2
αn = βαn = γαn =
9αn−1+βαn−1
8αn−1 + βαn−1 + γαn−1
8αn−1 + βαn−1, 3
βα = 8+β+γ γα = 8+β.
These conditions are equivalent to β = α−9, and γ = (α−1)/α, and (α−9)α = α−1+ (α − 1)/α. The latter simplifies to the cubic equation α3 − 10α2 + 1 = 0, which has root α = 9.9899799 · · · < 9.990.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com