Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: YSYY66
CS 4124
Homework Assignment 1
Given : January 19, 2023
Due : February 3, 2023
General directions . The point value of each problem is shown in [ ]. Each solution must include all details and an explanation of why the given solution is correct. In particular , write complete sentences . A correct answer without an explanation is worth no credit . The completed assignment must be submitted on Canvas as a PDF by 5:00 PM on February 3, 2023. No late homework will be accepted .
Digital preparation of your solutions is mandatory . This includes digital prepa - ration of any drawings ; see syllabus concerning neat drawings included in L A TEX solutions . Use of L A TEX is required . Also , please include your name .
Use of L A TEX ( required ).
● Retrieve this LATEX source fi le, named homework1 .tex, from the course web site.
● Rename the fi le < Your VT PID>_solvehw1 .tex, For example, for the instructor, the file name would be heath_solvehw1 .tex.
● Use a text editor (such as vi, emacs, or pico) to accomplish the next three steps. Alternately, use Overleaf as your LATEX platform.
● Uncomment the line
% setboolean{solutions}{True}
in the document preamble by deleting the %.
● Find the line
enewcommand{author}{Lenwood S . Heath}
and replace the instructor’s name with your name.
● Enter your solutions where you fi nd the LATEX comments % PUT YOUR SOLUTION HERE
● Generate a PDF and turn it in on Canvas by 5:00 PM on February 3, 2023.
[ 20] 1. Textbook Problem 5 in B .1 on Page 520.
Prove Lemma A .4: For all alphabets Σ and all languages L ⊆ Σ 大 , the equiv - alence relation ≡L is right - invariant .
The lemma and the de fi nition of the equivalence relation are on Page 505.
[20] 2. Textbook Problem 3( c ) in B .2 on Page 522 .
Design an FA M , with alphabet Σ = {0, 1} , that recognizes ( c ) the set of all strings that contain the string 011 , in that order , but not necessarily consecu - tively .
Be certain you understand the set ( language ) of M before you start design - ing . Constructing some examples of strings both in L(M) and not in L(M) can be helpful .
You may use an algebraic speci fi cation or a transition diagram ( labeled di - rected graph ) speci fi cation to present your design for M . Be certain to explain why your design works .
[ 20] 3. Consider the OA M4 in Figure 3.4 on Page 60. Give a complete and
careful algebraic speci fi cation
M4 = (Q, Σ, δ, q0 , F)
for M4 .
[ 20] 4. Textbook Problem 7( c ) in B .2 on Pages 522 and 523.
Use a ( fooling set )- plus - ( Continuation Lemma ) argument to prove that the following language is not Regular :
L5 = {aibjck | i = j oR j = k}.
Your argument will be a proof by contradiction .
The Continuation Lemma is Lemma 3.2 on Page 57, while the fooling set kind of argument is fi rst utilized on Pages 76 and 77.