CSE 105, Winter 2022 - Homework 1 2022
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
CSE 105, Winter 2022 - Homework 1
Instructions
Upload a single file to Gradescope for each group. All group members’ names and PIDs should be on each page of the submission. Your assignments in this class will be evaluated not only on the correctness of your answers, but on your ability to present your ideas clearly and logically. You should always explain how you arrived at your conclusions, using mathematically sound reasoning. Whether you use formal proof techniques or write a more informal argument for why something is true, your answers should always be well-supported. Your goal should be to convince the reader that your results and methods are sound.
Reading Sipser Sections 1.1 - 1.3
Key Concepts Deterministic finite automata (DFA), state diagram, computation trace, accept / reject, language of an automaton, regular language, union of languages, concatenation of languages, star of a language, closure of the class of regular languages under certain operations, nondeterministic finite automata (NFA)
Problem 1 (10 points)
For each of the below parts, draw the state diagram of the DFA that recognizes the given language. For full credit, it should have the minimal number of states (there is no need to prove that the number of states is minimal). Give a justification of why your DFA is correct, but no need for a complete formal proof.
1. 
= 
ℎ
Ø with Σ = {
, 
}
(2 POINTS)
2. 
= 
ℎ
ℎ
ℎ
ε with Σ = {
, 
}
(2 POINTS)
3. 
= {
∊ Σ* | 
1
, 
0
, 
ℎ 
0} with Σ = {0, 1}
(3 POINTS)
4. 
= {
∊ {0, 1} | 
ℎ
11}
NOTE: 111 does not belong to L since there are 2 occurrences of the substring ‘11’ (overlapping substrings) (3 POINTS)
Problem 2 (10 points)
Consider the following languages A and B
= {
∈ {0, 1} | 
1 
0}
= {
∈ {0, 1} | 
ℎ
}
1. Draw the state diagram of the DFA of the following language: 
∪ 
It may help to first construct the DFAs for A and B.
Briefly justify why your solution is correct.
(5 POINTS)
2. Draw the state diagram of the NFA of the following languages: (A)* ◦ B
Briefly justify the NFA constructed (No need for a formal proof of correctness).
(5 POINTS)
Problem 3 (10 points)
1. STATEMENT: All finite languages (languages with a finite number of strings) are regular.
Is the above mentioned statement true? If yes, prove the statement. Else, give a counterexample - a non-regular finite language.
(5 POINTS)
2. STATEMENT: All regular languages are finite.
Is the above mentioned statement true? If yes, prove the statement. Else, give a counterexample - an infinite regular language (language with an infinite number of strings) and draw the DFA for the language provided.
(5 POINTS)
Problem 4 (10 points)
Prove that regular languages are closed under union. That is, given two regular languages 
1 and 
2 , prove that 
1 ∪ 
2 is regular. In class we gave a high level overview of the proof. Here we are asking you to give the proof with full details.
(NOTE: in your proof, you are not allowed to assume the closure of regular languages under the complement/kleene star/union operations)
Problem 5 (10 points)
Recall the definition of regular languages. If a language L is regular, there exists a DFA which recognizes L.
1. Consider the language 
= {0
1
| 
≥ 0} .
Is A a regular language? If yes, construct a DFA which recognizes A. Else, justify intuitively as to why A is non-regular (no need for formal proof here).
(5 POINTS)
2. Consider the language 
= {0
1
| 
= 3} .
Is A a regular language? If yes, construct a DFA which recognizes A. Else, justify.
(5 POINTS)
2022-01-19