CS 4124 Homework Assignment 1
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
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 LATEX solutions. Use of LATEX is required. Also, please include your name.
Use of LATEX (required).
● Retrieve this LATEX source file, named homework1 .tex, from the course web site.
● Rename the file < 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
\renewcommand{\author}{Lenwood S . Heath}
and replace the instructor’s name with your name.
● Enter your solutions where you find 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 definition 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 specification or a transition diagram (labeled di- rected graph) specification 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 specification
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 first utilized on Pages 76 and 77.
2023-02-03