Question 1
Languaue
True False
Correct!
Question 2
Every DFA is also a NFA.
True
Correct!
o
h 1/11
.egaugnal raluger a si }0 ≥ m ,n ,mbna{ = L
2021/3/23
Question 3
For every three regular expressions R, S, and T, the languages denoted by and are the same.
True
False
Correct!
Question 4
To prove that a given language is regular, we can show that the language satisfies all three conditions of the pumping lemma.
True
False
Correct!
Question 5
Regarding the GNFA method discussed in class, changing the order of ripping out the states may change the language described by the final regular expression.
True
False
Correct!
False
h 2/11
)TR(∪)SR( )T∪ S(R
2021/3/23
Question 6
If R is a regular language and L is some language, and is a regular language, then L must be a regular language.
True False
Correct!
Question 7
All finite languages are regular.
True
False
Correct!
Question 8
r
The star (* operation) of a regular language may or may not be regular.
True False
rrect Answe
Question 9
1 / 1 pts
Language
o
h 3/11
.egaugnal raluger a si }0 ≥ m > n ,mbna{ = L
R∪L
2
Correct!
Question 10
All regular languages are finite.
True False
Correct!
Question 11
2 / 2 pts
Which of the following languages over alphabet {0, 1} is described by the regular expression ?
A) Any string over {0, 1} except the empty string.
B) Any string over {0, 1} of length at least one.
C) 0 or 1 followed by a string of any length over {0, 1}. D) All of the above
E) None of the above
D)
A) C) B) E)
Correct!
True False
h 4/11
+∑
2
Question 12
Let . Which of the following is true about B? (p is the pumping length)
A) B is non-regular because cannot be pumped. B) B is non-regular because cannot be pumped.
C) B is regular because the regular expression describes the language.
D) B is regular because a finite automaton can be built to recognize it. E) None of the above.
E) C) A) B) D)
Correct!
Question 13
Given the following NFA, which of the following does return?
A) B)
h 5/11
∗d∗c∗b∗a
pdpcpbpa d pcbb pa
)1q fo erusolc − ε( )}1q{( E
}0≥l ,k ,j ,i ,l+k=j+i ∣ ldkcjbia{=B
}1q{ Φ
2
rrect Answer
C)
D)
E) None of the above
A)
C) B) E) D)
The regular expression following language L?
A) L has at most one 0.
B) L has at least one 0s
C) L starts and ends with 0
D) L contains only even length strings E) L contains only odd length strings
D) A) C)
B) E)
Question 14
describes which of the
rrect Answer
o o
o
h 6/11
∗)1 ∪ 0(0∗)1 ∪ 0(
}2q ,1q ,0q{ }2q ,1q{
2
Question 15
2 / 2 pts
Let
about A? ( (p is the pumping length)
A) A is non-regular because B) A is non-regular because
. Which of the following is true
cannot be pumped.
is a context free language.
C) A is regular because the regular expression 000001111100000 describes the language.
D) A is regular because a finite automaton can be built to recognize it. E) Only C) and D) are correct.
A) B) D) C) E)
Correct!
Question 16
2 / 2 pts
Let DFA M consist of 4 states. Convert M into GNFA G. Before ripping out any states, how many states will G have?
4 6 5 7
Correct!
h 7/11
p0p1p0 p0p1p0
}5=m=n ,n0m1n0{=A
2
If we know that is a regular language, and that
is a non-regular ?
language, then what do we know about A) must be regular.
B) must be non-regular.
C) may or may not be regular.
D) This tells us nothing about regularity of E) None of the above.
E) A) D)
C) B)
, if
.
rrect Answer
Question 17
Question 18
If we know that is a regular language, and that
is a regular ?
language, then what do we know about A) must be regular.
B) must be non-regular.
C) may or may not be regular.
D) This tells us nothing about regularity of E) None of the above.
if
.
C)
o
h 8/11
3L
2L1L=3L 3L
2L 1L
1L
2L∩1L=3L 1L
3L 2L
3L 3L 3L
1L 1L 1L
2021/3/23
D) B) A) E)
rrect Answe
r
Question 19
Question 20
Let . Using the procedure discussed in class, if we convert the regular expression into a NFA N, how many accepting states will N have? Do not simplify.
A) 1
B) 2
C) 3
D) 4
E) This cannot be decided.
D)
Correct!
o
What is the minimum number of states a DFA can have?
2
0 1 3
h
9/11
∗)1∪0(
}1 ,0{=∑
2
rrect Answer
B) E) C) A)
Question 21
Short answer questions.
Note: For ALL the following short answer questions, write/draw your answer on white paper, mark the question number clearly, also write your name on top of each piece of the paper. Scan all answer sheets as a single PDF file, then upload.
Write/Draw legibly, unreadable answer will receive no grades! 1. [10 pts] Draw the DFA state diagram for the following language.
2. Let
(2.1) [10 pts] Draw the state diagrams of the two DFAs, each has two states and recognizing a simpler language. i.e. is of any strings with even length; is any string except .
(2.2) [10 pts] Use the product construction method discussed in class to draw the state diagram of a DFA that recognizes the original languge L. Show your state diagram before and after simplification.
3. [10 pts] Apply the algorithm we learned in class, convert the following NFA into an equivalent DFA, draw the resulting DFA’s state diagram. Note:
o
h1
noitisnart − ε ytpme stneserper λ dna }1 ,0{ = ∑
1L
}εtpecxegnirtsynasiDNAhtgnelnevefosiω ∣∗}1,0{∈ω{=L }lobmys emas eht htiw sdne dna strats ω ∣ ∗}1 ,0{ ∈ ω{ = L
ε 2L
2
4. [10 pts] Convert the following DFA into an equivalent Regular Expression by using the GNFA method, show step-by-step of your work. Please rip the states in the order of .
5. [20 pts] Use the pumping lemma to prove that the following language is non-regular.
11/11
}b ,a{=∑ 3q ,2q ,1q
}n2≤m≤n≤0 ,mbna{=L }b ,a{=∑