Description
1 attachmentsSlide 1 of 1attachment_1attachment_1
Unformatted Attachment Preview
•
•
•
•
•
•
•
1. Let = a, b . As the following example shows, for each regular expression, write the formal English
description of the set described by the regular expression. 20 points
Example:
(0 ∪ 1)∗ 00(0 ∪ 1)∗ 11(0 ∪ 1)∗
Answer: 𝑳 = {𝑥𝑦 |𝑤ℎ𝑒𝑟𝑒 𝑥 𝑐𝑜𝑛𝑡𝑎𝑖𝑛𝑠 𝑠𝑢𝑏𝑠𝑡𝑟𝑖𝑛𝑔 00 𝑎𝑛𝑑 𝑦 𝑐𝑜𝑛𝑡𝑎𝑖𝑛𝑠 𝑠𝑢𝑏𝑠𝑡𝑟𝑖𝑛𝑔 11}
a) 𝑎+ (bb)* ∪ 𝑏 * 𝑎(𝑎𝑎)*
b) (𝛴 ∗ aba Σ* ∪ 𝛴 ∗ babΣ* )𝛴∗ abbΣ*
c) 𝑎∗ ∪ (𝑎∗ 𝑏𝑎∗ 𝑏𝑎∗ 𝑏𝑎∗ )∗
d) 𝑏𝑎Σ∗ 𝑎Σ ∗ Σ∗
2. Let = 0,1 . For each part below, write the regular expression that describes the language. 15 points
a) L1 = w | w is of even length and w 0
b) 𝐿2 = {𝑤|𝑤 has an even number of 0s and an odd number of 1s}
c) L3 = {w | w is any string except 0, 01, 11, 1100, 1101, 1110, 1111}
1
3. Use the GNFA method discussed in class to convert the following DFA into an equivalent regular
expression. Note: 1) eliminate states in order of q1, q2, q3,…, 2) you must show all steps to receive full
credit. 15 points
Let DFA M = ({q1 , q2 , q3 , q4 },{0,1}, , q1 ,{q1 , q2 , q3}) where the transition function table is listed as
below. Draw its state diagram first before eliminating states.
q1
q2
q3
0
q4
q3
q4
q4
q4 q4
1
q2
q4
q2
4. Let = 0,1 . Use the procedure given in Lemma 1.55 to convert the following regular expression into
an NFA. You must show all steps to receive full credit. 10 points
(01)+ 10(𝜀 ∪ Σ)
5. For each part, first identify whether the language is regular or not, you must justify your answers to
receive full credit. If the language is non-regular, use the pumping lemma to prove it. 40 points, 10 pts
each
a) 𝐿4 = {𝜔𝜔𝑅 | 𝜔 ∈ {0, 1}∗ , 𝑎𝑛𝑑 𝜔𝑅 𝑖𝑠 𝑡ℎ𝑒 𝑟𝑒𝑣𝑒𝑟𝑠𝑎𝑙 𝑜𝑟 𝜔}
b) 𝐿5 = {𝑥𝑦||𝑥| = |𝑦| and 𝑥, 𝑦 ∈ {0,1}* }
c) 𝐿6 = {𝑎𝑖 𝑏 𝑗 𝑐 𝑘 | 𝑗 = 𝑖 + 𝑘 and 𝑖, 𝑗, 𝑘 > 0}
d) 𝐿7 = {𝜔 | 𝜔 ∈ {0, 1}∗ , 𝑎𝑛𝑑 𝑁0 (𝜔)% 3 > 𝑁1 (𝜔)% 3}.
𝑵𝒐𝒕𝒆: 𝑁0 (𝜔) 𝑟𝑒𝑝𝑒𝑟𝑠𝑒𝑛𝑡𝑠 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 0𝑠 𝑖𝑛 𝜔; % 𝑖𝑠 𝑡ℎ𝑒 𝑚𝑜𝑑𝑢𝑙𝑜 𝑜𝑝𝑒𝑟𝑎𝑡𝑜𝑟
2
Purchase answer to see full
attachment
Explanation & Answer:
Worksheet
User generated content is uploaded by users for the purposes of learning and should be used following Studypool’s honor code & terms of service.
