Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Assignment 1 – Deadline September 20, 11:59 pm

September 13, 2022

Instructions:  The goal of this course is to strive for mathematical clarity in computation. In that spirit, please make sure your answers are clear, concise and rigorous.  The onus for all three is on you.  Use a word processor to type your answers (preferably Latex).

Assignment can be done in groups of 2 with one submission. Please indicate both the names on the submission (if done in a group).

1.   [10 points] Let Lk   =  {北  ∈ {0, 1}*   :the kth   bit from the right is  1}. Consider the set A =  {0, 1}k .   Show that any two strings 北 and y in A are distinguishable with respect to Lk   (thus showing that any DFA for Lk  has at least 2k  states).

2.   [10 points] Let L ⊆ {0, 1}*  be a regular language.   For any string 北, let 北R  be its reverse string.  As an example, if 北 = 0010, 北R  = 0100.  Show that L\  = {北 : 北北R  ∈ L} is also regular.

3.   [10 points] Let L =  {0i 1j   : j  > i}.   Let A =  {0i   : i ≥ 1}.   Prove that L is not regular by showing that for any 北,y ∈ A (where 北  y), 北 and y are distinguishable with respect to L.

4.   [10 points] Let  L  =  {北  ∈ {0, 1}*   :  北 is the binary representation of a number divisible by 3}. Prove that L is regular by constructing a DFA for L.