11/9/2020 Pop Quiz #13: FA20: CS-154 Sec 04 - Formal Lang and Comput
Pop Quiz #13
Due Oct 15 at 11:59pm Points 10 Questions 7
Available after Oct 14 at 9am Time Limit None Allowed Attempts 3
Take the Quiz Again
Attempt History
Attempt Time Score
LATEST Attempt 1 8 minutes 10 out of 10
m
er as
co
Score for this attempt: 10 out of 10
eH w
Submitted Oct 14 at 9:44pm
o.
This attempt took 8 minutes.
rs e
ou urc
Question 1 pts
o
aC s
vi y re
Consider the following languages over Σ = {a, b} with the notations below
na(w): number of a's in string w
ed d
nb(w): number of b's in string w
ar stu
L1 ={w: na(w) = nb(w)}
is
L2 ={w: na(w) >= nb(w)}
Th
L3= {w: na(w) <= nb(w)}
L4 = {w: na(w) > nb(w)}
L5 = {w: na(w) < nb(w)}
sh
L6 = {w: na(w) nb(w)}
Correct! L1 and L6 are complement Correct
to each other
Correct! L6 = L4 + L5
This study source was downloaded by 100000823516103 from CourseHero.com on 07-06-2021 10:44:37 GMT -05:00
https://sjsu.instructure.com/courses/1373758/quizzes/1427227?module_item_id=11285053 1/7
https://www.coursehero.com/file/76602489/Pop-Quiz-13-FA20-CS-154-Sec-04-Formal-Lang-and-Computpdf/
, 11/9/2020 Pop Quiz #13: FA20: CS-154 Sec 04 - Formal Lang and Comput
Correct
Correct! (L2+L3) is a regular Correct
language
Correct! L3 and L4 are complement Correct
to each other
Other Incorrect Match Options:
Incorrect
m
Question 2 pts
er as
co
eH w
o.
(Cont.)
rs e
ou urc
Give the grammar for L1. Assume the start symbol is A.
L1 ={w: na(w) = nb(w)}
o
aC s
vi y re
Correct!
A --> AA | aAb|bAa| ε
ed d
A --> AA | aAb|bAa| a|b| ε
ar stu
A --> aAb|bAa| ε
is
None is a correct answer
Th
sh
Question 3 pts
(Cont.)
This study source was downloaded by 100000823516103 from CourseHero.com on 07-06-2021 10:44:37 GMT -05:00
https://sjsu.instructure.com/courses/1373758/quizzes/1427227?module_item_id=11285053 2/7
https://www.coursehero.com/file/76602489/Pop-Quiz-13-FA20-CS-154-Sec-04-Formal-Lang-and-Computpdf/
Pop Quiz #13
Due Oct 15 at 11:59pm Points 10 Questions 7
Available after Oct 14 at 9am Time Limit None Allowed Attempts 3
Take the Quiz Again
Attempt History
Attempt Time Score
LATEST Attempt 1 8 minutes 10 out of 10
m
er as
co
Score for this attempt: 10 out of 10
eH w
Submitted Oct 14 at 9:44pm
o.
This attempt took 8 minutes.
rs e
ou urc
Question 1 pts
o
aC s
vi y re
Consider the following languages over Σ = {a, b} with the notations below
na(w): number of a's in string w
ed d
nb(w): number of b's in string w
ar stu
L1 ={w: na(w) = nb(w)}
is
L2 ={w: na(w) >= nb(w)}
Th
L3= {w: na(w) <= nb(w)}
L4 = {w: na(w) > nb(w)}
L5 = {w: na(w) < nb(w)}
sh
L6 = {w: na(w) nb(w)}
Correct! L1 and L6 are complement Correct
to each other
Correct! L6 = L4 + L5
This study source was downloaded by 100000823516103 from CourseHero.com on 07-06-2021 10:44:37 GMT -05:00
https://sjsu.instructure.com/courses/1373758/quizzes/1427227?module_item_id=11285053 1/7
https://www.coursehero.com/file/76602489/Pop-Quiz-13-FA20-CS-154-Sec-04-Formal-Lang-and-Computpdf/
, 11/9/2020 Pop Quiz #13: FA20: CS-154 Sec 04 - Formal Lang and Comput
Correct
Correct! (L2+L3) is a regular Correct
language
Correct! L3 and L4 are complement Correct
to each other
Other Incorrect Match Options:
Incorrect
m
Question 2 pts
er as
co
eH w
o.
(Cont.)
rs e
ou urc
Give the grammar for L1. Assume the start symbol is A.
L1 ={w: na(w) = nb(w)}
o
aC s
vi y re
Correct!
A --> AA | aAb|bAa| ε
ed d
A --> AA | aAb|bAa| a|b| ε
ar stu
A --> aAb|bAa| ε
is
None is a correct answer
Th
sh
Question 3 pts
(Cont.)
This study source was downloaded by 100000823516103 from CourseHero.com on 07-06-2021 10:44:37 GMT -05:00
https://sjsu.instructure.com/courses/1373758/quizzes/1427227?module_item_id=11285053 2/7
https://www.coursehero.com/file/76602489/Pop-Quiz-13-FA20-CS-154-Sec-04-Formal-Lang-and-Computpdf/
